Lineare Rekursion: Fakultät und Summe

Lineare Rekursion: jeder Aufruf erzeugt höchstens einen weiteren Aufruf. Fakultät: n! = 1 für n <= 1, sonst n * (n-1)!. Summe 1..n analog.

Die Aufruftiefe ist $\Theta(n)$. Die Arbeit ist $\Theta(n)$, wenn pro Frame konstante Arbeit anfällt.

Iterative Varianten vermeiden Stackwachstum und sind in Java oft robuster.

Lineare Rekurrenz als Treppe: Climbing Stairs [1].

Wo gebraucht

Lehrform für Induktion und für das Lesen von Spezifikationen. In Produktion ersetzt man lineare Ketten oft durch Schleifen; die rekursive Form bleibt in Beweisen, in funktionalen Sprachen und in Codegenerator-Ausgabe sichtbar.

Vertiefung

Lineare Rekursion erzeugt pro Aktivierung höchstens einen weiteren rekursiven Aufruf. Die Anzahl aktiver Ebenen entspricht bei Fakultät oder Präfixsumme der Grösse des noch nicht bearbeiteten Eingabeteils.

Die Fakultätsdefinition kombiniert das kleinere Ergebnis beim Zurückkehren mit dem aktuellen Faktor. Eine Summenfunktion über ein Array kann analog Index oder Restlänge als Fortschrittsmass verwenden. Beide benötigen lineare Zeit und linearen Aufrufspeicher.

Numerische Grenzen bleiben unabhängig von der Rekursionsform. int und long überlaufen schon bei moderaten Fakultätsargumenten; für exakte grosse Werte ist BigInteger nötig.

Schwierigkeitsstufen

1. Aufruf- und Rückkehrphase einer linearen Rekursion verfolgen.
2. Zeit- und Speicherbedarf aus dem Fortschrittsmass ableiten.
3. Rekursionslogik von numerischem Überlauf trennen.

Fallstricke

Ein korrekter Abbruch schützt nicht vor arithmetischem Überlauf. Häufig wird ausserdem nur die Zahl der Aufrufe betrachtet und der gleichzeitig belegte Aufrufspeicher vergessen.