Rekursion
Zuletzt aktualisiert
Rekursion bedeutet, dass eine Funktion sich selbst mit einer kleineren Version desselben Problems aufruft, bis sie bei einem Fall landet, der so klein ist, dass er sich direkt beantworten lässt. Genau dieser direkt beantwortbare Fall ist der Basisfall, und jede rekursive Funktion braucht einen: fib(n) zerfällt immer weiter in fib(n - 1) und fib(n - 2), bis fib(1) oder fib(0) erreicht ist, die sich einfach selbst zurückgeben. Der Visualizer oben führt genau das aus: Drücke auf Abspielen und sieh zu, wie sich die Aufrufe zu einem Baum verzweigen, an den Blättern die Basisfälle erreichen und ihre Werte dann wieder nach oben zurückgeben, wo sie auf jeder Ebene kombiniert werden.
Das Zweite, was die Animation zeigt, ist der Aufrufstapel (Call Stack): jeder Aufruf, der begonnen, aber noch nicht zurückgegeben hat. Der Stapel wächst, je tiefer die Aufrufe gehen, erreicht sein Maximum bei der Rekursionstiefe und baut sich wieder ab, sobald die Ergebnisse zurückkommen. Genau deshalb kann tiefe Rekursion in einen Stack Overflow laufen, während eine iterative Schleife den Stapel nie wachsen lässt. Dieselbe Aufrufform steckt hinter der Tiefensuche, hinter Merge Sort und hinter den meisten Operationen auf einem Binärbaum.
Zeit- und Speicherkomplexität
Für die oben gezeigte naive rekursive Fibonacci-Berechnung und die zwei üblichen Verbesserungen:
| Ansatz | Zeit | Speicher | Anmerkungen |
|---|---|---|---|
| Naive Rekursion | O(2^n) | O(n) | Der Aufrufbaum verdoppelt sich auf jeder Ebene; der Speicher entspricht dem tiefsten Stapel, nicht dem ganzen Baum. |
| Mit Memoisierung | O(n) | O(n) | Jedes fib(k) wird einmal berechnet und zwischengespeichert; wiederholte Teilbäume schrumpfen auf ein Nachschlagen zusammen. |
| Iterative Schleife | O(n) | O(1) | Zwei mitlaufende Variablen ersetzen den Stapel vollständig. |
| Jede Rekursion, allgemein | Aufrufe × Arbeit pro Aufruf | O(max depth) | Der Stapel hält einen Frame pro Aufruf, der begonnen, aber noch nicht zurückgegeben hat. |
Schritt für Schritt
| Schritt | Was passiert |
|---|---|
| 1 | Der erste Aufruf fib(n) landet auf dem Aufrufstapel. |
| 2 | Er braucht fib(n - 1), also landet auch dieser Aufruf auf dem Stapel; der Elternaufruf wartet. |
| 3 | Die Aufrufe schachteln sich weiter, bis einer bei n <= 1 ankommt: Der Basisfall antwortet sofort, ohne tieferen Aufruf. |
| 4 | Der Wert des Basisfalls geht an den Elternaufruf zurück, der nun seinen zweiten Aufruf starten kann: fib(n - 2). |
| 5 | Sind beide Kindaufrufe zurückgekehrt, addiert der Elternaufruf sie und kehrt selbst zurück; sein Frame verlässt den Stapel. |
| 6 | Das Zurückkehren wiederholt sich den Baum hinauf, bis der Frame des ersten Aufrufs mit der endgültigen Antwort vom Stapel genommen wird und der Stapel leer ist. |
Durchgerechnetes Beispiel
Auswertung von fib(4) in exakter Aufrufreihenfolge, genau so, wie die Animation sie abspielt:
| Aufruf | Stapel in diesem Moment | Gibt zurück |
|---|---|---|
fib(4) | fib(4) | wartet auf die Kindaufrufe |
fib(3) | fib(4) > fib(3) | wartet auf die Kindaufrufe |
fib(2) | fib(4) > fib(3) > fib(2) | wartet auf die Kindaufrufe |
fib(1) | fib(4) > fib(3) > fib(2) > fib(1) | 1 (Basisfall) |
fib(0) | fib(4) > fib(3) > fib(2) > fib(0) | 0 (Basisfall) |
fib(2) kombiniert | fib(4) > fib(3) > fib(2) | 1 + 0 = 1 |
fib(1) | fib(4) > fib(3) > fib(1) | 1 (Basisfall) |
fib(3) kombiniert | fib(4) > fib(3) | 1 + 1 = 2 |
fib(2) erneut | fib(4) > fib(2) | 1, komplett neu berechnet |
fib(4) kombiniert | fib(4) | 2 + 1 = 3 |
Wann Rekursion verwenden
| Verwenden, wenn | Vermeiden, wenn |
|---|---|
| Das Problem selbstähnlich ist: Bäume, verschachtelte Strukturen, Teile und herrsche | Eine einfache Schleife dasselbe ohne Stack-Frames ausdrückt |
Die Tiefe begrenzt und moderat ist, etwa O(log n) bei Merge Sort | Die Tiefe bei riesigen Eingaben die Eingabegröße erreichen kann und ein Stack Overflow droht |
| Backtracking den Stapel braucht, um sich zu merken, wo es weitergeht | Dieselben Teilprobleme sich wiederholen und du sie nicht zwischenspeicherst |
| Die rekursive Fassung klar leichter zu lesen und zu prüfen ist | Du in einer performancekritischen Schleife bist, in der der Aufruf-Overhead messbar ins Gewicht fällt |
Recursion-Code
Eine saubere, lauffähige Recursion-Implementierung in Python, JavaScript, Java, C++, C. Wähle eine Sprache, kopiere den Code oder öffne ihn vorgeladen im Coddy-Playground.
Recursion-Code in Python
Python
1calls = 02
3def fib(n, depth=0):4 global calls5 calls += 16 # Print the call with its depth so the recursion is visible7 print(" " * depth + f"fib({n})")8 if n <= 1:9 return n10 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1)11
12
13print("fib(5) =", fib(5))14print("calls made:", calls)Recursion-Code in JavaScript
JavaScript
1let calls = 0;2
3function fib(n, depth = 0) {4 calls += 1;5 // Print the call with its depth so the recursion is visible6 console.log(' '.repeat(depth) + `fib(${n})`);7 if (n <= 1) return n;8 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);9}10
11console.log('fib(5) =', fib(5));12console.log('calls made:', calls);Recursion-Code in Java
Java
1public class Main {2 static int calls = 0;3
4 static int fib(int n, int depth) {5 calls++;6 // Print the call with its depth so the recursion is visible7 System.out.println(" ".repeat(depth) + "fib(" + n + ")");8 if (n <= 1) return n;9 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);10 }11
12 public static void main(String[] args) {13 System.out.println("fib(5) = " + fib(5, 0));14 System.out.println("calls made: " + calls);15 }16}Recursion-Code in C++
C++
1#include <iostream>2#include <string>3
4int calls = 0;5
6int fib(int n, int depth) {7 calls++;8 // Print the call with its depth so the recursion is visible9 std::cout << std::string(depth * 2, ' ') << "fib(" << n << ")\n";10 if (n <= 1) return n;11 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);12}13
14int main() {15 int result = fib(5, 0);16 std::cout << "fib(5) = " << result << "\n";17 std::cout << "calls made: " << calls << "\n";18 return 0;19}Recursion-Code in C
C
1#include <stdio.h>2
3int calls = 0;4
5int fib(int n, int depth) {6 calls++;7 /* Print the call with its depth so the recursion is visible */8 printf("%*sfib(%d)\n", depth * 2, "", n);9 if (n <= 1) return n;10 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);11}12
13int main(void) {14 printf("fib(5) = %d\n", fib(5, 0));15 printf("calls made: %d\n", calls);16 return 0;17}Rekursion FAQ
Was ist ein Basisfall in der Rekursion?
Die Eingabe, die klein genug ist, um sie ohne weiteren rekursiven Aufruf zu beantworten. Bei
fib(n) ist das n <= 1, was n direkt zurückgibt. Ohne erreichbaren Basisfall hören die Aufrufe nie auf, der Stapel wächst immer weiter und das Programm stürzt mit einem Stack Overflow ab.Was ist der Aufrufstapel und warum ist er wichtig?
Die Laufzeitumgebung hält einen Frame pro Aufruf, der begonnen, aber noch nicht zurückgegeben hat, samt seinen Argumenten und lokalen Variablen. Die Rekursionstiefe entspricht der Stapelhöhe: Eine Rekursion, die
n Ebenen tief geht, belegt O(n) Speicher, selbst wenn jeder Aufruf fast nichts tut. Die Chip-Reihe unter der Animation zeigt genau diesen Stapel beim Wachsen und beim Abbauen.Warum braucht rekursives Fibonacci exponentielle Zeit?
Weil dieselben Teilprobleme immer wieder neu berechnet werden: Im durchgerechneten Beispiel oben wird
fib(2) innerhalb von fib(4) zweimal ausgewertet, und diese Verdopplung wiederholt sich grob auf jeder Ebene, was O(2^n) Aufrufe ergibt. Speichert man jedes Ergebnis beim ersten Berechnen zwischen, also Memoisierung, schrumpft der Baum auf O(n).Ist Rekursion besser als Iteration?
Keines von beiden ist grundsätzlich besser. Jede Rekursion lässt sich als Schleife mit explizitem Stapel schreiben und jede Schleife als Rekursion. Rekursion gewinnt bei der Lesbarkeit für selbstähnliche Probleme wie Baumtraversierungen und die Tiefensuche; Iteration gewinnt bei Speicher und Aufruf-Overhead für lineare Durchläufe.
Was verursacht einen Stack Overflow in einer rekursiven Funktion?
Entweder ein fehlender oder nie erreichter Basisfall, sodass die Aufrufe nie enden, oder eine korrekte Rekursion, deren Tiefe schlicht das Stapellimit der Laufzeitumgebung sprengt, etwa ein Aufruf pro Element bei Millionen von Elementen. Die Abhilfen: den Basisfall garantieren, die Tiefe begrenzen oder auf Iteration umstellen.
Welche Algorithmen sind von Natur aus rekursiv?
Teile-und-herrsche-Sortierverfahren wie Merge Sort und Quicksort, Traversierungen eines Binärbaums und von Graphen, die binäre Suche, Backtracking-Rätsel wie das Damenproblem sowie alles, was über verschachtelte Strukturen wie JSON oder ein Dateisystem definiert ist.
Verwandte Ressourcen
Mehr Visualisierungen
