Rekursive Algorithmen

Eine Methode heißt rekursiv, wenn sie sich selbst aufruft. Jede rekursive Definition besteht aus zwei Teilen: dem Basisfall (Abbruchbedingung) und dem Rekursionsschritt, der das Problem auf eine kleinere Instanz reduziert. Ohne Basisfall läuft die Rekursion endlos und verursacht einen Stacküberlauf (StackOverflowError).

Mathematisch gilt \( n! = n \cdot (n-1)! \) mit \( 0! = 1 \). Diese Definition lässt sich direkt in Code umsetzen.

Java:

public static long fakultaet(int n) {
    if (n <= 1) return 1;          // Basisfall
    return n * fakultaet(n - 1);    // Rekursionsschritt
}

Python:

def fakultaet(n):
    if n <= 1:
        return 1
    return n * fakultaet(n - 1)

Die Fibonacci-Folge ist definiert durch \( F_0 = 0,\ F_1 = 1,\ F_n = F_{n-1} + F_{n-2} \). Hier sind zwei rekursive Aufrufe pro Schritt nötig.

Java:

public static long fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

Python:

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Bei jedem rekursiven Aufruf wird ein neuer Stack-Frame auf dem Aufrufstapel angelegt. Die Fakultät hat eine Rekursionstiefe von \( n \) und benötigt \( \mathcal{O}(n) \) Speicher. Die naive Fibonacci-Variante ist katastrophal: jeder Aufruf verzweigt sich, der Aufrufbaum hat \( \mathcal{O}(2^n) \) Knoten. Schon \( F_{40} \) dauert mehrere Sekunden. Mit Memoisierung oder einer iterativen Schleife sinkt der Aufwand auf \( \mathcal{O}(n) \).

Rekursion ist die natürliche Sprache für baumartige Strukturen: Dateisysteme, Syntaxbäume, Spielbäume, MergeSort, Quicksort, Backtracking-Probleme wie Sudoku oder das Acht-Damen-Problem. Überall dort, wo ein Problem in gleichartige Teilprobleme zerlegt werden kann, ist sie das Mittel der Wahl.

Typische Fallstricke sind: vergessener oder falscher Basisfall (Endlosrekursion), nicht-monotone Reduktion (das Argument wird nicht kleiner), Verwechslung von n-- und n - 1 sowie fehlende Rückgabe in Java. Auch der Glaube, Rekursion sei immer schöner als Iteration, ist falsch – bei tiefen Rekursionen droht der Stacküberlauf.

Zusammenfassung: Rekursion löst Probleme, indem sie sich auf kleinere Teilprobleme zurückführt. Basisfall und Rekursionsschritt sind unverzichtbar, der Stack-Verbrauch wächst mit der Tiefe.

Abitur-Tipp: Trace die Aufrufe von fib(5) auf Papier – das zeigt anschaulich, warum die naive Fibonacci-Rekursion exponentiell viele Aufrufe benötigt.