Recursion

Kurz: Eine Methode, die sich selbst aufruft, um ein Problem in kleinere Teilprobleme derselben Art zu zerlegen — braucht immer einen Abbruchfall, sonst läuft sie endlos.

Genauer: Jeder rekursive Aufruf legt einen neuen Eintrag auf dem Call-Stack ab; ohne Abbruchbedingung (Base Case) führt das irgendwann zu einem StackOverflowError. Klassisches Lehrbeispiel ist die Fakultätsberechnung, viele solche Fälle lassen sich alternativ auch iterativ mit einer Schleife lösen.

int fakultaet(int n) {
    if (n <= 1) return 1;
    return n * fakultaet(n - 1);
}

Im Detail

int fakultaet(int n) {
    if (n <= 1) return 1;          // Base Case - stoppt die Rekursion
    return n * fakultaet(n - 1);   // rekursiver Aufruf mit kleinerem Teilproblem
}
 
// fakultaet(4) läuft so ab:
// fakultaet(4) = 4 * fakultaet(3)
//              = 4 * (3 * fakultaet(2))
//              = 4 * (3 * (2 * fakultaet(1)))
//              = 4 * (3 * (2 * 1)) = 24
 
// Fehlt der Base Case -> StackOverflowError
int endlos(int n) {
    return n * endlos(n - 1); // kein Abbruch - ruft sich für immer weiter selbst auf
}
 
// Fibonacci-Zahlen rekursiv - anschauliches, aber ineffizientes Beispiel
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2); // zwei rekursive Aufrufe pro Schritt!
}

Jeder Methodenaufruf (auch ein rekursiver) legt einen neuen Stack-Frame mit eigenen lokalen Variablen an — bei fakultaet(4) liegen kurzzeitig vier solcher Frames übereinander, bis die Rekursion wieder “zurückrollt” und die Ergebnisse multipliziert. Das naive fib(n)-Beispiel zeigt ein häufiges Rekursions-Problem: es berechnet dieselben Teilergebnisse (z. B. fib(2)) exponentiell oft mehrfach neu, was für größere n extrem langsam wird — hier hilft entweder Memoization (Zwischenergebnisse cachen) oder eine iterative Schleifen-Lösung, die dasselbe Ergebnis in linearer Zeit liefert. Als grobe Faustregel: Rekursion ist oft eleganter lesbar bei Problemen, die sich natürlich selbst-ähnlich zerlegen lassen (Baumstrukturen, Divide-and-Conquer-Algorithmen), iterative Lösungen sind fast immer speicher- und performanceschonender.

Siehe auch: Methods, Schleifen, Algorithms