Rekursion

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, der passiert, wenn eine Rekursion kein Ende findet. Das allein zeigt, wie wichtig — und wie häufig — dieses Konzept in der Informatik ist.

Die sich selbst aufrufende Funktion

Die Matroschka-Analogie bricht, weil in der realen Welt niemand den Kontext der vorherigen Puppe "erinnert". In einem Programm speichert jeder Stapelrahmen explizit seinen eigenen Zustand (Parameter, lokale Variablen) und wartet aktiv auf das Ergebnis des darunterliegenden Aufrufs.

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).

def factorial(n):
    if n <= 1:              # Basisfall
        return 1
    return n * factorial(n - 1)  # Rekursiver Fall

print(factorial(5))  # Ausgabe: 120

Der 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.

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.

# 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 Fall

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."

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, wie oft fib(2) und fib(3) mehrfach berechnet werden.