Rekursion versus Iteration: Stacktiefe, Grenzen und wann umgestellt werden sollte

Worum es geht

Eine rekursive Funktion löst ein Problem, indem sie sich selbst auf kleinere Instanzen anwendet; jeder unabgeschlossene Aufruf belegt einen Frame auf dem Call-Stack. Der Stack ist endlich. Python erzwingt eine Rekursionsgrenze, abrufbar mit sys.getrecursionlimit(), die laut Dokumentation verhindern soll, dass unendliche Rekursion den C-Stack überläuft und den Interpreter zum Absturz bringt; ein Überschreiten löst RecursionError aus. Nativer Code ist durch die Stackgrösse des Threads begrenzt (die Grenze des Hauptthreads ist RLIMIT_STACK in getrlimit(2)); ein Überlauf dort ist ein Segmentation Fault, keine Ausnahme. Iteration hält den Zustand in Variablen oder in einem expliziten Stack oder einer Queue auf dem Heap, dessen Grösse durch den Speicher begrenzt ist, nicht durch einen festen Stack.

Warum es wichtig ist

Rekursion, deren Tiefe der Eingabe folgt, ist eine Angriffsfläche für Denial-of-Service: tief verschachteltes JSON, ein Verzeichnisbaum mit Tausenden von Ebenen, eine lange verkettete Struktur oder ein Parser für verschachtelte Klammern lassen sich durch eine gezielt konstruierte Eingabe zum Absturz bringen. Tail-Call-Elimination ist nicht anzunehmen, sofern die Sprachspezifikation sie nicht ausdrücklich zusichert; die meisten verbreiteten Sprachen tun das nicht, sodass eine „endrekursive Schleife" weiterhin pro Iteration einen Frame verbraucht.

So wird es angewendet

• Rekursion für Probleme beibehalten, deren Tiefe durch die Struktur begrenzt ist, nicht durch die Eingabegrösse: balancierte Bäume, Syntaxbäume aus einem grössenbegrenzten Parser, Teile-und-herrsche über Hälften (die Tiefe ist logarithmisch).
• Umstellen, wenn die Tiefe linear zur Eingabe wächst: einen Baum mit einem expliziten Stack (Tiefensuche) oder einer Queue (Breitensuche) durchlaufen; lineare Rekursion durch eine Akkumulatorschleife ersetzen.
• Wo Rekursion beibehalten wird, einen Tiefenparameter übergeben und bei einem dokumentierten Maximum sauber fehlschlagen, bevor die Laufzeitgrenze greift, mit einer Fehlermeldung, die die Grenze nennt.
• Ein Anheben der Rekursionsgrenze als Notlösung behandeln: Sie tauscht einen RecursionError gegen einen möglichen C-Stack-Überlauf ein, und die Stackgrösse anderer Threads wird getrennt von der des Hauptthreads festgelegt.
• Rekursive Funktionen mit überlappenden Teilproblemen memoisieren (siehe dynamische Programmierung); Memoisierung reduziert den Aufwand, nicht die Tiefe.

Stolpersteine

Eine Umstellung auf Iteration ändert die Besuchsreihenfolge, sofern Kindknoten nicht in umgekehrter Reihenfolge auf den Stack gelegt werden. Wechselseitige Rekursion verbirgt Tiefe über mehrere Funktionen hinweg. Tiefe Ketten delegierender Generatoren (yield from) werden bei jeder Fortsetzung durchlaufen; ihre Tiefe wie Rekursionstiefe behandeln. Ausnahmen, die einen tiefen Stack abwickeln, sind langsam und erzeugen riesige Tracebacks. Rekursive __eq__, __repr__ oder Serialisierer auf zyklischen Daten terminieren nie; besuchte Objekte nachverfolgen.

Die Tiefenbegrenzung gilt auch für die iterative Form

Rekursion durch einen expliziten Stack zu ersetzen begrenzt die Tiefe nicht; es verschiebt die Grenze lediglich vom Call-Stack auf den Heap, wo der Fehlerfall ein Out-of-Memory-Abbruch des gesamten Prozesses ist statt eines abfangbaren RecursionError. Bei von der Eingabe gesteuerter Verschachtelung (JSON, Klammern, Verzeichnisbäume) in beiden Formen eine dokumentierte Höchsttiefe einhalten: in der rekursiven Version den Tiefenparameter prüfen, in der iterativen Version die Länge des expliziten Stacks prüfen, jeweils mit einem Fehler, der die Grenze nennt, fehlschlagen. Parser bringen eine solche Begrenzung häufig mit (zum Beispiel weist serde_json standardmässig Dokumente zurück, die tiefer als 128 Ebenen verschachtelt sind). Ist eine Begrenzung vorhanden, ist die Wahl zwischen Rekursion und Iteration eine Frage der Klarheit und der Framekosten der Laufzeitumgebung, nicht der Sicherheit.