Rekursion mit while(true)?

[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?

[Prof. Karsten Weihe]

Gilt das als rekursiv?

Warum soll das als rekursiv gelten, wo ist die Rekursion

KW

[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

[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;
}

[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...)

[Prof. Karsten Weihe]

Also ist die while(true)-Lösung keine Rekursion

Nein

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.

Ich hatte zwei Tutoren so verstanden, dass while(true) eine rekursive Lösung ist.

Das kann wohl nur ein Missverständnis gewesen sein.

Ein Kumpel hingegen hat im Testat gesagt bekommen, dass es keine ist und in der Klausur Punktabzug droht.

Und zwar heftig

KW