Rekursion.

Rekursion löst ein Problem, indem eine Funktion sich selbst aufruft, auf einem kleineren oder einfacheren Teilproblem, bis ein Basisfall erreicht ist. Typische Anwendungsfälle sind Fakultät, Fibonacci, Baum-Traversierung und Divide-and-Conquer-Algorithmen, also überall dort, wo sich ein Problem natürlich in kleinere Teilprobleme zerlegen lässt und die Problemstruktur sich direkt im Code widerspiegelt. Du lernst hier, rekursive Funktionen zu schreiben, ihren Ablauf am Call-Stack zu verfolgen, den Basisfall (englisch: Base Case) und den Fortschritt sauber zu setzen und die typischen Klausurfallen (StackOverflowError, fehlender Basisfall, doppelte Berechnungen bei Fibonacci) zu vermeiden.

Pflicht-Bestandteile jeder terminierenden rekursiven Funktion

• Basisfall (Abbruchbedingung): wann hört die Rekursion auf, ohne sich selbst aufzurufen
• Fortschritt zum Basisfall: jeder rekursive Aufruf bringt das Problem dem Basisfall näher. Fehlt der Fortschritt (z. B. f(n) ruft wieder f(n) oder f(n+1) auf), entsteht eine endlose Aufruf-Kette, auch mit Basisfall.

Wichtige Folgen und Abgrenzungen

• Stack Overflow: ohne Basisfall oder ohne Fortschritt ruft sich die Funktion endlos auf, bis der Call-Stack voll ist (Java: StackOverflowError, Python: RecursionError bei überschrittener sys.getrecursionlimit(); CPython nutzt standardmäßig häufig ein Limit um 1000, das konkrete Limit ist mit sys.getrecursionlimit() abfragbar und mit sys.setrecursionlimit() änderbar).
• Rekursion vs Iteration: im Prinzip lässt sich Rekursion durch eine iterative Lösung mit explizitem Stack simulieren. Praktisch ist das nicht immer kürzer oder verständlicher, besonders bei Bäumen und Divide-and-Conquer.
• Direkt vs indirekt: Direkte Rekursion ruft sich selbst auf (f → f). Indirekte Rekursion ist eine Kette (f → g → f), die seltener vorkommt aber dieselben Regeln braucht.

Wichtig: Das Teilproblem muss nicht numerisch kleiner sein. Bei Bäumen, Listen oder Graphen arbeitest du oft mit einer kleineren oder vereinfachten Struktur (Teilbaum, Tail einer Liste, kleinerer Sub-Graph).

In Klausuren wirst du oft gefragt: schreibe eine rekursive Funktion für Fakultät / Fibonacci oder trace die Aufrufe für fakultaet(4) Schritt für Schritt. Pro Aufruf eine Zeile aufschreiben mit aktuellem Argument und Rückgabewert.

Rekursives Denken in drei Fragen

Wenn du eine rekursive Funktion schreibst, frag dich der Reihe nach:

1. Was ist der Basisfall? Für welche Eingabe kann ich die Antwort ohne Selbstaufruf direkt geben?
2. Wie sieht das nächst-kleinere Teilproblem aus? Was übergebe ich beim rekursiven Aufruf, um dem Basisfall einen Schritt näher zu kommen?
3. Wie kombiniere ich das Teilergebnis mit dem aktuellen Wert? Was rechne ich mit dem Rückgabewert des rekursiven Aufrufs?

Diese drei Fragen sind die mentale Vorlage hinter jedem rekursiven Algorithmus.

Klassisches Beispiel: Fakultät

Die Fakultät ist für alle nichtnegativen ganzen Zahlen definiert: 0! = 1 (per Definition) und für n ≥ 1 gilt n! = n · (n-1) · dots · 1. Mathematisch rekursiv:

0! = 1, und für n ≥ 1 gilt n! = n · (n-1)!.

Genau das schreiben wir auch im Code, plus eine Eingabe-Validierung gegen negative Zahlen:

public static int fakultaet(int n) {
  if (n < 0) {
    throw new IllegalArgumentException("n muss >= 0 sein");
  }
  if (n <= 1) {
    return 1;             // Basisfall: 0! = 1, 1! = 1
  }
  return n * fakultaet(n - 1);  // Rekursiver Aufruf
}

