Rekursion Erklärt: Wann Einsetzen, Wann Nicht

Eine Funktion, die sich selbst aufruft, hat eine maximale Tiefe, und die ist kleiner, als die meisten erwarten: 1.000 Aufrufe in CPython standardmäßig, etwa 10.000 bis 15.000 in Node und in Browser-Engines, je nachdem, wie viel jeder Frame belegt. Wird dieses Limit überschritten, wird das Programm nicht einfach langsamer. Es stürzt ab. Python löst RecursionError: maximum recursion depth exceeded aus; JavaScript löst RangeError: Maximum call stack size exceeded aus.

Beide Fehler haben die gleiche Ursache, und wenn Sie sie einmal verstanden haben, wissen Sie, wann Rekursion das richtige Werkzeug ist und wann sie zum Risiko wird.

Was eine rekursive Funktion mit dem Aufrufstapel wirklich macht

Jeder Funktionsaufruf legt einen Frame auf den Stapel: die Argumente, die lokalen Variablen, die Rücksprungadresse. Ein normaler Aufruf kehrt zurück, und sein Frame wird entfernt. Ein rekursiver Aufruf kann noch nicht zurückkehren, weil er auf den Aufruf wartet, den er gerade gestartet hat, also bleibt jeder Frame auf dem Stapel, bis der darunterliegende fertig ist.

1
2
3
4

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

factorial(4) baut vier Frames auf dem Stapel auf, bevor einer von ihnen einen Wert liefert:

1
2
3
4

factorial(4) -> 4 * factorial(3)
                     factorial(3) -> 3 * factorial(2)
                                          factorial(2) -> 2 * factorial(1)
                                                               factorial(1) -> 1   # Basisfall, der Stapel wächst nicht weiter

Erst wenn factorial(1) 1 zurückgibt, wickelt sich der Stapel ab: 2 * 1, dann 3 * 2, dann 4 * 6, Ergebnis 24.

Zwei Teile sorgen dafür, dass das funktioniert. Der Basisfall (n <= 1) stoppt die Rekursion. Der rekursive Fall ruft die Funktion mit einer Eingabe erneut auf, die sich dem Basisfall annähert. Fehlt einer der beiden, hört die Funktion nie auf, sich selbst aufzurufen: In Python landen Sie innerhalb von tausend Aufrufen bei RecursionError, in einer Sprache ohne Limit stirbt der Prozess an einem Stack Overflow.

Wann Rekursion das richtige Werkzeug ist: verschachtelte Daten

Rekursion zahlt sich aus, wenn Daten bis zu einer Tiefe verschachtelt sind, die Sie vorher nicht kennen: ein Baum, ein Dateisystem, beliebig verschachteltes JSON. Eine Schleife über solche Daten braucht einen Stapel, den Sie selbst verwalten müssen. Rekursion liefert einen kostenlos, denn der Aufrufstapel ist der Stapel, den Sie brauchten.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def flatten(nested):
    result = []
    for item in nested:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result

flatten([1, [2, 3, [4, [5, 6]], 7], 8])
# [1, 2, 3, 4, 5, 6, 7, 8]

Jeder Aufruf von flatten kümmert sich um eine Ebene. Trifft die Funktion auf eine verschachtelte Liste, übergibt sie diese an einen neuen Aufruf, und der Stapel merkt sich, wo in der äußeren Liste weitergemacht wird, sobald die innere fertig ist. Die iterative Variante müsste diese Position selbst mitführen.

Das Durchlaufen eines Verzeichnisbaums hat die gleiche Form:

1
2
3
4
5
6

from pathlib import Path

def total_size(path: Path) -> int:
    if path.is_file():
        return path.stat().st_size
    return sum(total_size(child) for child in path.iterdir())

total_size ist es egal, ob ein Verzeichnis eine Ebene oder zehn tief ist. Jeder Aufruf kümmert sich um seinen eigenen path.

Wann Rekursion das falsche Werkzeug ist: flache, lange Eingaben

Eine flache Liste zu summieren ist der umgekehrte Fall. Es gibt keine Verschachtelung, also bringt Rekursion nichts außer Stapelrisiko.

1
2
3
4

def sum_recursive(nums):
    if not nums:
        return 0
    return nums[0] + sum_recursive(nums[1:])

Sie funktioniert bei kleinen Eingaben und scheitert bei realen Eingaben:

1
2
3
4

>>> sum_recursive(list(range(2000)))
Traceback (most recent call last):
  ...
RecursionError: maximum recursion depth exceeded

Zweitausend Elemente, ein Frame pro Element, das Doppelte des Standardlimits. Die Schleifenversion braucht nur einen einzigen Frame, unabhängig von der Länge der Liste:

1
2
3
4
5

def sum_iterative(nums):
    total = 0
    for n in nums:
        total += n
    return total

sum_iterative(list(range(1_000_000))) liefert sofort ein Ergebnis. In Begriffen der Big-O-Notation sind beide Varianten zeitlich O(n), aber die rekursive kostet zusätzlich O(n) an Stapelspeicher, und dieser Speicher ist auf rund tausend Frames begrenzt.

Löst Tail-Call-Optimierung tiefe Rekursion in Python oder JavaScript?

