Verzweigte Rekursion und Mehrfacharbeit

Verzweigte Rekursion erzeugt mehrere Aufrufe pro Frame, etwa naive Fibonacci: fib(n)=fib(n-1)+fib(n-2). Die Aufrufzahl wächst exponentiell, viele Teilprobleme werden wiederholt.

Gegenmittel: Memoization, dynamische Programmierung oder geschlossene Formeln.

Komplexität der naiven Variante versus linearer DP-Variante unterscheiden können.

$$T(n)=T(n-1)+T(n-2)+\Theta(1)$$

Dieselbe Zerlegung linear: Fibonacci Number [1].

Wo gebraucht

Unmemoized Suchbäume, naive rekursive Layouts, exponentielle Parser-Varianten. Dieselbe Struktur steckt in Divide-and-Conquer (Merge Sort) und in Backtracking; der Unterschied ist, ob Teilprobleme überlappen und ob man Ergebnisse speichert.

Vertiefung

Bei verzweigter Rekursion entstehen aus einem Problem mehrere Teilprobleme. Die Laufzeit hängt nicht nur von der Tiefe, sondern auch von der Zahl der Knoten im entstehenden Aufrufbaum ab.

Naive Fibonacci-Berechnung löst dieselben Argumente wiederholt. Memoisierung speichert Ergebnisse nach Argument und reduziert den Aufrufbaum auf die Zahl verschiedener Teilprobleme. Dynamische Programmierung berechnet dieselben Abhängigkeiten in geordneter Form ohne Rekursion.

Nicht jede Verzweigung bedeutet Mehrfacharbeit. Bei Divide-and-conquer-Verfahren können disjunkte Teilbereiche entstehen; dann bestimmt zusätzlich die Arbeit zum Teilen und Kombinieren die Rekurrenz.

Schwierigkeitsstufen

1. Einen kleinen Aufrufbaum zeichnen.
2. Wiederholte und disjunkte Teilprobleme unterscheiden.
3. Eine Rekurrenz mit Memoisierung oder Teil-und-herrsche-Struktur analysieren.

Fallstricke

Die Rekursionstiefe allein beschreibt die Laufzeit nicht. Memoisierung hilft nur, wenn Zustände eindeutig und mit vertretbarem Aufwand als Schlüssel gespeichert werden.