Jeder Aufruf landet auf dem Call-Stack (jeder Funktionsaufruf legt einen Stack-Frame an, der lokale Variablen und Rücksprungadresse speichert) und wartet, bis die tieferen Aufrufe fertig sind. Erst dann wird zurückgerechnet.
Klausur-Tracing als Tabelle
In Klausuren wird oft eine Trace-Tabelle gefordert. Für fakultaet(3) mit Basisfall n <= 1 sieht sie so aus:
| Aufruf-Nr. | n | Rückgabewert (beim Abbau) |
|---|
| 1 | 3 | 6 |
| 2 | 2 | 2 |
| 3 | 1 | 1 |
Spalte 1 zählt die Aufrufe vom Startaufruf bis zum Basisfall (3 Aufrufe für fakultaet(3)). Die Rückgabewerte werden von unten nach oben ausgefüllt: erst fakultaet(1) = 1 (Basisfall), dann fakultaet(2) = 2 · 1 = 2, zuletzt fakultaet(3) = 3 · 2 = 6.
Im interaktiven Abschnitt kannst du das Schritt für Schritt selbst sehen.
Fibonacci: warum rekursive Lösungen langsam sein können
Fibonacci ist klassisch rekursiv definiert: fib(n) = fib(n-1) + fib(n-2) mit Basisfällen fib(0) = 0 und fib(1) = 1. Die naive Rekursion verzweigt sich in jedem Schritt zwei Mal, viele Teilprobleme werden mehrfach gelöst:
fib(5) ruft fib(4) und fib(3) auf. fib(4) ruft wieder fib(3) und fib(2) auf. So wird fib(3) zweimal komplett neu berechnet.
Die Laufzeit der naiven Fibonacci-Rekursion ist exponentiell, O(2ⁿ) als gebräuchliche obere Schranke (genauer O(φⁿ) mit dem goldenen Schnitt φ ≈ 1,618), während eine iterative Lösung oder eine rekursive Lösung mit Memoization (gespeicherte Zwischen-Ergebnisse) linear (O(n)) ist. Im Stepper unten siehst du diese doppelten Aufrufe live.
Tail-Rekursion: was es ist und warum es in Java/Python (meist) nichts bringt
Eine Tail-Rekursion liegt vor, wenn der rekursive Aufruf das Letzte ist, was die Funktion tut, ohne dass danach noch gerechnet wird. return f(n-1) ist tail-rekursiv, return n * f(n-1) ist nicht tail-rekursiv (nach f(n-1) muss noch mit n multipliziert werden).
In Sprachen mit Tail-Call-Optimierung (TCO) kann der Compiler tail-rekursive Aufrufe in eine Schleife umwandeln und braucht damit nur einen einzigen Stack-Frame. Standard-Java (HotSpot JVM) und CPython unterstützen das nicht, daher bringt Tail-Rekursion dort keinen Vorteil; bei sehr tiefer Rekursion solltest du die Funktion meist iterativ umschreiben. (Einige Sprachen und Laufzeitumgebungen bieten TCO, auf Standard-Java/CPython solltest du dich nicht darauf verlassen.)
Konkrete Grenzen: Python hat ein konfigurierbares Limit (Standard ~1000, änderbar via sys.setrecursionlimit()); Javas Stack-Größe ist JVM-abhängig (typisch einige tausend Frames für Standard-Methoden, einstellbar via -Xss).
Wann Rekursion?
- Bäume durchgehen: Dateisystem, JSON, HTML-DOM, Syntax-Bäume.
- Mathematische Definitionen, die sich auf sich selbst beziehen (Fakultät, Fibonacci, ggT mit Euklid).
- Divide-and-Conquer-Algorithmen: Mergesort, Quicksort, Binäre Suche.
- Backtracking: Sudoku-Solver, Wege durch ein Labyrinth, Permutationen erzeugen.
Wann nicht: einfache Schleifen über Zähler oder Sammlungen sind oft schneller, klarer und sparen Stack. Faustregel: wenn das Problem nicht natürlich in Teilprobleme zerfällt, ist Iteration meist die bessere Wahl.
