1. Rekursion

Beispiel 1: Berechnung von Fakultäten

Erinnern Sie sich noch an die Fakultätsfunktion? Sie ist so definiert: $$0! = 1$$ und $$n! = 1\cdot 2\cdot 3\cdot \ldots \cdot (n-1)\cdot n \ \mathrm{für}\ n \in \mathbb{N} \backslash \{0\},$$ also beispielsweise: $$5! = 1\cdot 2\cdot 3\cdot 4 \cdot 5 = 120$$

Probieren Sie das folgende Programm aus, auch im Einzelschrittmodus.
Analysieren Sie das Programm genau und überlegen Sie, welche Anweisungen der Reihe nach ausgeführt werden.

Definition:
Von Rekursion spricht man, wenn sich eine Methode entweder direkt selbst aufruft oder über eine Aufrufkette (z.B. Methode a ruft Methode b auf, die ruft Methode c auf, diese wiederum ruft Methode a auf).

Wichtig: Jede Rekursion benötigt eine Abbruchbedingung, die das Unterbrechen der Aufrufkette nach endlich vielen Schritten sicherstellt.

Erklärung des Programmablaufs:

Um zu verstehen, wieso ein rekursiver Aufruf einer Methode überhaupt funktionieren kann stellen Sie sich am besten vor, dass der Computer bei jedem Aufruf der Methode fakultät die Werte aller Parameter und lokalen Variablen "speichert" und bei jeder Rückkehr wiederherstellt. Bei jedem Betreten der Methode fakultät erhalten die Parameter und lokalen Variablen daher "neue" Werte.

TODO <Erklärung des Stacks für Interessierte>

Hier etwas gröber dargestellt:

Aufgabe 1: Die Fibonacci-Folge

Die Fibonacci-Folge ist wie folgt definiert: $$ f_1 = 1 $$ $$ f_2 = 1 $$ $$ f_n = f_{n-2} + f_{n-1}\ \ \mathrm{für}\ \ n > 2 $$ Jedes Folgenglied ist also die Summe der beiden vorhergehenden Folgenglieder. Hier die ersten Glieder: $$1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ \ldots$$

Programmieren Sie eine Methode, die das n-te Glied der Fibonacci-Folge berechnet. Nutzen Sie dazu rekursive Methodenaufrufe und orientiere Dich am vorherigen Programm (Fakultätsberechnung).
Welchen wesentlichen Unterschied zum vorherigen Programm bemerken Sie? Wie wirkt er sich auf die obigen Diagramme zur Erklärung aus?

Musterlösung -> Bitte erst nach der Informatikstunde ansehen!

Beispiel 2: Die Kochkurve

Die Kochkurve und die aus ihr gewonnene Kochsche Schneeflocke werden in diesem Wikipedia-Artikel schön beschrieben. Die Kochkurve ergibt sich, indem man von einer waagrechten Strecke ausgeht und bei jedem Iterationsschritt jede Strecke folgendermaßen ersetzt: Die Kochsche Schneeflocke erhält man, wenn man von einem gleichseitigen Dreieck ausgehend dieselbe Iterationsvorschrift immer wieder anwendet.

Aufgabe 2: Fraktaler Baum

Erstelle mit Hilfe rekursiver Methodenaufrufe ein Programm, das einen fraktalen Baum zeichnet. Hier die Zeichnung nach der 12. Iteration:

Die Zeichnung beginnt mit einer vertikalen Linie und folgt folgender Iterationsvorschrift:

Tipp:
Mit der Methode penUp() kannst Du den Stift der Turtle anheben, so dass sie nicht mehr zeichnet. Mit der Methode penDown() kannst Du ihn wieder herabsenken, so dass die Turtle wieder zeichnet.

Lösung

Für Interessierte:

Neben der Kochkurve und fraktalen Bäumen gibt es viele weitere schöne fraktale Punktmengen, die mit wenig Aufwand durch einfach rekursive Methoden gezeichnet werden können:

Lassen Sie sich herausfordern!

Aufgabe 3: Die Türme von Hanoi

Das Problem der Türme von Hanoi wird in diesem Video gut erklärt:

Kurzgefasst:
Vor Ihnen befinden sich drei Stäbe ("Türme"), wobei sich auf dem rechten der drei Stäbe n der Größe nach geordnete Scheiben befinden, die größte zuunterst. Die Aufgabe besteht darin, alle n Scheiben zum linken Stab zu bringen, wobei folgende Spielregeln gelten:

Bei jedem Schritt darf nur eine Scheibe bewegt werden.
Es darf nie zu einer Situation kommen, bei der auf einem der drei Stäbe eine größere Scheibe oberhalb einer kleinen zu liegen kommt.

Aufgabe 5: Die Türme von Hanoi
Die drei Türme bekommen die Nummern 1, 2 und 3.

Schreibe eine Klasse Hanoi mit einer Methode erkläreLösung(int startTurmNummer, int zielTurmNummer, int n), die in Textform erklärt, wie man n Scheiben unter Einhaltung der im Video erklärten Regeln vom Turm startTurmNummer zum Turm zielTurmNummer bringt.

Die Ausgabe von erkläreLösung(1, 3, 4) soll beispielsweise so aussehen:

Bewege eine Scheibe von Turm 1 zu Turm 2
Bewege eine Scheibe von Turm 1 zu Turm 3
Bewege eine Scheibe von Turm 2 zu Turm 3
Bewege eine Scheibe von Turm 1 zu Turm 2
Bewege eine Scheibe von Turm 3 zu Turm 1
Bewege eine Scheibe von Turm 3 zu Turm 2
Bewege eine Scheibe von Turm 1 zu Turm 2
Bewege eine Scheibe von Turm 1 zu Turm 3
Bewege eine Scheibe von Turm 2 zu Turm 3
Bewege eine Scheibe von Turm 2 zu Turm 1
Bewege eine Scheibe von Turm 3 zu Turm 1
Bewege eine Scheibe von Turm 2 zu Turm 3
Bewege eine Scheibe von Turm 1 zu Turm 2
Bewege eine Scheibe von Turm 1 zu Turm 3
Bewege eine Scheibe von Turm 2 zu Turm 3

Lösungsidee/Tipps:

Bei gegebenen Türmen x und y hat der übrige Turm dann immer die Nummer 6 - x - y
Um n Scheiben von Turm x zu Turm y zu bewegen, bewege zuerst n - 1 Scheiben von Turm x zu Turm 6 - x - y, dann eine (die größte!) Scheibe von Turm x zur Turm y und dann n - 1 Scheiben von Turm 6 - x - y zu Turm y. Die Methode erkläreLösung muss sich also nur geeignet selbst aufrufen.

Lösung