In diesem Curriculum lernen Sie, was Rekursion ist, wann es sie braucht und warum man mit Iteration schnell an gewisse Grenzen stösst.

Einführungsüberlegungen

Die folgende Grafik entsteht von links nach rechts durch immer die gleiche Vorschrift.

Welche Beschreibung passt am besten zu der von Ihnen formulierten Vorschrift?

1. Man nimmt bei einem gleichseitigen Dreieck die Mitte heraus.
2. Man teilt das Dreieck in vier gleichgrosse Dreiecke und entfernt das mittlere.
3. Jede ausgefüllte Dreiecksfäche wird in vier gleich grosse Dreiecke unterteilt und jeweils die zentral gelegene wird entfernt.
4. Aus gleichseitigen, nach oben zulaufenden Dreiecken wird ein dreieckiger Turm gebaut, wobei die Basis aus jeweils 2ⁿ nebeneinander stehenden Dreiecken besteht (n ist die Platznummer, des anzuschauenden Dreiecks). In der zweiten, darüber liegenden Zeile - sofern es sie gibt -, wird zwischen dem 1. und dem 2. Basisdreick begonnen wird und jedes zweite Dreieck wird weggelassen. In der dritten, wiederum darüberliegenden Zeile - sofern es sie gibt -, ... und jetzt wird es langsam kompliziert... ich gebe auf und klicke mal diesen Button...
5. Drei Dreiecke, die aussehen wie das ganze auf dem vorherigen Platz, werden mit der Spitze nach oben übereinander gestapelt: zwei unten, eins oben. Auf dem ersten Platz der Dreiecksfolge steht ein gleichseitiges, einfarbiges Dreieck mit Spitze nach oben.

Viele von Ihnen werden etwas zwischen 3. und 4. geschrieben haben, nachdem Sie gemerkt haben, dass die 1. und 2. Vorschrift nur gerade für einen Schritt ausreicht. Ein paar wenige haben vielleicht etwas Ähnliches wie die 5. Vorschrift. Falls nicht, kein Weltuntergang! Sie werden lernen, solche Vorschriften zu schreiben.

Wir schauen uns diese Vorschrift einmal genauer an:

(Wer Folgen in der Mathematik schon behandelt hat, kennt zwar die Begriffe, sollte diesen Abschnitt aber nicht überspringen)

Die Vorschrift ist zweiteilig: Der erste Teil bezieht sich allgemein darauf, wie ein neues Element aus demjenigen erstellt wird, das als letztes erstellt wurde, ohne zu sagen, wie das vorherige aussieht oder entstand. Der zweite Teil beschreibt das 1. Element der Dreiecksfolge. So kann man der Reihe nach vom ersten Element ausgehend alle Elemente mit der gleichen Vorschrift bis ins Unendliche erstellen.

Diese Art, eine Folge von Elementen zu beschreiben, bedeutet aber, dass z.B. das 5. Element der Dreiecksfolge nur entstehen kann, wenn die vier vorherstehenden Elemente/Dreiecke ebenfalls schon gebildet wurden. Es gibt keine Möglichkeit, direkt das 5. Element zu bilden.

Eine solche Vorschrift heisst in der Mathematik eine rekursiv definierte Folge. Im Gegensatz dazu gibt es die explizit definierte Folge, die es eben erlaubt, das 5. Element zu berechnen, ohne die ersten vier zu kennen.

Betrachten Sie die Folge: 1, 3, 5, 7, 9, 11, ...

Rekursiv definiert kann man sagen, dass sie durch addieren von 2 zum vorherigen Element entsteht und dass das erste Element 1 ist.

Sie explizit zu definieren, ist allerdings auch nicht schwer. Dazu muss man aber wissen, an welcher Stelle n in der Folge (an welcher Platznummer) das zu berechnende Element aₙ steht.

Die Formel lautet aₙ = 2⋅n-1. Also das Element an der Stelle n wird berechnet, indem man die Platznummer n mit zwei multipliziert und 1 abzieht. Überprüfen Sie das kurz, sollten Sie nicht selbst auf die Formel gekommen sein.

Wenn beim Programmieren von Rekursion gesprochen wird, hat das zwar sehr viel Ähnlichkeit mit der mathematischen Definition von oben und gleichzeitig ist es doch ganz anders. Beim Programmieren ist der Gegensatz zur Rekursion z.B. Iteration - also Wiederholung - statt der expliziten Definition.

Erster Versuch: Von Iteration zu Rekursion

Das Sierpinski-Dreieck kann sowohl iterativ als auch rekursiv definiert werden.

Beginnen Sie mit der Iteration, die Sie schon kennen.

Schreiben Sie nun die untenstehende Funktion für ein Sierpinski-Dreieck, das die Iterationstiefe, die Grösse und eine Farbe erwartet, fertig. Beginnen Sie damit, dass Sie sich überlegen, was in der Variable result stehen muss, so dass Sie innerhalb der for-Schleife anschliessend aus dem immer wieder neu zu speichernden result das Sierpinski für eine gewisse Iterationstiefe erstellen können. Spielen Sie danach mit verschiedenen Iterationstiefen.

