rekursive Bäume

Material für den Informatikunterricht

Von Bäumen und Baumkuchen

"Also die Sache mit der Rekursion musst du mir nochmal erklären", sagt Emil, der sich mit Paula im Café neben dem Grafikstudio "proz" getroffen hat.
"Kein Problem", erwidert Paula, "wenn du's kapierst, dann zahlst du, ja?"
Emil kriegt glänzende Augen: "Mindestens!"
"Na ja", dämpft Paula ab, schiebt ihren Kakao beiseite und zeichnet dies auf einen Bierdeckel:

"Was siehst du hier?" fragt sie.
Emil verzieht das Gesicht, nimmt einen großen Schluck Cappuccino und antwortet: "Also, ich würd's als ein irgendwie entartetes Ypsilon ansehen, oder als Mistgabel für Fortgeschrittene oder so, oder als ..."
"Falsch", fährt Paula dazwischen, "das ist die Ausführung einer rekursiven Prozedur! Es ist ein rekursiver Baum."
Emil runzelt die Stirn. "Also bis jetzt zahle ich noch keinen Pfennig."
Paula lässt sich nicht beirren: "Gut, es ist ein rekursiver Baum in Primitivform. Denn was ist ein Baum anderes als ein Stamm mit Astansätzen, an denen sich der Baum dann in immer kleineren Ausgaben wiederholt?"
"Ich zahl' immer noch nicht", anwortet Emil.
Paula nimmt nun auch einen ordentlichen Schluck von ihrem heißen Kakao, holt ihren kleinen Kalender aus der Handtasche, reißt ein Blatt heraus, seufzt und schreibt hin:

"Die LOGO-Befehle kennst du?"
"Geschenkt, Paula, das ist es nicht", winkt Emil ab.
"Natürlich nicht, man muss schon kapieren, was die Befehle in dieser Prozedur so alles anstellen. Du wirst dich wundern", sagt Paula. "Was diese Prozedur macht, ist folgendes - aber stop. Vorher noch ein Fachbegriff: 'Inkarnation', so heißt eine Version oder Variante der Prozedur mit einem bestimmten Wert der Parameter. Die Parameter können ja verschiedene Werte annehmen. Und jede Ausgabe der Prozedur baum mit einem neuen Wert des Parameters länge ist so eine neue Inkarnationen der Prozedur baum ."
Emil verzieht das Gesicht: "Also ich hab Latein im Leistungskurs gehabt. Und incarnatio müsste sowas Ähnliches wie Fleischwerdung oder so heißen. Igitt."
"Lenk' nicht ab", meint Paula nur.
Emil atmet tief durch und hat eine Idee: "Also gibt es von dieser Prozedur hier 2 oder 3 Inkarnationen, denn die Prozedur heißt baum , und baum wird in dieser Prozedur noch zweimal aufgerufen: Zeile 4 und 6!"
"Falsch, wart's ab!" Paula wird nun doch etwas energisch. "Hör' jetzt einfach mal ein paar Minuten zu, du Maustreiber! Also wir geben ein: baum 100.

Es beginnt die 1. Inkarnation. 1. Zeile: Weil länge größer als 20 ist, geht es weiter mit der 2. und 3. Zeile: VW 100 und LI 45 . Dann beginnt in Zeile 4 die

2. Inkarnation. Es wird also wieder die Prozedur baum aufgerufen, jetzt allerdings mit länge/2 = 50. Die Bedingung der 1. Zeile gilt immer noch nicht, also VW 50 LI 45, siehe Zeilen 2 und 3. Und auch diese Inkarnation stößt auf die Zeile 4; es beginnt also die

3. Inkarnation, sie verläuft wie die zweite, allerdings mit halber Länge der vorgegebenen Länge, also VW 25 LI 45. Dann steht eigentlich in der 4. Zeile der Aufruf einer weiteren Inkarnation an. Diese hätte dann in ihrem Parameter länge den halben Wert der 3. Inkarnation, das wäre 12,5. Da sorgt endlich die Bedingung, die in der 1. Zeile steht, für Schluss. RK heißt Rückkehr und bedeutet, dass eine weitere Inkarnation hier nicht erfolgt. Deshalb ist aber insgesamt noch lange nicht Schluss! Sondern der Rest der 3. Inkarnation steht ja noch da: Zeile 5: RE 90 und Zeile 6. Auch die hier fällige weitere Inkarnation findet nicht statt, weil sie gleich in der 1. Zeile wieder auf die Abbruchbedingung stößt. Weil sie wahr ist, es wäre nämlich die neue länge = 12,5, erfolgt die Rückkehr in die vorige, hier in die 3. Inkarnation. Die hat noch die beiden letzten Zeilen abzuarbeiten: LI 45 RW 25. Ende der 3. Inkarnation. Aber die 2. Inkarnation war ja noch nicht fertig. Also

