Rekursion
Eine Methode darf sich selbst aufrufen. Das klingt nach einem Trick oder nach einem Fehler – es ist aber eine der mächtigsten Ideen der Informatik.
Der Einstieg
Sage ohne Rechner voraus, was das Programm ausgibt. Verfolge den Ablauf auf Papier.
Auflösung
Aufruf mit 4
Aufruf mit 3
Aufruf mit 2
Aufruf mit 1
Basisfall erreicht
Rückkehr aus 2 mit 2
Rückkehr aus 3 mit 6
Rückkehr aus 4 mit 24
Ergebnis: 24Erst geht es vier Ebenen tief hinunter, dann kommt die Berechnung auf dem Rückweg zustande. Das ist der typische Ablauf: Der eigentliche Rechenschritt passiert erst, wenn der rekursive Aufruf zurückgekehrt ist.
Die zwei Bestandteile
Jede rekursive Methode braucht genau zwei Dinge:
- Einen Basisfall – eine Situation, in der die Methode ohne weiteren Selbstaufruf antworten kann. Bei der Fakultät:
pN <= 1. - Einen Rekursionsschritt – der Selbstaufruf mit einem Argument, das dem Basisfall näher kommt. Bei der Fakultät:
fakultaet(pN - 1).
Fehlt der Basisfall, oder kommt der Schritt ihm nicht näher, läuft die Rekursion unendlich weiter – bis der Speicher voll ist. Das ist das Gegenstück zur Endlosschleife.
Ändere im Programm oben fakultaet(pN - 1) zu fakultaet(pN) und führe es aus.
Was passiert? Wie unterscheidet sich der Abbruch von dem einer Endlosschleife?
Auflösung
Das Programm bricht mit einem Fehler ab: Der Speicher für die Aufrufverwaltung ist voll.
Der Unterschied zur Endlosschleife: Eine Endlosschleife läuft ewig weiter und verbraucht keinen zusätzlichen Speicher. Eine endlose Rekursion legt bei jedem Aufruf neuen Speicher an und bricht deshalb nach einiger Zeit ab.
Für die Fehlersuche ist die Rekursion damit sogar freundlicher: Sie meldet sich, statt stumm hängenzubleiben.
Der Aufrufstapel
Woher weiß Java, wohin es nach return zurückkehren muss?
Bei jedem Methodenaufruf legt Java einen Eintrag auf den Aufrufstapel (englisch call stack): die Rücksprungadresse und die lokalen Variablen des Aufrufs. Bei return wird der oberste Eintrag wieder heruntergenommen.
Bei fakultaet(4) liegen zwischenzeitlich vier Einträge übereinander – jeder mit einem eigenen Wert für pN. Genau deshalb wissen die Aufrufe nichts voneinander.
Und genau deshalb ist es derselbe Datentyp, den du in der letzten Lektion gebaut hast: ein Stapel. Wer zuletzt kam, geht zuerst.
Aufruf fakultaet(4)
┌──────────────┐
│ pN = 1 │ ← zuletzt aufgerufen, kehrt zuerst zurück
├──────────────┤
│ pN = 2 │
├──────────────┤
│ pN = 3 │
├──────────────┤
│ pN = 4 │ ← zuerst aufgerufen, kehrt zuletzt zurück
└──────────────┘Rekursiv oder iterativ?
Beide Fassungen liefern dasselbe.
a) Welche findest du besser lesbar? Begründe.
b) Welche braucht mehr Speicher? Warum?
c) In welchen Fällen wäre die rekursive Fassung deutlich im Vorteil?
Auflösung
a) Auslegungssache. Die rekursive Fassung bildet die mathematische Definition wörtlich ab: „n! ist n mal (n−1)!“. Die iterative sagt, wie man es ausrechnet. Wer die Definition kennt, findet die Rekursion klarer.
b) Die rekursive. Sie legt für jeden Aufruf einen Eintrag auf den Aufrufstapel – bei summeRekursiv(100000) sind das hunderttausend. Die iterative Fassung braucht immer gleich viel.
c) Überall dort, wo die Struktur der Daten selbst rekursiv ist:
- Ein Baum besteht aus einem Knoten und zwei Teilbäumen, die selbst wieder Bäume sind.
- Ein Ordner enthält Dateien und Unterordner, die selbst wieder Ordner sind.
- Ein Term besteht aus Teiltermen.
Bei solchen Strukturen ist die iterative Fassung deutlich umständlicher – man muss sich den Stapel selbst bauen.
Rekursion in der Grafik
Ein Bild sagt hier mehr als jede Erklärung.
a) Wo ist der Basisfall, wo der Rekursionsschritt?
b) Was passiert, wenn du pTiefe von 8 auf 12 erhöhst? Rechne vorher aus, wie viele Äste dann gezeichnet werden.
c) Ändere den Verzweigungswinkel von 25 auf 40 und die Schrumpfung von 0.72 auf 0.6. Beschreibe, was sich ändert.
Auflösung
a) Der Basisfall ist pTiefe == 0 – dann wird nichts mehr gezeichnet. Der Rekursionsschritt sind die beiden Aufrufe am Ende, jeweils mit pTiefe - 1.
b) Auf jeder Ebene verdoppelt sich die Anzahl: 1 + 2 + 4 + … Bei Tiefe 8 sind das 2⁸ − 1 = 255 Äste, bei Tiefe 12 schon 2¹² − 1 = 4095.
Das ist exponentielles Wachstum – dieselbe Klasse, die du in der Einführungsphase als „prinzipiell unbrauchbar für große Eingaben“ kennengelernt hast. Hier ist es unproblematisch, weil die Tiefe klein bleibt.
c) Der Baum wird breiter und die Äste werden schneller kürzer – er sieht buschiger und gedrungener aus.
Aufgabe 1: Klassische Rekursionen
Ergänze die Methoden so, dass alle Tests grün werden. Alle sollen rekursiv gelöst werden.
Formuliere dir vor jeder Methode zwei Sätze: „Der Basisfall ist …“ und „Sonst gilt: …“.
Tipp 1: summe
Basisfall: Bei pN <= 0 ist die Summe 0.
Sonst: Die Summe von 1 bis n ist n plus die Summe von 1 bis n−1.
Tipp 2: fibonacci
Hier gibt es zwei Basisfälle: bei 0 und bei 1.
Sonst ruft sich die Methode zweimal auf – mit pN - 1 und mit pN - 2.
Tipp 3: umgekehrt
Basisfall: Ein Wort der Länge 0 oder 1 bleibt, wie es ist.
Sonst: Das umgekehrte Wort ist das umgekehrte Wort ohne den ersten Buchstaben, und daran hinten der erste Buchstabe.
Tipp 4: istPalindrom
Basisfall: Wörter mit weniger als zwei Zeichen sind Palindrome.
Sonst: Stimmen erstes und letztes Zeichen nicht überein, ist es keines. Stimmen sie überein, hängt alles daran, ob der Teil dazwischen ein Palindrom ist.
Aufgabe 2: Fibonacci ist eine Falle
Die rekursive Fibonacci-Methode ist elegant – und katastrophal langsam.
a) Zeichne auf Papier den Aufrufbaum für fibonacci(5). Wie oft wird fibonacci(2) berechnet?
b) Miss, wie lange fibonacci(30) und fibonacci(35) brauchen.
c) Erkläre, woher der Aufwand kommt.
d) Schreibe eine iterative Fassung und miss sie ebenfalls.
Tipp zur iterativen Fassung
Du brauchst nur die letzten beiden Werte zu merken. Starte mit 0 und 1 und schiebe sie in einer Schleife weiter:
int vorletzter = 0;
int letzter = 1;
for (int i = 2; i <= pN; i++) {
int neu = vorletzter + letzter;
vorletzter = letzter;
letzter = neu;
}Auflösung zu a) und c)
a) Der Aufrufbaum für fibonacci(5):
fib(5)
┌───────┴───────┐
fib(4) fib(3)
┌────┴────┐ ┌────┴────┐
fib(3) fib(2) fib(2) fib(1)
┌───┴───┐ ┌─┴─┐ ┌─┴─┐
fib(2) fib(1) fib(1) fib(0) ...fibonacci(2) wird dreimal berechnet. Bei fibonacci(30) wird fibonacci(2) über 800 000 Mal berechnet – jedes Mal von vorne.
c) Der Aufwand wächst exponentiell, weil sich jeder Aufruf in zwei neue teilt und dabei dieselben Teilprobleme immer wieder gelöst werden.
Die iterative Fassung ist dagegen linear – ein Durchlauf genügt.
Merke: Rekursion ist ein Werkzeug, kein Selbstzweck. Wo Teilprobleme sich überlappen, ist sie ohne Zusatzmaßnahmen die schlechtere Wahl.
Zusatzaufgabe
Die Türme von Hanoi: Drei Stäbe, auf dem ersten liegen n Scheiben, von unten nach oben immer kleiner. Alle sollen auf den dritten Stab – dabei darf immer nur eine Scheibe bewegt werden, und nie eine größere auf eine kleinere.
a) Löse es für n = 3 auf dem Tisch mit Münzen. Wie viele Züge brauchst du?
b) Formuliere die rekursive Idee in zwei Sätzen: Was ist der Basisfall? Und wie führt man n Scheiben auf n−1 zurück?
c) Schreibe eine Methode bewege(int pAnzahl, String pVon, String pNach, String pHilfe), die alle Züge ausgibt.
d) Wie viele Züge braucht das Verfahren für n Scheiben? Welche Wachstumsklasse ist das?