Rekursion und warum Python sie (nicht) mag 🌀

Wenn Sie im Vorstellungsgespräch gebeten werden, Fakultät oder Fibonacci-Zahlen rekursiv zu schreiben – schreiben Sie sie. Aber wenn Sie sie in der Praxis oft verwenden...
Ja, Rekursion ist konzeptionell schön, mathematisch elegant, aber wenn man sich zu sehr hineinsteigert, kann man die Produktion lahmlegen und den gesamten Arbeitsspeicher mit Stack-Frames füllen.

Wir analysieren, was unter der Haube passiert und warum Python Rekursion im Gegensatz zu funktionalen Sprachen nicht mag.

1️⃣ Der Preis: der Aufrufstapel
Jeder Funktionsaufruf ist nicht kostenlos. Es wird ein neuer Stack-Frame im Speicher erstellt. In diesem Frame werden lokale Variablen und die Rücksprungadresse gespeichert.
Stellen Sie sich eine Matroschka vor, bei der jede nächste Puppe genauso viel wiegt wie die vorherige. In Python lastet dieses "Gewicht" auf dem Arbeitsspeicher.
Eine while- oder for-Schleife verwendet einen einzigen Speicherblock. Rekursion verbraucht Speicher linear (oder exponentiell) proportional zur Aufruftiefe.

2️⃣ Warum es keine Endrekursionsoptimierung gibt
In Sprachen wie Haskell oder C++ ist der Compiler schlau. Wenn der rekursive Aufruf die letzte Aktion in der Funktion ist (Endrekursion), ersetzt er ihn durch einen einfachen Sprung (GOTO), ohne einen neuen Frame zu erstellen. Dies wird als Tail Call Optimization (TCO) bezeichnet.

In Python gibt es TCO nicht und wird es nicht geben. Guido van Rossum (BDFL) ist grundsätzlich gegen TCO in Python. Das Argument ist einfach: „Wir wollen vollständige Tracebacks von Fehlern sehen.“ Wenn der Stack zusammengeklappt wird, erfahren Sie nie, bei welcher Rekursionstiefe der Fehler aufgetreten ist.
Daher ist das Limit von 1000 Aufrufen (Standard) kein Fehler, sondern eine Sicherung gegen Stack-Überlauf. Kann man es über sys.setrecursionlimit erhöhen? Ja. Aber wenn Sie das brauchen, haben Sie zu 99% einen Architekturfehler gemacht.

3️⃣ Wann ist Rekursion böse, wann notwendig?
❌ Lineare Strukturen (z. B. Listen): Berechnung von Fakultät, Fibonacci-Zahlen oder Durchlaufen einer flachen Liste. Eine iterative while/for-Schleife ist immer schneller und speicherschonender (O(1) Speicher gegenüber O(N)).
✅ Verzweigte Strukturen (Bäume, Graphen, verschachtelte Dicts): Parsen von JSON, Durchlaufen des Dateisystems, DOM-Baums oder Algorithmen wie Divide and Conquer (QuickSort, MergeSort). Hier reduziert Rekursion die kognitive Belastung und macht den Code lesbar.

4️⃣ Heilmittel gegen Langsamkeit: @lru_cache
Ein klassisches Beispiel für Dummheit ist die Berechnung von Fibonacci "brute force". Die Komplexität ist O(2^n). Das bedeutet, dass das Programm zur Berechnung der 50. Zahl stirbt, bevor es fertig ist.
Die Lösung ist Memoisation.
Der Dekorator @functools.lru_cache speichert die Ergebnisse von Aufrufen zwischen. Wenn die Funktion bereits mit diesem Argument aufgerufen wurde, holt Python einfach den fertigen Wert aus der Hashtabelle. Das verwandelt den exponentiellen Schrecken in lineare Komplexität O(N).

Fazit: Python ist nicht Haskell oder Lisp. Hier ist Rekursion ein Bürger zweiter Klasse. Verwenden Sie sie für Bäume und Graphen, aber für alles andere gibt es Schleifen.

#anatomie_des_python