Fortsetzung der 2. Inkarnation: Es geht in Zeile 5 weiter. Hier dreht der Igel um 90° nach rechts, aber nicht am Stamm, sondern hier oben in der linken Astgabel. Dann kommt diese 2. Inkarnation an die 6. Zeile mit einem weiteren Aufruf der Prozedur und ihrer halbe Länge. Das gibt die

4. Inkarnation. länge jetzt = 50/2, denn die 3. Inkarnation war ja fertig und der mitgeschleppte Wert der Variablen länge ist von der 2. Inkarnation her noch 50. Es geht als 25 Schritte vorwärts, dann nach links. Und was mit dem Aufruf einer weiteren Inkarnation in Zeile 4 passiert, weißt du ja. Also folgt nach LI 45 aus Zeile 3 und danach RE 90, eine weitere Inkarnation findet aus bekannten Gründen wieder nicht statt, und die 4. Inkarnation geht mit LI 45 RW zu Ende. Dabei ist der Wert von länge hier in der 4. Inkarnation bekanntlich = 25. Das heißt, diese Inkarnation hat einen Strich gemacht: hier oben. Ende der 4. Inkarnation. Und

Fortsetzung der 2. Inkarnation. Die war ja bis zu ihrer 6. Zeile gekommen. Sie dreht sich jetzt wieder in Ausgangsrichtung (Zeile 7), und der Igel läuft rückwärts. Und zwar die Länge dieser 2. Inkarnation, also länge = 50. Ende der 2. Inkarnation. Es geht weiter mit der

Fortsetzung der 1. Inkarnation. Die war bis zur 3. und 4. Zeile gekommen. Das ist in der Zeichnung der Astansatz am Stamm-Ende. Also jetzt Zeile 5: RE 90 , insgesamt von der Senkrechten aus also 45 Grad nach rechts. Es beginnt die rechte Hälfte der Äste unseres Bäumchens. Und zwar kommt als nächstes die Zeile 6 dran. Es beginnt die

5. Inkarnation. Die Abbruchbedingung in der 1. Zeile ist in diesem Fall ungültig, denn die 5. Inkarnation hat die halbe Länge der bisherigen Inkarnation, das war 100, also jetzt VW 50 LI 45. Und weiter geht's mit einer weiteren Verzweigung in der

6. Inkarnation. Auch hier macht die Abbruchbedingung nichts, denn es gilt länge = 25. Die 6. Inkarnation kommt nach einer Linksdrehung auf die Zeile 4. Eine hier fällige weiter Inkarnation wird nicht ausgeführt, denn diese hätte den Parameter-Wert 12,5. Also weiter mit Zeile 5: Rechtsdrehung. Für die 6. Zeile gilt dasselbe wie für die 4. Zeile: Wegen der Rückkehr-Definition länge < 20 spielt sich nichts Neues ab, die 6. Inkarnation geht zu Ende mit LI 45 RW 25 . Ende der 6. Inkarnation.

Aber die 5. Inkarnation war noch nicht zu Ende, sondern bis zu ihrer Zeile 3 und 4 gekommen. Also Fortsetzung der 5. Inkarnation, Zeile 5 und 6. Dann Aufruf einer weiteren Inkarnation, nämlich der

7. Inkarnation. Sie hat den Parameter-Wert länge = 25, macht damit einen Schritt vorwärts, dreht nach links, eröffnet keine weitere Inkarnation (wieso wohl?), dreht nach rechts, macht aus demselben Grund wie gerade wieder keine weitere Inkarnation auf, dreht nach links und geht ihre Länge rückwärts. Das war dieser Ast hier ganz rechts. Ende der 7. Inkarnation. Nun wird noch der

Rest der 5. Inkarnation abgespult. Sie war ja bis zu ihrer Zeile 5 und 6 gekommen. Jetzt also schnell Zeile 7 und 8: LI 45 bedeutet, dass sich der Igel wieder in die Startrichtung dieser 5. Inkarnation ausrichtet, dann rückwärts mit der hauseigenen Länge, das war 50. Ende der 5. Inkarnation. Es geht zu Ende mit dem

Rest der 1. Inkarnation. Die war bis zur Zeile 5 und 6 gekommen, jetzt dreht der Igel 45 Grad nach links, damit steht er senkrecht - Und dann geht's rückwärts. Und zwar die Länge, die eben für diese 1. Inkarnation gilt, also RW 100. Ende der 1. Inkarnation."