WICHTIG: Beachten Sie, dass die Grösse in diesem Curriculum immer die Gesamtgrösse der Figur sein soll, nicht die Grösse eines einzelnen Teilstücks - in diesem Fall Dreieck.

Wenn man diese Iteration genau betrachtet, fällt auf, dass man auf gewisse Weise auch auf das vorherige Element der Folge zugreift, man überschreibt es nur fast augenblicklich mit dem nächsten Element und kommt so zur n-ten Iteration.

Rekursion tut das nicht. Rekursion speichert die ersten n-1 Elemente nicht. Rekursion läuft quasi vom letzten Element (Unendlichkeit widerspräche der Definition eines Algorithmus, wie Sie aus der 2. Klasse wissen) her durch bis zum ersten Element und legt unterwegs Leerstellen aus, die sie auf dem Rückweg mit Inhalt füllt.

Eine Rekursion taucht also quasi vom letzten Element her bis zum Grund, wo sie das erste Element findet, und arbeitet sich von dort aus 'hoch', bis sie wieder beim letzten Element ist.

Dies tut sie, indem sie zwei Codeblöcke hat, die durch eine Verzweigung getrennt sind. Der eine Codeblock besteht aus dem Erstellen der Leerstellen, und der andere aus einer sogenannten Abbruchbedingung - also dem ersten Element der Folge. Das Erstellen der Leerstellen erfolgt durch einen Selbstaufruf.

Innehrhalb des Codeblocks, der eine Funktion definiert, wird die Funktion verwendet, wie wenn es sie vorher schon gegeben hätte, z.B. so:

Sie kriegen eine Fehlermeldung, dass die maximale Rekursionstiefe erreicht ist. Das ist der Compiler, der den Computer davor schützt, in eine Endlosschleife zu fallen. Die Funktion hat keine Bedingung, die ihr sagt, ob und dass das erste Element erreicht ist.

Die Abbruchbedingung ist also notwendig, damit die Funktion nicht unendlich sich selbst verarbeitet.

Die Funktion selbstaufruf() muss also auf jeden Fall eine Abbruchbedingung bekommen. Dies könnte man z.B. mit einem Parameter machen, der mit jedem Selbstaufruf kleiner wird. zum Beispiel so:

Probieren Sie es aus:

Stimmt es mit Ihrer Vermutung überein? Falls nicht, denken Sie nochmals genau darüber nach. Es ist wichtig, dass Sie verstehen, warum z an der ersten Stelle und nicht am Ende steht.

Wenn Sie das verstanden haben, kehren Sie zum Sierpinski-Dreieck zurück. Schauen Sie sich dieses nochmals an - oben rechts als gleichgrosse Folge, oder unten mit unterschiedlicher Grösse - und versuchen Sie, schon über Abbruchbedingung und Selbstaufruf nachzudenken.

Überarbeiten wir den obigen Code, nach diesen Überlegungen:

def pseudo_sierpinski(tiefe: int, groesse: float, farbe: Color):
    if a ist erstes Element:
        return gleichseitiges_dreieck(groesse, farbe)
    else:  
        return pseudo-sierpinski(um_eins_geringere_tiefe, halbe_groesse, farbe) über
               pseudo-sierpinski(um_eins_geringere_tiefe, halbe_groesse, farbe) neben
               pseudo-sierpinski(um_eins_geringere_tiefe, halbe_groesse, farbe)

Schreiben Sie nun unten diesen Code in PyTamaro:

Diese Animation zeigt Schritt für Schritt, wie die Leerstellen für das Sierpinski-Dreieck ausgelegt werden, vergleichen Sie sie mit Ihren vorherigen Gedanken:

Was Sie gelernt haben

Sie können nun Iteration von Rekursion unterscheiden und haben erste Schritte mit Rekursion unternommen.

Sie haben verstanden, dass ...

• Wiederholung sowohl mit Iteration als auch mit Rekursion erreicht wird.
• mathematische Rekursion als Gedankenbrücke für das Verständnis der Rekursion im Programmieren herhalten kann, sich aber deutlich davon unterscheidet.
• Iteration nicht bedeutet, dass man direkt zu einem bestimmten Element der Folge kommt, dass aber Iteration ein linearer Prozess, eine Abfolge beschreibt, während Rekursion mit zurücktauchen beschrieben werden könnte.
• Rekursion immer zweigeteilt ist: Abbruchbedingung und Codeblock mit Selbstaufruf.
• Dass der Selbstaufruf einem Erstellen von Leerstellen gleichkommt, die auf dem Rückweg mit Inhalt gefüllt werden.
• mit Rekursion Probleme gelöst werden können, die mit Iteration nur schwer gelöst werden können.