Endrekursion und Iteration in Java

Endrekursion bedeutet: der rekursive Aufruf ist die letzte Aktion, das Ergebnis wird unverändert durchgereicht. Dann braucht man den alten Frame logisch nicht mehr.

Akkumulator-Muster:

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

Äquivalente Iteration: Schleife multipliziert acc, bis n bei 1 ankommt.

Warum das in Java zählt: HotSpot macht daraus nicht automatisch eine Schleife. Tiefe Endrekursion kann trotzdem StackOverflowError auslösen. Deshalb in Java bei grosser Tiefe iterieren oder einen expliziten Deque als Stack nutzen.

Wo Endrekursion trotzdem wichtig ist: Übergabe an Sprachen mit TCO, Lesen funktionaler Specs, mechanische Umformung Rekursion → Schleife, und als Kontrast zu Divide-and-Conquer-Rekursion (Hanoi, Merge Sort), die nach dem Aufruf noch kombiniert und damit nicht endständig ist.

Hanoi-Kurzform als Gegenbeispiel zur Endrekursion: zwei rekursive Aufrufe plus Zug dazwischen, Anzahl Züge 2^n - 1.

Wo gebraucht

Funktionale Sprachen und JVM-fremde Laufzeiten nutzen Tail-Call-Optimierung, um Endrekursion stapelkonstant zu machen. Auf der HotSpot-JVM fehlt das; Endrekursion ist trotzdem die richtige Denkform, bevor man bewusst in eine Schleife übersetzt.

Vertiefung

Bei einer endrekursiven Funktion ist der rekursive Aufruf die letzte semantische Aktion. Der gesamte Folgezustand kann daher durch aktualisierte Parameter beschrieben werden. Java garantiert jedoch nicht, dass solche Aufrufe ohne zusätzliche Aktivierungsdatensätze ausgeführt werden.

Eine Schleife überführt Parameter in veränderliche Zustandsvariablen und hält den Speicherbedarf unabhängig von der Schrittzahl. Das unterscheidet sich von Teil-und-herrsche-Verfahren, bei denen nach einem Teilaufruf noch Ergebnisse kombiniert oder weitere Zweige besucht werden müssen.

Für tiefe Baum- oder Graphalgorithmen kann ein Deque offene Teilprobleme explizit speichern. Dadurch werden Kapazität, Reihenfolge und Fehlerbehandlung sichtbar steuerbar. Der benötigte Speicher verschwindet nicht, liegt aber nicht mehr in der impliziten Aufrufverwaltung.

Schwierigkeitsstufen

1. Letzte rekursive Aktion von nachgelagerter Kombination unterscheiden.
2. Parameterzustand in eine Schleifeninvariante übertragen.
3. Rekursive Verzweigungen mit einem expliziten Deque simulieren.

Fallstricke

Syntaktisch letzte Zeile bedeutet nicht automatisch endrekursiv, wenn das Ergebnis danach noch verrechnet wird. Eine entsprechende Form schützt in Java ausserdem nicht verlässlich vor zu grosser Aufruftiefe.