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^n 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 wir die vier vorherstehenden Elemente/Dreiecke ebenfalls schon gebildet haben. 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 wir 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_n steht.

Die Formel lautet a_n = 2n-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 dazu z.B. Iteration - also Wiederholung - statt der 'expliziten Definition'.

Erster Versuch: Von Iteration zu Rekursion

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

Wir beginnen mit der Iteration, die Sie schon kennen.

Sollten Sie noch kein gleichseitiges Dreieck in Ihrer toolbox haben, speichern Sie vorher ein solches noch ab:

Schreiben Sie nun die untenstehende Funktion für ein Sirpinski-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 Sirpinski für eine gewisse Iterationstiefe erstellen können. Spielen Sie danach mit verschiedenen Iterationstiefen. WICHTIG: Beachten Sie, dass die Grösse immer die Gesamtgrösse der Figur sein soll, nicht die Grösse eines einzelnen Dreiecks.

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.

Da es hier auf der Seite deshalb zu Problemen kommt, löschen Sie bitte den vollständigen Print-Befehl und führen Sie die Zelle erneut aus, so dass keine Fehlermeldung mehr kommt.

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 das Z an 1. Stelle und nicht zu hinterst steht.

Wenn Sie das verstanden haben, können wir zurück zum Sirpinski-Dreieck. 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_sirpinski(tiefe: int, groesse: float, farbe: Color):
    if a ist erstes Element:
        return gleichseitiges_dreieck(groesse, farbe)
    else:              
        return pseudo-sirpinski(um_eins_geringere_tiefe, halbe_groesse, farbe) über 
                pseudo-sirpinski(um_eins_geringere_tiefe, halbe_groesse, farbe) neben 
                pseudo-sirpinski(um_eins_geringere_tiefe, halbe_groesse, farbe)

Schreiben Sie nun unten diesen Code in PyTamaro:

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.