Seite 1 von 1

Rekursion mit while(true)?

Verfasst: 7. Jul 2015 14:07
von escape
Kann eine while(true)-Schleife eine rekursive Lösung sein?

Beispiel: Gesucht wird der größte Wert ab einem bestimmten Knoten im binären Baum.

Code: Alles auswählen

Node p = startKnoten;

while(true) {
   if(p == null || p.right == null) {
      break;
   } else {
      p = p.right;
   }
}
Gilt das als rekursiv?

Re: Rekursion mit while(true)?

Verfasst: 7. Jul 2015 14:11
von Prof. Karsten Weihe
escape hat geschrieben: Gilt das als rekursiv?
Warum soll das als rekursiv gelten, wo ist die Rekursion :?:

KW

Re: Rekursion mit while(true)?

Verfasst: 7. Jul 2015 14:32
von escape
Die folgende Funktion sollte die als Beispiel genannte while(true)-Lösung ersetzen können.

Code: Alles auswählen

function recFun(node p) {
   if(p.right == null) {
      return p;
   } else {
      return recFun(p.right);
   }
}
Ich will nicht behaupten, dass technisch oder hardwarenah gesehen das gleiche passiert. Aber ist nicht der Ablauf der gleiche?

In Worten gesagt, funktioniert die Suche so: "Gibt es noch ein größeres Kind? Ja => führe die selbe Prüfung nochmal mit diesem Kind durch. Nein => der aktuelle Knoten ist der größte"
Die Rekursion in der while(true)-Schleife würde ich darin sehen, dass
  • der gleiche Code ein wiederholt aufgerufen wird,
  • dabei das Ergebnis des letzten Aufrufs als Parameter des nächsten dient,
  • ein Problem schrittweise verkleinert wird; im nächsten Schritt ist nur noch der Teilbaum ab dem Knoten zu bearbeiten

Re: Rekursion mit while(true)?

Verfasst: 7. Jul 2015 14:48
von KaeferZuechter
Jede primitive Rekursion entspricht einer Iteration und umgekehrt.
Viele Compiler/Interpreter werden Rekursionen aus Effiziensgründen auch intern in Iterationen umwandeln.
Rekursiv programmiert man normalerweise, weil es eleganter und lesbarer ist.


Die while-Schleife sollte man IMHO besser so schreiben:

Code: Alles auswählen

Node p = startKnoten;

while(!(p == null || p.right == null)) {
      p = p.right;
}

Re: Rekursion mit while(true)?

Verfasst: 7. Jul 2015 17:36
von escape
Also ist die while(true)-Lösung keine Rekursion, sondern lediglich eine Iteration die - vom Ablauf her und oberflächlich - das gleiche tut wie eine Rekursion?

(Ich hatte zwei Tutoren so verstanden, dass while(true) eine rekursive Lösung ist. Ein Kumpel hingegen hat im Testat gesagt bekommen, dass es keine ist und in der Klausur Punktabzug droht. Deswegen meine Verwirrung über diese Art der Schleifenverwendung, von der ich eigentlich gar nicht besonders begeistert bin...)

Re: Rekursion mit while(true)?

Verfasst: 7. Jul 2015 18:21
von Prof. Karsten Weihe
escape hat geschrieben:Also ist die while(true)-Lösung keine Rekursion
Nein :!:

escape hat geschrieben: sondern lediglich eine Iteration die - vom Ablauf her und oberflächlich - das gleiche tut wie eine Rekursion?
Wenn Sie damit die allgemein bekannte Aussage meinen, dass jede Iteration in eine äquivalente Rekursion umgewandelt werden kann, stimme ich Ihnen zu. Ansonsten ist mir nicht klar, was Sie mit diesem Satz meinen.

escape hat geschrieben: Ich hatte zwei Tutoren so verstanden, dass while(true) eine rekursive Lösung ist.
Das kann wohl nur ein Missverständnis gewesen sein.

escape hat geschrieben: Ein Kumpel hingegen hat im Testat gesagt bekommen, dass es keine ist und in der Klausur Punktabzug droht.
Und zwar heftig :!: :shock:

KW