Zurück zum Lernbereich

Rekursion

Rekursion: die Programmiertechnik, die einfach aussieht, bis man sie versteht. Und dann auch.

  • Grundlagen
  • 14 min
  • Einsteiger

Einfache Sprache

Diese Vorschau ist in Einfacher Sprache. Das ganze Portal gibt es auch in Einfacher Sprache. Du kannst oben die Sprache wechseln. Oder nutze den Knopf unten. Unsere Texte in Einfacher Sprache entstehen KI-gestützt und werden redaktionell begleitet. Sie orientieren sich an den Grundprinzipien der Leichten Sprache, sind aber keine geprüfte Leichte Sprache: Eine Prüfgruppe von Menschen mit Lernschwierigkeiten prüft sie nicht.

Vorschau: Rekursion

Was ist Rekursion?

Eine Funktion kann sich selbst aufrufen. Das nennt man Rekursion. Rekursion bedeutet: Das Problem wird immer kleiner. Irgendwann gibt es eine einfache Antwort. Die Funktion stoppt dort.

Der Basisfall

Jede Rekursion braucht einen Basisfall. Basisfall bedeutet: Hier endet die Rekursion. Ohne Basisfall ruft sich die Funktion ewig auf. Das Programm stürzt ab.

Wo Rekursion hilft

Rekursion hilft bei verschachtelten Strukturen. Verschachtelt bedeutet: Etwas liegt in etwas anderem. Zum Beispiel: Ordner in Ordnern. Ein normales Programm kann nur eine Ebene durchsuchen. Rekursion kann alle Ebenen durchsuchen.

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

Rekursion funktioniert wie Matroschka-Puppen: Du öffnest die größte Puppe und findest eine kleinere mit einem Zettel: "Mach dasselbe mit mir." Jede Puppe wandert an die nächste Person, und das geht weiter, bis jemand bei der kleinsten Puppe ankommt, die sich nicht mehr öffnen lässt, und auf ihr eine Zahl findet — den Basisfall. Dann reist die Zahl zurück nach oben: Jede Person nimmt das Ergebnis, fügt ihren eigenen Beitrag hinzu und gibt es weiter.

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. 1. factorial(5) ruft factorial(4) auf — merkt sich 5 * ?
  2. 2. factorial(4) ruft factorial(3) auf — merkt sich 4 * ?
  3. 3. factorial(3) ruft factorial(2) auf — merkt sich 3 * ?
  4. 4. factorial(2) ruft factorial(1) auf — merkt sich 2 * ?
  5. 5. factorial(1) erreicht BASISFALL → gibt 1 zurück
  6. 6. factorial(2) = 2 * 1 = 2
  7. 7. factorial(3) = 3 * 2 = 6
  8. 8. factorial(4) = 4 * 6 = 24
  9. 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: 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 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 Fall

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

Rekursiv (impliziter Stack)

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.

Iterativ (expliziter Stack)

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

Dateisuche Ordnerstrukturen unbekannter Tiefe durchsuchen
HTML-Parsing Verschachtelte DOM-Elemente traversieren
JSON-Traversierung Verschachtelte Objekte und Arrays verarbeiten
Spielbäume MinMax-Algorithmus für Schach, Tic-Tac-Toe
Fraktale Sierpinski-Dreieck, Koch-Schneeflocke
Divide & Conquer Merge Sort, Quicksort, binäre Suche

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.

5 fib(5)
Schritt 1 / 13fib(5)
Steuerung
Schritte

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

  1. Rekursion = eine Funktion ruft sich selbst auf, um ein Problem auf eine kleinere Version desselben Problems zu reduzieren.
  2. Jede rekursive Funktion braucht zwei Teile: den Basisfall (wann aufhören) und den rekursiven Fall (wie weiter).
  3. Ohne Basisfall: unendliche Aufrufe → Stapelüberlauf (in Python: RecursionError). Der Basisfall ist das Sicherheitsnetz.
  4. Rekursion ist ideal für hierarchische Probleme (Ordner, Bäume, verschachtelte Strukturen), bei denen die Tiefe unbekannt ist.
  5. Rekursion und Iteration können dieselben Probleme lösen, aber Rekursion bildet hierarchische Probleme natürlicher ab.

Prüfen

Quiz: Rekursion

Noch offen

Welche zwei Teile braucht jede rekursive Funktion?

Wähle eine Antwort

Auflösung: 1) B · 2) C · 3) B · 4) B

Prüfen

Checkpoint: Teste dein Wissen

Kannst du das in eigenen Worten erklären? Hake ab, was sitzt.

0 von 3 sitzen