Nein. Bei sum_recursive passiert als Letztes die Addition, nicht der rekursive Aufruf, also muss jeder Frame am Leben bleiben, um ein Ergebnis zu erhalten und es zu addieren. Sie können die Funktion so umschreiben, dass der rekursive Aufruf die allerletzte Operation ist, und dabei die laufende Summe als Argument mitführen:

1
2
3
4

def sum_tail(nums, acc=0):
    if not nums:
        return acc
    return sum_tail(nums[1:], acc + nums[0])

In einer Sprache mit Tail-Call-Optimierung erkennt der Compiler, dass nach dem Aufruf nichts mehr aus dem Frame des Aufrufers gebraucht wird, und verwendet diesen Frame wieder, statt einen neuen auf den Stapel zu legen. Die Rekursion wird im Hintergrund zu einer Schleife.

CPython macht das nicht, aus einer bewussten Design-Entscheidung: Die Kernentwickler haben es abgelehnt, weil es Tracebacks schwerer lesbar machen würde. sum_tail stößt bei einer Liste mit 2.000 Elementen trotzdem an das Limit. Die ES2015-Spezifikation von JavaScript enthält Proper Tail Calls, aber V8 (Chrome, Node.js) und SpiderMonkey (Firefox) haben sie nie umgesetzt; nur JavaScriptCore, die Engine von Safari, tut es.

Die Regel ist also in beiden Sprachen gleich. Wenn die Größe der Eingabe entscheidet, wie tief die Rekursion geht, verlassen Sie sich nicht darauf, dass die Engine Sie rettet. Wandeln Sie die Funktion in eine Schleife um, oder begrenzen Sie die Tiefe.

Wie Memoization langsame Rekursion behebt

Manche rekursiven Funktionen kommen nie in die Nähe des Tiefenlimits. Ihr Problem ist, dass sie dieselbe Berechnung immer wieder ausführen. Die naive rekursive Fibonacci-Funktion ist der klassische Fall:

1
2
3
4

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

fib(5) ruft fib(4) und fib(3) auf, und fib(4) ruft fib(3) erneut auf. Diese Duplikation summiert sich auf jeder Ebene, also wächst die Zahl der Aufrufe exponentiell mit n (um einen Faktor von etwa 1,6 pro Schritt, meist als die obere Schranke O(2^n) geschrieben). In CPython braucht fib(30) bereits etwa ein Zehntel einer Sekunde und fib(40) über zehn Sekunden.

Die Lösung lässt die Rekursion unangetastet und cacht die Ergebnisse, sodass jede unterschiedliche Eingabe nur einmal berechnet wird:

1
2
3
4
5
6
7

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    if n < 2:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

lru_cache ist ein Decorator. Er umhüllt fib_memo, und wenn sich ein Argument wiederholt, gibt er das gespeicherte Ergebnis zurück, statt den Funktionskörper erneut auszuführen. fib_memo(40) liefert sofort ein Ergebnis.

Die Tiefe ändert sich nicht: fib_memo(40) braucht weiterhin etwa 40 Stapel-Frames. Was sich ändert, ist die Anzahl der Aufrufe, die von exponentiell auf linear sinkt. Sie zahlen O(n) Speicher für den Cache und erhalten O(n) Zeit statt exponentieller Laufzeit.

Rekursion oder Iteration: Was wählen Sie?

Ein Fall verdient mehr als eine Tabellenzeile. Wenn die Rekursionstiefe von einer Eingabe gesteuert wird, der Sie nicht vertrauen, ist das ein Denial-of-Service-Vektor. Ein rekursiver Parser, der pro verschachtelter Klammer in einem vom Nutzer stammenden Text eine Ebene tiefer geht, lässt sich von jedem zum Absturz bringen, der ein paar Tausend [-Zeichen sendet. Begrenzen Sie die Tiefe explizit, oder rekursieren Sie nicht.

Wie Sie eine rekursive Funktion in eine Schleife umwandeln

Der direkte Ersatz für Rekursion über einen Baum ist ein expliziter Stapel: eine list, auf die Sie selbst push und pop anwenden, gesteuert von einer while-Schleife. Hier ist flatten so umgeschrieben:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def flatten_iterative(nested):
    result = []
    stack = [iter(nested)]
    while stack:
        for item in stack[-1]:
            if isinstance(item, list):
                stack.append(iter(item))
                break
            result.append(item)
        else:
            stack.pop()
    return result

Sie liefert dasselbe Ergebnis mit nur einem Stapel-Frame, egal wie tief die Eingabe ist. Die Kosten sind die Verwaltung, die Sie direkt sehen: Der Stapel aus Iteratoren ist genau das, was der Aufrufstapel zuvor für Sie mitführte.

Wenn Sie das nächste Mal eine rekursive Funktion schreiben, fragen Sie sich, wie tief sie werden kann. Ist die Antwort klein und bekannt (eine Konfigurationsdatei, ein UI-Komponentenbaum, ein Parse-Baum für Ihre eigene Grammatik), behalten Sie die Rekursion. Lautet die Antwort „was immer die Eingabe vorgibt", schreiben Sie die Schleife.

Verwandte Artikel

• Big-O-Notation Erklärt mit Code-Beispielen
• Git Bisect: den Commit finden, der einen Bug eingeführt hat