Java Rekursion

Rekursion bedeutet, dass eine Methode sich selbst aufruft. Es ist ein natürlicher Weg, Probleme auszudrücken, deren Struktur sich in kleinerem Maßstab wiederholt — herunterzählen, einen Baum durchlaufen, eine Fakultät berechnen, einen String umkehren.

Jede rekursive Methode besteht aus zwei Teilen: einem Basisfall, der direkt zurückgibt, ohne zu rekursieren, und einem rekursiven Fall, der die Methode auf einem kleineren Teil des Problems aufruft. Stimmt einer der Teile nicht, liefert das Programm entweder ein falsches Ergebnis oder läuft endlos (bis die JVM den Stack sprengt).

Ein erstes Beispiel: Fakultät

Die Fakultät von n ist n × (n-1) × (n-2) × … × 1. Per Definition gilt 0! = 1. Diese Definition ist selbst rekursiv: n! = n × (n-1)!.

Die Java-Übersetzung ergibt sich direkt:

public static int factorial(int n) {
  if (n == 0) return 1;            // base case
  return n * factorial(n - 1);      // recursive case
}

Der Aufruf factorial(4) ergibt:

factorial(4)
  = 4 * factorial(3)
  = 4 * 3 * factorial(2)
  = 4 * 3 * 2 * factorial(1)
  = 4 * 3 * 2 * 1 * factorial(0)
  = 4 * 3 * 2 * 1 * 1
  = 24

Jeder Aufruf wartet auf dem Stack, bis der nächste zurückgibt. Wenn factorial(0) schließlich 1 zurückgibt, pflanzt sich das Ergebnis die Kette hinauf fort.

Der Basisfall ist unverzichtbar

Ohne einen Basisfall hat die Methode nichts, was die Rekursion stoppt. Der klassische Fehler:

public static int factorial(int n) {
  return n * factorial(n - 1);    // no base case
}

Dies rekursiert endlos — bis der Aufruf-Stack erschöpft ist und die JVM einen StackOverflowError auslöst. Der Basisfall ist das, was die Kette beendet; der rekursive Fall ist das, was auf ihn zuschreitet.

Der andere klassische Fehler ist ein Basisfall, den die Rekursion niemals erreicht:

public static int factorial(int n) {
  if (n == 0) return 1;
  return n * factorial(n + 1);    // wrong direction
}

factorial(4) würde hier factorial(5), factorial(6), … versuchen und abstürzen. Der rekursive Aufruf muss das Argument näher an den Basisfall heranführen.

Rekursion auf ganzen Zahlen: Countdown

Ein triviales zweites Beispiel zur Verdeutlichung — die Zahlen von n bis 1 ausgeben:

public static void countdown(int n) {
  if (n <= 0) return;             // base case
  System.out.println(n);
  countdown(n - 1);                // recursive case
}

countdown(3) gibt 3, 2, 1 aus. Tausche die Reihenfolge, um 1, 2, 3 auszugeben:

public static void countup(int n) {
  if (n <= 0) return;
  countup(n - 1);                  // recurse first, print after
  System.out.println(n);
}

Gleiche Rekursion, andere Ausgabereihenfolge — weil der rekursive Aufruf vor der Ausgabe erfolgt. Die Lektion: Was man vor dem rekursiven Aufruf tut, geschieht auf dem Weg hinunter; was man danach tut, geschieht auf dem Weg zurück.

Rekursion auf Strings: Umkehren

Man kann das Umkehren eines Strings so verstehen: „Nimm das erste Zeichen weg, kehre den Rest um, hänge das erste Zeichen an das Ende":

public static String reverse(String s) {
  if (s.length() <= 1) return s;            // base case
  return reverse(s.substring(1)) + s.charAt(0);
}

reverse("cat") → reverse("at") + 'c' → reverse("t") + 'a' + 'c' → "t" + 'a' + 'c' → "tac".

Das ist elegant, aber ineffizient — jeder rekursive Aufruf allokiert einen neuen Substring. Eine StringBuilder-Schleife wäre schneller. Rekursion ist oft der klarste Ausdruck einer Idee; sie ist nicht immer die schnellste Implementierung.

Fibonacci und die Kosten der Rekursion

Die Fibonacci-Folge lautet 0, 1, 1, 2, 3, 5, 8, 13, …, definiert als fib(n) = fib(n-1) + fib(n-2). Die direkte Übersetzung:

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

Das ist korrekt, aber exponentiell langsam — fib(40) läuft bereits spürbar langsam, fib(50) ist schmerzhaft. Der Rekursionsbaum berechnet dieselben Teilprobleme milliardenfach neu (fib(5) allein ruft fib(2) dreimal auf). Die Lösung in echtem Code ist entweder Memoization oder eine einfache Schleife.

Memoization behält die rekursive Form, speichert aber jedes Ergebnis beim ersten Berechnen zwischen, sodass jedes Teilproblem nur einmal ausgeführt wird:

public static long fibMemo(int n, long[] cache) {
  if (n < 2) return n;
  if (cache[n] != 0) return cache[n];      // already computed
  return cache[n] = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
}
// call as: fibMemo(50, new long[51])

Eine einfache Schleife verzichtet vollständig auf die Rekursion und benötigt konstanten Speicher:

public static long fibLoop(int n) {
  long a = 0, b = 1;
  for (int i = 0; i < n; i++) {
    long next = a + b;
    a = b;
    b = next;
  }
  return a;
}

Zu wissen, wann Rekursion das falsche Werkzeug ist, ist genauso wichtig wie zu wissen, wann sie das richtige ist.

Rekursion vs. Iteration

Jede rekursive Methode lässt sich als Schleife umschreiben, und jede Schleife lässt sich als Rekursion umschreiben — sie sind gleich mächtig. Die Wahl hängt von Klarheit und Kosten ab:

• Rekursion wählen, wenn die Daten selbst rekursiv sind (Bäume, verschachtelte Ordner, JSON) oder wenn die rekursive Definition klarer als die Schleife ist, wie bei factorial oder reverse.
• Eine Schleife wählen, wenn die Rekursion tief genug wäre, um einen StackOverflowError zu riskieren, oder wenn eine iterative Version genauso lesbar ist und den Overhead pro Aufruf vermeidet, wie bei fib.

Wenn beide gleich klar sind, bevorzuge in Java die Schleife: Sie hat keine Stack-Tiefenbegrenzung und keine Aufruf-Frame-Kosten.

StackOverflowError

Jeder ausstehende Aufruf belegt einen Teil des JVM-Stacks. Mit der Standard-Stack-Größe können in der Regel einige Tausend Aufrufe verschachtelt werden, bevor es zu Problemen kommt:

factorial(100000);    // StackOverflowError

Java führt keine Tail-Call-Optimierung durch — selbst ein rekursiver Aufruf, der das letzte ist, was die Methode tut, verbraucht noch einen Stack-Frame. Wenn das Problem sehr tiefe Rekursion erfordern kann, wechsle zu einer Schleife oder verwende ein explizites Deque als eigenen Stack.

Ein ausgearbeitetes Beispiel

Was kommt als Nächstes

Du hast Methoden definiert, Parameter übergeben, Namen überladen und rekursiert. Das nächste Konzept ist Scope — welche Teile einer Methode welche Variablen sehen können und was passiert, wenn ein Name an mehr als einer Stelle vorkommt. Lies weiter im Kapitel über Variablen-Scope.

Übungen