def fakultaet(n):
    if n < 0:
        raise ValueError("n muss >= 0 sein")
    if n <= 1:
        return 1                 # Basisfall: 0! = 1, 1! = 1
    return n * fakultaet(n - 1)  # Rekursiver Aufruf

Am Fakultätsbeispiel prüfen: Basisfall und Fortschritt

Im Code oben kannst du beide Pflicht-Bestandteile direkt identifizieren:

1. Basisfall: if (n <= 1) return 1; deckt 0! und 1! ab und kehrt ohne weiteren Selbstaufruf zurück.
2. Fortschritt: der rekursive Aufruf ist fakultaet(n - 1), also wird n in jedem Schritt um 1 kleiner und nähert sich dem Basisfall.

Fehlt eine dieser beiden Eigenschaften, ruft sich die Funktion endlos auf: Java wirft StackOverflowError, Python einen RecursionError.

Was passiert intern

fakultaet(4) führt zu insgesamt 4 Funktionsaufrufen (Startaufruf fakultaet(4) plus 3 rekursive Selbstaufrufe bis zum Basisfall fakultaet(1)), die nacheinander zurückgeben:

fakultaet(4)
= 4 * fakultaet(3)
= 4 * 3 * fakultaet(2)
= 4 * 3 * 2 * fakultaet(1)
= 4 * 3 * 2 * 1
= 24

fakultaet(4)
= 4 * fakultaet(3)
= 4 * 3 * fakultaet(2)
= 4 * 3 * 2 * fakultaet(1)
= 4 * 3 * 2 * 1
= 24

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:

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.

Call-Stack live beobachten

Folge dem Stack für die Beispiel-Rekursion fakultaet(4). Im Visualizer siehst du links den wachsenden Call-Stack (jeder Frame zeigt das aktuelle n), rechts die Rückgabewerte beim Abbau. Du siehst zuerst, wie sich Aufrufe stapeln (jeder wartet auf den nächsten), dann wird der Basisfall erreicht und die Rückgabe rollt Frame für Frame zurück.

Wichtig: der Call-Stack ist begrenzt. Bei sehr tiefer Rekursion (typisch > 1000 Aufrufe) wirft Java einen StackOverflowError, Python einen RecursionError (nach sys.getrecursionlimit(), standardmäßig 1000). Tail-Rekursion bringt in Standard-Java (HotSpot JVM) und CPython keinen Vorteil, weil beide keine Tail-Call-Optimierung haben (Details im Erklärungs-Tab oben). Bei sehr tiefer Rekursion solltest du die Funktion meist iterativ umschreiben.

---

Code-Stepper: Schritt für Schritt durchspielen

Drei interaktive Demos zu Rekursion mit voll sichtbarem Call-Stack: fakultaet(4) als Standard-Linear-Rekursion, fibonacci(4) als Verzweigungs-Beispiel (zwei rekursive Aufrufe pro Schritt) und ein Bug-Demo mit vergessenem Basisfall, das zum Stack Overflow führt. Klicke auf Step oder Auto und beobachte, wie der Stack wächst und beim Rückgeben wieder abgebaut wird.

1. fakultaet(4): linearer Stack-Aufbau + Rollback

2. fibonacci(4): Verzweigung mit doppelten Aufrufen

Anders als Fakultät hat Fibonacci zwei rekursive Aufrufe pro Schritt: fib(n-1) + fib(n-2). Das führt zu einem Baum von Aufrufen, viele Teilergebnisse werden doppelt berechnet. Hier sehen wir die ersten Schritte von fib(4).

3. Bug-Demo: vergessener Basisfall → Stack Overflow

Was passiert, wenn der Basisfall fehlt oder unerreichbar ist? Die Funktion ruft sich endlos selbst auf, der Stack wächst unbegrenzt - bis Java StackOverflowError wirft. Hier eine kaputte countDown-Funktion, die statt zu stoppen immer weiter zählt.

Quiz: Rekursion

Sechs Fragen zu Basisfall, Stack Overflow und Klausur-Klassikern wie Fakultät / Fibonacci.