Rekursion
Rekursion: die Programmiertechnik, die einfach aussieht, bis man sie versteht. Und dann auch.
Was wäre, wenn eine Funktion ein Problem lösen könnte, indem sie eine etwas einfachere Version von sich selbst um Hilfe bittet — immer wieder, bis die Antwort offensichtlich ist? Das ist Rekursion.
Die Entwickler-Plattform "Stack Overflow" wurde nach genau dem Absturz benannt (Stack Overflow = Stapelüberlauf), der passiert, wenn eine Rekursion kein Ende findet. So bekannt ist dieser Absturz unter Programmierern.
Die sich selbst aufrufende Funktion
Definition
Rekursion
Analogie
Definition
Die Matroschka-Analogie bricht an zwei Stellen. Ein Puppensatz hat immer eine kleinste Puppe; einer Rekursion ohne Basisfall fehlt sie, und das Öffnen geht endlos weiter, bis der Speicher erschöpft ist oder, wie in Python, das Rekursionslimit greift. Und während ein Mensch sich seinen Beitrag einfach merkt, muss im Programm jeder Stapelrahmen seinen Zustand (Parameter, lokale Variablen) ausdrücklich speichern, solange er auf das Ergebnis des darunterliegenden Aufrufs wartet.
Beispiel: Fakultät (5!) — Abstieg und Rückkehr
- 1. factorial(5) ruft factorial(4) auf — merkt sich 5 * ?
- 2. factorial(4) ruft factorial(3) auf — merkt sich 4 * ?
- 3. factorial(3) ruft factorial(2) auf — merkt sich 3 * ?
- 4. factorial(2) ruft factorial(1) auf — merkt sich 2 * ?
- 5. factorial(1) erreicht BASISFALL → gibt 1 zurück
- 6. factorial(2) = 2 * 1 = 2
- 7. factorial(3) = 3 * 2 = 6
- 8. factorial(4) = 4 * 6 = 24
- 9. factorial(5) = 5 * 24 = 120
Am tiefsten Punkt existieren 5 Stapelrahmen gleichzeitig im Speicher, jeder mit seiner eigenen Kopie von n. Wenn der Basisfall zurückkehrt, werden die Rahmen einer nach dem anderen in umgekehrter Reihenfolge abgebaut — das sogenannte "Abwickeln" (Unwinding).
Merke
Python-Code: Fakultät
def factorial(n):
if n <= 1: # Basisfall
return 1
return n * factorial(n - 1) # Rekursiver Fall
print(factorial(5)) # Ausgabe: 120Der Basisfall: Dein Sicherheitsnetz
Der Basisfall ist die wichtigste Zeile in jeder rekursiven Funktion. Er definiert, WANN die Funktion aufhört sich selbst aufzurufen und WAS sie an diesem Punkt zurückgibt. Ohne Basisfall ruft sich die Funktion unendlich oft auf — jeder Aufruf erzeugt einen neuen Stapelrahmen, bis der verfügbare Speicher erschöpft ist oder, wie in Python, ein festes Rekursionslimit greift.
Stell dir ein kreisförmiges Labyrinth ohne Ausgangsschilder vor. Ohne Markierung wandert man endlos im Kreis. Setzt man eine rote Markierung an eine bestimmte Stelle mit der Anweisung "Wenn du die rote Markierung siehst, bleib stehen" — dann wird aus endlosem Wandern eine endliche Suche. Diese Markierung ist der Basisfall.
Merke
Countdown: Ohne vs. mit Basisfall
# KAPUTT — kein Basisfall
def countdown(n):
print(n)
countdown(n - 1) # ruft endlos: 3, 2, 1, 0, -1, ...
# → RecursionError nach ~1000 Aufrufen
# KORREKT — Basisfall stoppt bei 0
def countdown(n):
if n <= 0: # Basisfall
print(0)
return # STOPP
print(n)
countdown(n - 1) # Rekursiver FallDer Unterschied ist eine einzige if-Abfrage — aber sie entscheidet zwischen einem funktionierenden Programm und einem Absturz. Der Basisfall muss VOR dem rekursiven Aufruf im Funktionskörper stehen.
Achtung
Häufiger Fehler: Rekursionslimit erhöhen
sys.setrecursionlimit(10000) fügt keinen zusätzlichen Speicher hinzu. Bei endloser Rekursion verzögert es nur den Absturz, und ein zu hohes Limit kann Python selbst zum Absturz bringen. Wenn die Rekursion endlos läuft oder das Problem sehr große Tiefe erfordert, ist die richtige Lösung entweder ein korrekter Basisfall oder der Umstieg auf eine iterative Lösung.
Wo Schleifen versagen: Rekursion für Hierarchien
Schleifen (for, while) eignen sich hervorragend für lineare Folgen: durch eine Liste iterieren, von 1 bis n zählen. Aber wenn die Datenstruktur selbst verschachtelt ist — Ordner in Ordnern, HTML-Elemente in Elementen, Äste eines Spielbaums — kann eine einfache Schleife nicht tiefer als eine Ebene sehen.
Du musst alle .pdf-Dateien auf einer Festplatte finden. Den Ordner auf oberster Ebene durchgehen und jede Datei prüfen ist einfach. Aber manche Einträge sind Ordner, die weitere Dateien und Ordner enthalten, verschachtelt bis in unbekannte Tiefe. Der rekursive Ansatz: "Öffne den Ordner. Prüfe jeden Eintrag. Ist es eine Datei? Bewerte sie. Ist es ein Ordner? Wende dasselbe Verfahren an."
def find_pdfs(folder): results = [] for item in os.listdir(folder): path = os.path.join(folder, item) if os.path.isfile(path) and path.endswith('.pdf'): results.append(path) elif os.path.isdir(path): results.extend(find_pdfs(path)) return results Kürzer, liest sich wie die Problembeschreibung. Nutzt den Aufrufstapel implizit.
def find_pdfs_iterative(root): results = [] stack = [root] while stack: folder = stack.pop() for item in os.listdir(folder): path = os.path.join(folder, item) if os.path.isfile(path) and path.endswith('.pdf'): results.append(path) elif os.path.isdir(path): stack.append(path) return results Umgeht Pythons Rekursionslimit bei sehr tiefen Verzeichnissen.
Merke
Rekursion in der Praxis
Interaktiv: Fibonacci-Aufrufbaum
Klicke dich Schritt für Schritt durch den Aufrufbaum von fib(5). Beobachte, wie sich die Funktion immer wieder selbst aufruft, bis sie einen Basisfall erreicht — und wie die Ergebnisse dann den Baum hinauf zurückkehren. Achte besonders darauf, dass fib(3) zweimal berechnet und fib(2) dreimal aufgerufen wird.
Merke
Synthese: Rekursion ist kein Zauber
Rekursion ist kein Zauber — sie ist ein diszipliniertes Delegationsmuster: Zerlege das Problem, vertraue darauf, dass dein zukünftiges Ich das kleinere Stück bewältigt, und definiere den Punkt, an dem die Delegation aufhört.
In der KI ist Rekursion allgegenwärtig: Baumtraversierungen, Tiefensuche (DFS), Divide-and-Conquer-Algorithmen und Spielbaum-Bewertung (MinMax) — alles basiert auf dem rekursiven Prinzip.
Merke
Das Wichtigste auf einen Blick
- Rekursion = eine Funktion ruft sich selbst auf, um ein Problem auf eine kleinere Version desselben Problems zu reduzieren.
- Jede rekursive Funktion braucht zwei Teile: den Basisfall (wann aufhören) und den rekursiven Fall (wie weiter).
- Ohne Basisfall: unendliche Aufrufe → Stapelüberlauf (in Python: RecursionError). Der Basisfall ist das Sicherheitsnetz.
- Rekursion ist ideal für hierarchische Probleme (Ordner, Bäume, verschachtelte Strukturen), bei denen die Tiefe unbekannt ist.
- Rekursion und Iteration können dieselben Probleme lösen, aber Rekursion bildet hierarchische Probleme natürlicher ab.
Prüfen
Quiz: Rekursion
Welche zwei Teile braucht jede rekursive Funktion?
Wähle eine Antwort
1. Welche zwei Teile braucht jede rekursive Funktion?
2. factorial(4) wird aufgerufen. Wie viele Stapelrahmen existieren maximal gleichzeitig?
3. Eine countdown-Funktion hat keinen Basisfall. Was passiert bei countdown(3)?
4. Du musst alle .txt-Dateien in einem Ordner mit Unterordnern unbekannter Tiefe finden. Warum ist Rekursion hier besser als eine einfache for-Schleife?
Prüfen
Checkpoint: Teste dein Wissen
Kannst du das in eigenen Worten erklären? Hake ab, was sitzt.
0 von 3 sitzen