Rekursion mit while(true)?

escape
Erstie
Erstie
Beiträge: 12
Registriert: 25. Apr 2015 20:47

Rekursion mit while(true)?

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

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Rekursion mit while(true)?

Beitrag von Prof. Karsten Weihe »

escape hat geschrieben: Gilt das als rekursiv?
Warum soll das als rekursiv gelten, wo ist die Rekursion :?:

KW

escape
Erstie
Erstie
Beiträge: 12
Registriert: 25. Apr 2015 20:47

Re: Rekursion mit while(true)?

Beitrag 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

KaeferZuechter
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 108
Registriert: 15. Apr 2015 19:24

Re: Rekursion mit while(true)?

Beitrag 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;
}
IT'S CALLED A FOURIER TRANSFORM WHEN YOU TAKE A NUMBER AND CONVERT IT TO THE BASE SYSTEM WHERE IT WILL HAVE MORE FOURS, THUS MAKING IT "FOURIER". IF YOU PICK THE BASE WHERE IS HAS THE MOST FOURS, THE NUMBER IS SAID TO BE "FOURIEST".

\(1160_8 \rightarrow 624_{10} \rightarrow 440_{12} \rightarrow 4444_5\)

- Zach Weiner -

escape
Erstie
Erstie
Beiträge: 12
Registriert: 25. Apr 2015 20:47

Re: Rekursion mit while(true)?

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

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Rekursion mit while(true)?

Beitrag 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

Antworten

Zurück zu „Archiv“