1. Rekursion (Einführung)

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 (von lateinisch recurrere == „zurücklaufen“) 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.
Ruft sich die rekursive Methode genau ein Mal auf, so spricht man von linearer Rekursion. Ruft sie sich mehrmals auf, so spricht man von verzweigter Rekursion (siehe Aufgabe 1 unten).

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.

Hier etwas gröber dargestellt:

Aufgabe 1: Die Fibonacci-Folge

Die Fibonacci-Folge ist wie folgt definiert: $$ f_0 = 1 $$ $$ f_1 = 1 $$ $$ f_n = f_{n-2} + f_{n-1}\ \ \mathrm{für}\ \ n > 1 $$ 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 3: 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

Für Interessierte: Quicksort
Stellen Sie sich ein Array mit n Elementen (z.B. Zahlen oder Zeichenketten) vor, das es zu (numerisch bzw. alphabetisch) zu sortieren gilt. Bei zufälliger Verteilung ist Quicksort im Mittel der schnellste Algorithmus für diesen Zweck. Hier ist der Algorithmus erklärt und implementiert.

Aufgabe 4: Floodfill

Gegeben ist eine Pixelgrafik mit einem beliebig geformten, zusammenhängenden Gebiet von Pixeln einer Farbe. Gesucht ist ein Algorithmus, der - ausgehend von einem Pixel dieses Gebietes - alle damit verbundenen Pixel gleicher Farbe rot färbt.

Ein Algorithmus, der dieses Problem löst, ist Floodfill. Er existiert in einer rekursiven Variante, die hier sehr anschaulich erklärt ist.

Gegeben ist das Programmgerüst unten, bei dem bereits dafür gesorgt ist, dass bei Mausklick auf den Punkt (x, y) die Methode fill(x, y, newColor) aufgerufen wird. Ergänzen Sie die Methode fillIntntern so, dass ausgehend vom Punkt (x, y) alle gleichfarbigen, damit verbundenen Punkte in der neuen Farbe eingefärbt werden.

Lösung

Aufgabe 5: größter gemeinsamer Teiler

Sind $a, b \in \mathbb{N}$, so lässt sich der größte gemeinsame Teiler von $a$ und $b$ ("ggT(a, b)") auf folgende Art rekursiv berechnen:
$ ggT(a, b) = $

$a$, falls $a = b$,
$ggT(b, a-b)$, falls $ a > b$ und
$ggT(a, b - a)$, falls $a < b$.

Schreiben Sie eine Klasse MathTools mit einer Methode ggT, die den ggT zweier Zahlen auf die oben beschriebene Art berechnet!

Lösung