verzweigte Rekursion

Pad3 · Hält's aus hier Beiträge: 4

Hallo,

Ich hab auch nach längerer Boardsuche nicht gefunden was ich suche,
und zwar bräuchte ich jemanden, der in der Lage ist mir irgendwie
zu veranschaulichen wie mehrstufige Rekursion funktioniert!
Ich kann die Grundlagen und verstehe auch normale Rekurursion,
aber wenn 2 oder mehrere Aufrufe in vorkommen komm ich net mehr mit!
Mein Problem ist: Ich hab am Mittwoch mündliches Abitur in Info und zu 90%
bekomm ich ne rekursive Funktion / Prozedur und muss dann sagen, bzw.
erklären und nachvollziehen können was dort geschieht!

Als Beispiel:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

procedure Tf_baum.b_preorderClick(Sender: TObject);

          procedure gib_aus_preorder(b:t_baum);
            var teilbaum:t_baum;
                inhalt:t_inhalt;
            begin
                 if not b_leer(b)
                   then begin
                        b_lies(b,inhalt);
                        f_baum.lb_ausgabe.items.add(inhalt);
                        gib_aus_preorder(b_linkertb(b));
                        gib_aus_preorder(b_rechtertb(b));
                        end;
            end;

Hierbei soll eine Baumstruktur ausgegeben werden! Und ich versteh im Grunde was
geschieht, und was am Ende rauskommt aber wenn ich versuche dass Schritt für Schritt
mit Papier und Zettel nachzuvollziehen blick ich net durch!

Wär echt super wenn mir jemand helfen könnte!

Moderiert von raziel: Code- durch Delphi-Tags ersetzt.

alzaimar · Verfasst: So 08.05.05 22:15

Bei Rekursion musst Du für eine Weile deinen Verstand ausschalten und dich DOOF stellen.

Dein Beispiel für eine Baumtraversierung geht doch so (völlig stumpfsinnig, ohne Nachdenken):
Sei B ein Baum (B.L=linker Unterbaum, B.R=rechter Unterbaum, B.Root = Wurzel).

"Besuche alle Knoten in Baum B":
1. Besuche alle Knoten in Baum B.L
2. Besuche alle Knoten in Baum B.R

STOP! Nicht drüber nachdenken, sonst bekommt dein Verstand eine Rekursion, und DAS ist ungesund!

Na, ich will vielleicht den Beweis, das ich auch wirklich alle Knoten abgegrast habe.
Also:
"Besuche alle Knoten in Baum B":
1. Besuche alle Knoten in Baum B.L
2. Ausgabe "Hier ist Knoten" B.Root
3. Besuche alle Knoten in Baum B.R

STOP: Bleib DOOF und befolge nur Befehle (das macht der PC doch auch...)

Wir nehmen uns also einen Baum:
((2)-3-(4))-5-((6)-7-(8))
5 ist die Wurzel, links hängt die 3 unter ihr 2 und 4.
rechts von der 5 hängt die 7, unter ihr 6 und 8.

Besuche alle knoten im Baum ((2)-3-(4)) -5- ((6)-7-(8))
1. Besuche alle Knoten im Baum (2) -3- (4)
1.1 Besuche alle Knoten im Baum (2)
1.1.1 Besuche alle Knoten im Baum () fällt aus wegen is nich.
1.1.2 Ausgabe "Hier ist Knoten " 2
1.1.3 Besuche alle Knoten im Baum () fällt aus wegen is nich.
---- Eine Ebene zurück ---
1.2 Ausgabe "Hier ist Knoten" 3
1.3 Besuche alle Knoten im Baum (4)
1.3.1 Besuche alle Knoten im Baum () fällt aus wegen is nich.
1.3.2 Ausgabe "Hier ist Knoten " 4
1.3.3 Besuche alle Knoten im Baum () fällt aus wegen is nich.
---- Eine Ebene zurück ---
---- Eine Ebene zurück ---
2. Ausgabe "Hier ist Knoten" 4
3. Besuche alle Knoten im Baum (6) -7- (8)
3.1 Besuche alle Knoten im Baum (6)
3.1.1 Besuche alle Knoten im Baum () fällt aus wegen is nich.
3.1.2 Ausgabe "Hier ist Knoten " 6
3.1.3 Besuche alle Knoten im Baum () fällt aus wegen is nich.
---- Eine Ebene zurück ---
3.2 Ausgabe "Hier ist Knoten" 7
3.3 Besuche alle Knoten im Baum (8)
3.3.1 Besuche alle Knoten im Baum () fällt aus wegen is nich.
3.3.2 Ausgabe "Hier ist Knoten " 8
3.3.3 Besuche alle Knoten im Baum () fällt aus wegen is nich.
---- Eine Ebene zurück ---
---- Eine Ebene zurück ---
---- Eine Ebene zurück ---

