Frage zu Rekursiven Funktionen!

T0bi

Hi,

Ich bin gerade mal nen bissel dabei mich mit rekursiven Funktionen auseinander zusetzen. Da hab ich nen bissel in alten Tutorials rumgekrammt und bin bei Arnold W. hängen geblieben und zwar bei dem Beispiel mit dem Binärbaum.
http://www.willemer.de/informatik/cpp/rekursion.htm

Ich denke das ich verstehe wie so der Ablauf ist von einer Rekursion, aber diese Funktion verstehe ich nicht:

void ZeigeBaum(tBaum *Blatt)
{
    if (Blatt==0) return;
    ZeigeBaum(Blatt->links);            // Marke 1
    cout << Blatt->Inhalt << endl;
    ZeigeBaum(Blatt->rechts);           // Marke 2
}

Man ruft die Funktion am besten mit den ersten Eintrag auf, wenn das Blatt nicht leer sein sollte, ruft sich die Funktion erneut auf nur das es nun das naechste linke Blatt als Parameter hat usw.. Sollte das nächste Blatt irgendwann mal Null sein wird das letzte Ereignis vom stack genommen und das letzte linke Blatt angezeigt und dann mit dem rechten blatt weiter gemacht, da wird wieder zu erst nach dem linken Blatt gefragt uns. Aber wenn man im stack wieder zurueck geht muesste das doch in einer endlosschleife enden da ja nun irgendwann wieder das zuvor schon ausgegebene linke Blatt wieder da ist.

Koennte das evtl. mir noch mal jemand erklren wie des so ablaeuft?

Gruß Tobi.

finix

Die Funktion ruft sich zwar ggf. erneut auf, aber nicht mit dem selben Element. Die Funktionsausführung fängt auch nicht magischerweise von vorne an wenn der Selbstaufruf zurückkehrt bloß weil es sich um eine Rekursion handelt.

(Überleg dir mal wie es aussähe wenn an den Marken eins und zwei foo und bar statt ZeigeBaum aufgerufen würden -- Blatt nicht null; Aufruf foo mit Blatt->links; foo kehrt zurück; Inhalt ausgeben; Aufruf bar mit Blatt->rechts; bar kehrt zurück; ZeigeBaum für diesen tBaum abgehandelt!

Außerdem:

T0bi schrieb:

Man ruft die Funktion am besten mit den ersten Eintrag auf

Das ist so schlicht nicht richtig. Man ruft die Funktion am besten mit dem Baum auf den man gerade betrachten möchte, auch wenn dies wohl tatsächlich oft der erste Eintrag, die "Wurzel" sein wird.

Das ist ja das tolle an rekursiven Datenstrukturen. (Wobei sich das "rekursiv" hier nicht auf die Funktion bezieht, sondern das heißt die Elemente eines Baumes sind Bäume.)

T0bi

ZeigeBaum(Blatt->links);
cout << Blatt->Inhalt << endl;
ZeigeBaum(Blatt->rechts);

die stelle versteh ich trotzdem niht wirklich. fuer mich wuerde die funktion niemals das count geschweige denn den zweiten aufruf von ZeigeBaum erreichen, weil sie sich davor immer wieder neu aufruft...

makkurona

Du übergibst ihr das Erste Blatt.
Davon wird dann das Erste Blatt genommen, das nach links abzweigt und nochmals an de Funktion übergeben...
Dadurch wird die Funktion sozusagen mit einem neuen Stammblatt aufgerufen. Erst wenn das linke blatt 0 Zurückgibt, wird zurückgekehrt und das Rechte durchlaufen, bis auch das Nullzurückgibt.. ist die Linke Seite des Stammblattes abgearbeitet, wird das selbe prozedere nocheinmal mit rechts ausgeführt. Dann kehrt die FUnktion ganz zurück.

Schau dir die FUnktion nochmal genau an.

Bashar

Vielleicht sollte an der Stelle mal gesagt werden dass Blätter diejenigen Knoten sind, die keine Nachfolger haben.

finix

T0bi schrieb:

ZeigeBaum(Blatt->links);
cout << Blatt->Inhalt << endl;
ZeigeBaum(Blatt->rechts);

die stelle versteh ich trotzdem niht wirklich. fuer mich wuerde die funktion niemals das count geschweige denn den zweiten aufruf von ZeigeBaum erreichen, weil sie sich davor immer wieder neu aufruft...

Hast du meinen Post überhaupt gelesen?

makkurona

Ich habe drauf geantwortet.

Wenn Null zurückgegeben wird, wenn also Blatt->Links nicht vorhonden ist, wird zurückgekehrt in die Schleife die aufgerufen hat.

Du hast mich wohl nur missverstanden.

Edit: Kleiner Rechtschreibfehler.

zwutz

nehmen wir mal einen einfachen Baum

A
 B   C
D E F G

A hat die "Blätter" B und C
B hat die Blätter D und E
C hat die Blätter F und G

und jetzt spiel die Funktion mal in Gedanken durch