Rekursion vs. Iteration

Viele Probleme lassen sich sowohl rekursiv (Methode ruft sich selbst auf) als auch iterativ (Schleife) lösen. Beide Wege führen zum gleichen Ergebnis, unterscheiden sich aber in Lesbarkeit, Speicherverbrauch und Laufzeit. Im Abitur ist es eine typische Aufgabe, einen Algorithmus von einer Form in die andere zu übersetzen und die Vor- und Nachteile zu diskutieren.

Rekursiv (Java):

public static long fakRek(int n) {
    return (n <= 1) ? 1 : n * fakRek(n - 1);
}

Iterativ (Java):

public static long fakIter(int n) {
    long erg = 1;
    for (int i = 2; i <= n; i++) erg *= i;
    return erg;
}

Rekursiv (Python):

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

Iterativ (Python):

def fak_iter(n):
    erg = 1
    for i in range(2, n + 1):
        erg *= i
    return erg

Jeder rekursive Aufruf belegt einen Stack-Frame mit lokalen Variablen, Rücksprungadresse und Argumenten. Bei einer Tiefe von \( n \) ergibt das \( \mathcal{O}(n) \) zusätzlichen Speicher. Die Iteration dagegen kommt mit konstantem Speicher \( \mathcal{O}(1) \) aus. Außerdem sind Methoden- bzw. Funktionsaufrufe in der Praxis langsamer als Schleifeniterationen, da sie Sprünge und Speicherzugriffe auslösen.

Eine Rekursion heißt endrekursiv, wenn der rekursive Aufruf die letzte Aktion der Methode ist. Sprachen wie Scheme oder Scala können solche Aufrufe automatisch in eine Schleife umwandeln (tail call optimization) und vermeiden damit Stack-Frames. Java und Python führen diese Optimierung nicht durch – daher droht in beiden Sprachen bei tiefer Rekursion ein Stacküberlauf. Beispiel für endrekursive Fakultät (Java):

public static long fakTail(int n, long acc) {
    if (n <= 1) return acc;
    return fakTail(n - 1, n * acc);
}

Rekursion ist ideal für baumartige oder selbstähnliche Probleme: Baumtraversierung, MergeSort, Backtracking. Iteration ist effizienter für lineare Durchläufe und Zählschleifen. Für Fibonacci ist die iterative Variante der naiven Rekursion klar überlegen, weil sie Doppelberechnungen vermeidet.

Beim Übergang von Iteration zu Rekursion wird der Akkumulator als Parameter vergessen. Beim umgekehrten Weg sind Schleifengrenzen oft falsch (Off-by-one). In Python ist die Standardrekursionstiefe auf 1000 begrenzt – tiefere Rekursionen werfen RecursionError.

Zusammenfassung: Rekursion ist elegant, aber speicherhungrig; Iteration ist effizient, aber teils umständlich. Endrekursion kann in optimierenden Sprachen den Stack-Verbrauch eliminieren.

Abitur-Tipp: Begründe deine Wahl immer mit einem Komplexitätsargument (Stack \( \mathcal{O}(n) \) gegen Iteration \( \mathcal{O}(1) \)) – das gibt sichere Punkte.