Wow! Fertig! Wie haben wir das gemacht? In dem wir ausnahmsweise bei der Lösung *nicht* nachgedacht haben. Wir haben die Lösung kurz und knapp rekursiv definiert. So wie der Chef, der sagt:"Ich habe Recht, weil ich Recht habe". Und der ist auch DOOF.

Bei der Erklärung sind wir dann engstirnig vorgegangen.

Bei mir hat es mit der Rekursion einige Zeit gedauert, bis es -Plink- machte und ich es gefressen habe. Da mir DOOF sein nicht schwer fällt, komm ich damit ganz gut zurecht. Und man muss seine (iterativen!) Gedanken mal kurz ausschalten, damit man das kapiert. Rekursion ist sozusagen gegen die Natur, weil wir uns sagen, das man etwas nicht über sich selbst definieren kann.

Hilft Dir das?

Check mal die Towers of Hanoi in ...
www.delphi-forum.de/....php?p=249822#249822

Pad3 · Hält's aus hier Beiträge: 4

Jo, ich verstehs auf jeden Fall schonmal mehr als vorher! Bin jetzt allerdings was müde, und werd mir morgen nochma genauer Gedanken drüber machen!

Aber auf jeden Fall schonmal vielen herzlichen Dank für die mehr als ausführliche Antwort!

Pad3 · Hält's aus hier Beiträge: 4

So, also ich bin das alles nochmal durchgegangen!
Fazit: Deine Schreibweise hat mir tierisch geholfen!
Und ich hab jetzt schon mehrere DIN A4 Blätter vollgekritzelt mit irgendwelchen Bäumen
die ich durchgegangen bin und ES KLAPPT!!!! Ich habs raus!!!
Echt ein Glücksgefühl! Na ja, wie auch immer! Mir is aufgefallen,
dass dir aber ein Fehler unterlaufen ist!

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

procedure Tf_baum.b_inorderClick(Sender: TObject);

          procedure gib_aus_inorder(b:t_baum);
            var teilbaum:t_baum;
                inhalt:t_inhalt;
            begin
                 if not b_leer(b)
                   then begin
                        gib_aus_inorder(b_ltb(b));
                        b_lies(b,inhalt);
                        f_baum.lb_ausgabe.items.add(inhalt);
                        gib_aus_inorder(b_rtb(b));
                        end;
            end;

Das Wäre die Ausgabe Prozedur die du verwendet hast!
Aber ich denke das hast du nur falsch gelesen!
Mir hats auf jeden Fall geholfen!

VIELEN DANK!!!

Moderiert von raziel: Code- durch Delphi-Tags ersetzt.

alzaimar · Verfasst: Mo 09.05.05 19:30

Es freut mich, dass Du Rekursion kapiert hast. Ist so wie Fahrrad fahren, wenn man es erstmal drauf hat, vergisst man es nicht mehr. Und: Es wird dir helfen, elegante Programme zu schreiben.

Bei der implementierung der Rekursion ist natürlich immer zu beachten, das die irgendwann terminiert: Hier also: 'If Not Baum_Leer'. Das ist ein fundamentaler Aspekt! Gut beobachtet!

Und viel Glück!

Pad3 · Hält's aus hier Beiträge: 4

JUHUUUU!!!

Danke euch hab ich ne glatte 1 (14 punkte) in der Prüfung!!!
Es kam verzweigte Rekursion dran, und ich habs richtig verstanden!!

DANKE DANKE DANKE DANKE DANKE!!!!

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme