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.
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.
Abstieg legt Rahmen auf den Aufrufstapel, Aufstieg nimmt sie in umgekehrter Reihenfolge ab · Rekursionstiefe = größte Stapelhöhe · bei Baumrekursion: Anzahl der Aufrufe = Knoten im Aufrufbaum
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.