Der Aufrufstapel
Die Fakultät \(n! = n \cdot (n-1) \cdot \ldots \cdot 1\) lässt sich rekursiv berechnen: \(n! = n \cdot (n-1)!\) und \(1! = 1\). Doch während fakultaet(4) auf fakultaet(3) wartet, muss sich das Programm merken, dass danach noch mit 4 zu multiplizieren ist.
static long fakultaet(int n) {
if (n <= 1) {
return 1;
}
return n * fakultaet(n - 1);
}
- Rahmen:jeder Aufruf bekommt einen eigenen Speicherbereich mit seinen Parametern, lokalen Variablen und der Stelle, an der es nach der Rückkehr weitergeht.
- Aufrufstapel:die Rahmen liegen übereinander; nur der oberste arbeitet, alle darunter warten.
- Abstieg:jeder Selbstaufruf legt einen neuen Rahmen oben auf — bis die Abbruchbedingung greift.
- Aufstieg:
returnentfernt den obersten Rahmen und reicht den Wert an den wartenden Aufruf darunter. - Rekursionstiefe:größte Zahl gleichzeitig offener Aufrufe; bei
fakultaet(4)sind es 4.
| Schritt | Aufruf | Stapel (oben rechts) | Aktion |
|---|---|---|---|
| 1 | fakultaet(4) | f(4) | wartet auf 4 · fakultaet(3) |
| 2 | fakultaet(3) | f(4) f(3) | wartet auf 3 · fakultaet(2) |
| 3 | fakultaet(2) | f(4) f(3) f(2) | wartet auf 2 · fakultaet(1) |
| 4 | fakultaet(1) | f(4) f(3) f(2) f(1) | Abbruch: gibt 1 zurück |
| 5 | ← fakultaet(2) | f(4) f(3) f(2) | 2 · 1 = 2 zurück |
| 6 | ← fakultaet(3) | f(4) f(3) | 3 · 2 = 6 zurück |
| 7 | ← fakultaet(4) | f(4) | 4 · 6 = 24 zurück |
Drei andere Methoden, derselbe Mechanismus: Wähle oben eine Methode und gehe mit „Schritt vor“ (oder → auf der Bühne) durch die Aufrufe. Beobachte, wie der Stapel beim Abstieg wächst und beim Aufstieg Rahmen für Rahmen abgebaut wird. ▶ spielt alles ab.
Halte fest: Der zuletzt begonnene Aufruf wird als erster beendet. Beim Abstieg wird nur gewartet, gerechnet wird erst beim Aufstieg — außer bei ggT, wo der Wert unverändert nach unten durchgereicht wird.
Rahmen: Jeder Aufruf erhält einen eigenen Speicherbereich mit Parametern, lokalen Variablen und der Rücksprungstelle.
Aufrufstapel: Die Rahmen liegen übereinander; nur der oberste arbeitet, alle darunter warten.
Abstieg und Aufstieg: Jeder Selbstaufruf legt einen neuen Rahmen oben auf, bis die Abbruchbedingung greift; return entfernt den obersten Rahmen und reicht den Wert nach unten.
Rekursionstiefe: größte Zahl gleichzeitig offener Aufrufe.
Aufrufbaum bei zwei Selbstaufrufen
static int fib(int n) {
if (n <= 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
- Lineare Rekursion:ein Selbstaufruf je Aufruf — die Aufrufe bilden eine Kette.
- Baumrekursion:zwei oder mehr Selbstaufrufe — die Aufrufe bilden einen Aufrufbaum.
- Reihenfolge:Java wertet
fib(n - 1)vollständig aus, bevorfib(n - 2)beginnt: Der Baum wird von links nach rechts in die Tiefe durchlaufen. - Tiefe ≠ Anzahl:der Stapel ist höchstens so hoch wie der längste Ast, der Baum hat aber viel mehr Knoten.
fib(4): orange die Reihenfolge der Aufrufe, grün die Rückgabewerte, grün hinterlegt die Abbruchfälle.\(A(n)\) zählt die Aufrufe bei fib(n): der Aufruf selbst plus alle Aufrufe der beiden Teilbäume. Für \(n \le 1\) gilt \(A(n) = 1\).
Die beiden Teilbäume von fib(2) sind Abbruchfälle mit je einem Aufruf.
Linker Teilbaum fib(2) mit 3 Aufrufen, rechter Teilbaum fib(1) mit einem.
Neun Aufrufe — genau die neun Knoten im Baum. Die Rekursionstiefe ist dagegen nur 4.
Aufrufstapel: Der Abstieg legt Rahmen auf den Stapel, der Aufstieg nimmt sie in umgekehrter Reihenfolge ab. Rekursionstiefe = größte Stapelhöhe.
Lineare Rekursion: Ein Selbstaufruf je Aufruf — die Aufrufe bilden eine Kette.
Baumrekursion: Zwei oder mehr Selbstaufrufe — die Aufrufe bilden einen Aufrufbaum; Anzahl der Aufrufe = Knoten im Baum.
Tiefe ≠ Anzahl: Der Stapel ist höchstens so hoch wie der längste Ast, der Baum hat aber viel mehr Knoten.
Allgemeine Hinweise
Einrücken beim Mitschreiben
Rücke jeden neuen Aufruf eine Stufe weiter ein und jede Rückgabe wieder aus. So siehst du sofort, welcher Aufruf auf welchen wartet — die Einrückung ist die Stapelhöhe.
Jeder Rahmen hat sein eigenes n
Die Parameter gehören zum jeweiligen Aufruf. Wird im inneren Aufruf n kleiner, bleibt das n der wartenden Aufrufe unverändert.
Gerechnet wird beim Rückweg
In return n * fakultaet(n - 1); wird erst multipliziert, wenn der innere Aufruf zurückkehrt. Wer beim Abstieg schon Zwischenergebnisse notiert, verrechnet sich leicht.