Rekursion: Basisfall und Zerlegung

Rekursion löst ein Problem, indem sie dasselbe Problem auf kleineren Instanzen aufruft. Jede rekursive Methode braucht mindestens einen Basisfall, der ohne Selbstaufruf antwortet, und einen rekursiven Fall, der Fortschritt Richtung Basisfall garantiert.

Beispiel: Länge einer Liste: null -> 0; sonst 1 + Länge des Rests.

Ohne Basisfall oder ohne Verkleinerung entsteht unendliche Rekursion.

$$\mathrm{fact}(n)=n\cdot\mathrm{fact}(n-1),\quad \mathrm{fact}(0)=1$$

Wo gebraucht

Dateibaum-Walks, DOM/JSON-Bäume, Parser, Divide-and-Conquer, Backtracking. Überall, wo die Daten selbst rekursiv sind, ist Rekursion die direkte Abbildung der Struktur auf Kontrollfluss.

Vertiefung

Eine rekursive Definition benötigt einen Basisfall und einen Fortschrittsmassstab. Für jeden rekursiven Aufruf muss dieses Mass in einer wohlfundierten Ordnung kleiner werden. Nur dann folgt Terminierung aus der Struktur des Problems.

Der Basisfall ist nicht bloss ein technischer Abbruch. Er legt die kleinste Bedeutung der Funktion fest, aus der grössere Ergebnisse aufgebaut werden. Eine falsche Rückgabe dort verfälscht alle darüberliegenden Ebenen.

Korrektheit lässt sich oft induktiv zeigen: Der Basisfall stimmt, und unter der Annahme korrekter kleinerer Ergebnisse erzeugt der Rekursionsschritt das korrekte grössere Ergebnis.

Schwierigkeitsstufen

1. Basisfall und rekursiven Schritt identifizieren.
2. Ein streng fallendes Terminierungsmass angeben.
3. Einen Induktionsbeweis an die Implementierung koppeln.

Fallstricke

Ein erreichbarer Basisfall genügt nicht, wenn manche Pfade das Mass nicht verkleinern. Auch ein zu spät geprüfter Basisfall kann bereits einen ungültigen Zugriff auslösen.