"Also Paula, deinen Kakao hast du dir noch nicht verdient!", protestiert Emil. "Mag ja sein, dass aus acht Prozedurzeilen so ein wildes Inkarnations-Wesen folgt. Aber bitte: erklär mit das ganze Zeug doch mal in einem Satz, dann leg ich noch was drauf. Bitte", fragt er eine vorbeilaufende Kellnerin, "haben Sie, äh, Baumkuchen?"
Sie hat.
"Ich erklär's dir in zwei Sätzen, okay? Und ich benutze keinmal das Wort 'Inkarnation'", lächelt Paula und lehnt sich zurück.
"Also zweimal Baumkuchen, bitte", bestellt Emil.
Paula fährt sich durch's Haar, atmet tief durch und sagt: "Dieser Baum besteht aus einem Stamm, der sich nach links und rechts verzweigt, dann geht es wieder an den Ausgangspunkt zurück. Jede Verzweigung besteht auch wieder aus dem Baum in halber Größe."
Emil schluckt. "Und wo bleiben da die Äste?"
"Jede Verzweigung besteht auch wieder aus dem Baum in halber Größe."
"Und die ganz kleinen Äste?"
Paula betont denselben Satz anders: "Jede Verzweigung besteht auch wieder aus dem Baum in halber Größe."
Emil ist hartnäckig: "Und wieso verirrt sich die ganze Prozedur nicht in einem Wust von Winkeln und verschiedenen Werten für länge?"
Paula beugt sich vor und schaut Emil tief in die Augen: "Dieser Baum besteht aus einem Stamm, der sich nach links und rechts verzweigt, dann geht es wieder an den Ausgangspunkt zurück, Emil, du Rechtsklicker vom Dienst! Jeder Stamm, Ast und Zweig hat seinen eigenen Ausgangspunkt. Was ist jetzt mit dem Kuchen und meinem Kakao?"

"Testfrage", sagt Emil mit Denkerfalten auf seiner Stirn, "ist es so: Ich schreibe eine Baumprozedur mit VW :länge LI 45 RE 90 wieder LI 45 und zurück mit RW :länge. Das ist dann ein Stamm mit Ast-Ansätzen. Dann hänge ich bei den Ast-Ansätzen links und rechts ebenfalls den Aufruf der Baumprozedur 'rein, aber mit kürzerer Länge. Das ist schon die ganze rekursive Prozedur. Richtig?"
"Fast", sagt Paula. "Du musst zu Beginn der Prozedur klarstellen, wann Schluss sein soll: die Abbruchbedingung."
"Paula, das mein' ich doch", meint Emil.
"Logo", antwortet Paula mit vollem Mund.

Aber Emil ist schon ganz woanders: "Dann ist eine Prozedur für einen Baum mit jeweils drei Verzweigungen ja nicht viel komplizierter! Man müsste statt der 5. Zeile, wo es nach rechts geht, nur den Igel geradeaus stellen und noch einen weiteren Aufruf von baum einbauen?" Emil kommt in Fahrt: "Und was passiert, wenn ich auf diese Weise eine Prozedur für einen Baum mit 4 oder 8 Verzweigungen schreibe und dann zeichnen lasse?"
"Probier's doch aus", mampft Paula.

Übung: rekursive Bäume

Betrachte noch einmal Paulas Ausführungen am Schachtelmodell rechts: Jede Schachtel ist eine Inkarnation. Was fällt dir auf, wenn du alle Igelbewegungen aus der gesamten Grafik von oben nach unten notierst und ausführen lässt?
Versuche, Prozeduren für einen Baum mit 3 und 4 Verzweigungen zu schreiben. Nimm dazu die Ausgangs-Prozedur und verändere sie so, wie Emil es plant ("Man müsste statt der 5. Zeile ...")!
Was sagst du zu Emils letzter Frage?
Kann man an den Prozeduren erkennen, dass die Graphik der "Baumkrone" von links nach rechts aufgebaut wird?
Wie lautet die Prozedur, wenn die "Baumkrone" von rechts nach links aufgebaut wird?
Zu Paulas Vortrag: Zeige an der Graphik , wo der Igel am Ende der 4. Inkarnation steht.
Wenn die Prozedur mit der Länge 100 eingegeben wird, ergeben sich 7 Inkarnationen, wie Paula erklärt. Das sieht man auch an der dazu passenden Graphik. Wieso?
Wozu dient die letzte Zeile der Prozedur? Ist es nicht egal, wo der Igel am Schluss steht?
Wie kannst du erreichen, dass eine Prozedur noch kleinere Verästelungen produziert?
Formuliere einen Parameter so, dass du bereits beim Aufruf der Prozedur die Feinheit der Verästelung bestimmen kannst.
Schau dir noch einmal deine Prozedur für 3 oder 4 Verästelungen an: Wofür sorgen die beiden Befehle LI 45 RW :l?
Wie und warum ist es möglich, asymmetrische Bäume zu produzieren?