Rekursion auf verketteten Strukturen

Rekursion passt zu verketteten und baumartigen Daten: ein Knoten plus rekursive Verarbeitung der Kinder bzw. des Restes.

Beispiel Summe: null -> 0; sonst value + sum(next).

Vorteil: Code spiegelt die Datenform. Nachteil: Tiefe gleich Listenlänge kann den Stack sprengen; dann Iteration.

$$\mathrm{len}(x)=\mathrm{len}(x.\mathrm{next})+1$$

Wo gebraucht

Listen- und Baumverarbeitung in Compilern, Pretty-Printer, Serialisierung, Visitor-ähnliche Walks. In Java bei grosser Tiefe bewusst auf Iteration oder trampoline-/stack-basierte Walks umstellen.

Vertiefung

Verkettete Strukturen besitzen eine natürliche rekursive Form: Ein Knoten enthält einen Wert und den Rest der Struktur. Der leere Verweis bildet den Basisfall, der Nachfolger das kleinere Teilproblem.

Beim Vorwärtsverarbeiten geschieht die Arbeit vor dem rekursiven Aufruf, beim Rückwärtsverarbeiten danach. Diese Position entscheidet etwa, ob Werte in Listenreihenfolge oder umgekehrt ausgegeben werden.

Die strukturelle Eleganz ändert nichts an der linearen Aufruftiefe einer langen Kette. Für unbeschränkt grosse Daten ist eine Schleife robuster. Bei Bäumen kann Rekursion dagegen die Verzweigungsstruktur besonders direkt spiegeln.

Schwierigkeitsstufen

1. Leeren Verweis und Nachfolger als Rekursionsbestandteile erkennen.
2. Ausgabe vor und nach dem Aufruf vergleichen.
3. Eine rekursive Listenfunktion iterativ formulieren.

Fallstricke

Ein Zyklus verletzt die Annahme einer endlichen Kette und verhindert den Basisfall. Rekursive Verfahren brauchen bei potenziell zyklischen Strukturen daher zusätzliche Erkennung.