Inhaltsverzeichnis

1. Rekursion (Einführung)

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:

Was passiert mit den Werten der lokalen Variablen und Parameter beim rekursiven Methodenaufruf?
Bei jedem Aufruf einer Methode reserviert der Computer Speicherplatz für alle Parameter und lokalen Variablen. Wird innerhalb der Methode erneut dieselbe Methode aufgerufen, so wird erneut "neuer" Speicher reserviert, diesmal an einer anderen Stelle. Der "alte" Speicher bleibt erhalten. Bei der Rückkehr mittels "return" wird der "neue" Speicher wieder freigegeben und der "alte" kommt wieder zum Einsatz. Bei jedem Betreten der Methode fakultät erhalten die Parameter und lokalen Variablen daher "neue" Werte, bei jedem Verlassen werden die "alten" Werte wiederhergestellt.

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 orientieren Sie sich 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!

Aufgabe 2: 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 MyMathTools mit einer Methode ggT, die den ggT zweier Zahlen auf die oben beschriebene Art berechnet!

Lösung

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 Turmnummern x und y (aus {1, 2, 3}) 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

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 4: 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:

Tipps:

Es ist empfehlenswert, die rekursive Methode so zu programmieren, dass sie die Turtle vor ihrer Beendigung genau in den Zustand (d.h. Richtung, Position) bringt, in dem sie bei ihrem Aufruf war.
Mit der Methode penUp() können Sie 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!

Weiteres Beispiel (für Interessierte): Quicksort

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 5: 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 6: Berechnung von Binomialkoeffizienten

Im Bild rechts sehen Sie das Pascalsche Dreieck. Die Einträge lassen sich durch folgende Regeln ganz einfach ermitteln:

(i) Der erste und letzte Eintrag jeder Reihe hat den Wert 1.
(ii) Den Wert der Einträge dazwischen erhält man, indem man die Werte der Einträge links und rechts darüber addiert (dargestellt durch die grauen Pfeile).

Ihre Aufgabe ist es, eine rekursive Methode int pascal(int zeile, int spalte) zu erstellen, die einen beliebigen Eintrag der Pyramide berechnen kann.
Wie die Parameter Zeile und Spalte definiert sind, ersehen Sie aus folgender tabellenartiger Struktur: Beispielsweise ergibt pascal(4, 2) den Wert 6.

Erstellen Sie die Methode pascal!

Lösung