Über dieses Experiment
Ein Baum besteht aus einem Stamm, auf dem zwei kleinere Bäume wachsen. Dieser eine Satz ist ein vollständiges Programm: eine Funktion, die einen Ast zeichnet und sich dann zweimal selbst aufruft. Rekursion verwandelt kurze Regeln in ausdrucksstarke Bilder. Beobachte, wie ein Baum, ein Sierpiński-Dreieck und eine Koch-Schneeflocke Aufruf für Aufruf entstehen, verfolge, wie der Aufrufstapel wächst und schrumpft, und zähle, wie schnell die Anzahl der Aufrufe mit zunehmender Tiefe explodiert.
Lernziele
- Den Basisfall und den rekursiven Fall einer rekursiven Funktion bestimmen
- Die Reihenfolge nachvollziehen, in der rekursive Aufrufe ausgeführt werden und zurückkehren
- Erkläre, was der Aufrufstapel enthält und warum seine Tiefe wichtig ist
- Berechne die Anzahl der Aufrufe für eine bestimmte Tiefe, zum Beispiel 2^(n+1) − 1 bei einem Binärbaum
- Beschreibe Selbstähnlichkeit und berechne eine einfache fraktale Dimension
Anleitung
- 1Wähle den Baum mit Tiefe 3 aus und verfolge die Aufrufe langsam. Welcher Ast wird zuerst gezeichnet: der linke oder der rechte? Warum?
- 2Halte an, wenn der Stapel seine größte Tiefe erreicht hat. Wofür steht jeder Stack-Frame? Wie viele Frames gibt es im Vergleich zur Tiefe?
- 3Fülle für den Baum eine Tabelle mit Tiefe und Aufrufen aus. Finde die Regel und überprüfe sie bei Tiefe 10.
- 4Ändere den Astwinkel und das Längenverhältnis. Bei welchen Einstellungen überlappen sich die Äste?
- 5Wechsle zum Sierpinski-Dreieck. Wo befindet sich der Basisfall im Code? Wie viele Dreiecke werden bei Tiefe 5 gezeichnet?
- 6Erstelle die Koch-Schneeflocke mit Tiefe 5. Erkläre mithilfe der angezeigten Werte, wie der Umfang immer weiter wachsen kann, während die Fläche begrenzt bleibt.
Das Modell
Annahmen
- Die Funktionsaufrufe werden nacheinander in Programmreihenfolge und tiefensuchend ausgeführt, genau wie in einer gewöhnlichen Programmiersprache.
- Der Pseudocode übergibt Positionen und Richtungen als Parameter, sodass nach der Rückkehr eines Aufrufs kein Zustand der Turtle wiederhergestellt werden muss.
- Die fraktale Dimension des Baums, log 2 / log(1/r), beschreibt nur die Spitzen, wenn sich die Äste nicht überlappen.
- Die maximale Rekursionstiefe ist begrenzt, damit die schrittweise Wiedergabe schnell bleibt: 12 für den Baum, 7 für das Dreieck und 6 für die Schneeflocke.
Im Unterricht ausprobieren
- Q1Was würde passieren, wenn die Baumfunktion keinen Basisfall hätte?
- Q2Wie viele Aufrufe führt die Sierpinski-Funktion bei Tiefe 4 aus? Erkläre deine Antwort mithilfe einer Summe.
- Q3Warum wird der Aufrufstapel nie tiefer als Rekursionstiefe plus eins, obwohl Tausende von Aufrufen ausgeführt werden?
- Q4Schreibe eine rekursive Funktion, die n! berechnet, und bestimme ihren Basisfall.
- Q5Die Küstenlinie Großbritanniens erscheint umso länger, je kürzer das Lineal ist, mit dem man sie misst. Wie erklärt das Koch-Schneeflockenmodell dieses Phänomen?
Häufig gestellte Fragen
Ist Rekursion langsamer als eine Schleife?
Jeder Aufruf kostet etwas Zeit und Speicherplatz für seinen Stack-Frame, deshalb ist eine Schleife oft geringfügig schneller. Bei verzweigten Strukturen wie Bäumen, verschachtelten Ordnern oder beim Parsen lässt sich Rekursion jedoch viel einfacher schreiben, und jede Rekursion kann mit einem eigenen, expliziten Stack umgeschrieben werden.
Was ist ein Stack Overflow?
Jeder noch nicht abgeschlossene Aufruf belegt einen Frame auf dem Aufruf-Stack. Wenn die Rekursion zu tief geht, zum Beispiel weil der Basisfall nie erreicht wird, geht dem Stack der Speicher aus und das Programm stürzt mit einem Stack-Overflow-Fehler ab.
Wo kommen Fraktale in der Natur vor?
Farne, Romanesco-Brokkoli, Flussnetze, Blitze, Blutgefäße und die verzweigten Atemwege der Lunge sind über mehrere Größenordnungen hinweg annähernd selbstähnlich. Deshalb verwendet man rekursive Regeln, um sie in der Computergrafik zu erzeugen.