Python-Rekursion

Rekursion ist eine Technik, bei der eine Funktion sich selbst aufruft, um ein Problem zu lösen, indem es in kleinere, identische Teilprobleme aufgeteilt wird. Jeder Aufruf arbeitet an einer einfacheren Version des ursprünglichen Problems, bis ein trivialer Fall erreicht wird — der Basisfall — der direkt beantwortet werden kann.

Dieses Kapitel behandelt:

• Wie Rekursion funktioniert und wie der Call-Stack aussieht
• Basisfall und rekursiver Fall
• Klassische rekursive Probleme: Fakultät, Fibonacci, Potenz, Flatten
• Rekursion vs. Iteration — wann welche zu wählen ist
• Pythons Rekursionslimit und wie man damit umgeht
• Memoization mit functools.lru_cache

Wie Rekursion funktioniert

Wenn eine Funktion sich selbst aufruft, legt Python für jeden Aufruf einen neuen Stack-Frame auf den Call-Stack. Jeder Frame behält seine eigenen lokalen Variablen. Sobald der Basisfall erreicht wird, beginnen die Frames in umgekehrter Reihenfolge zurückzukehren — last in, first out — bis der ursprüngliche Aufruf seine endgültige Antwort erhält.

Eine gültige rekursive Funktion hat immer zwei Teile:

Ohne einen Basisfall (oder mit einem, der niemals erreicht wird) ruft die Funktion sich selbst endlos auf und Python löst einen RecursionError aus.

Ein einfaches Beispiel: Countdown

Die folgende Funktion zählt von n bis null herunter und gibt dann "Go!" aus. Sie ist leicht nachzuverfolgen, da jeder Aufruf n um eins reduziert, bis n <= 0.

def countdown(n):
    if n <= 0:         # base case
        print("Go!")
        return
    print(n)
    countdown(n - 1)   # recursive case

countdown(5)

Ausgabe:

5
4
3
2
1
Go!

Ablauf des Call-Stacks:

1. countdown(5) gibt 5 aus, ruft countdown(4) auf
2. countdown(4) gibt 4 aus, ruft countdown(3) auf
3. … und so weiter …
4. countdown(0) gibt "Go!" aus und kehrt zurück — das Abwickeln beginnt

Fakultät

Die Fakultät von n (geschrieben n!) ist das Produkt aller positiven ganzen Zahlen bis n. Sie ist rekursiv definiert als:

• 0! = 1 (Basisfall)
• n! = n × (n − 1)! (rekursiver Fall)

def factorial(n):
    if n == 0 or n == 1:   # base case
        return 1
    return n * factorial(n - 1)

print(factorial(5))    # 120
print(factorial(0))    # 1
print(factorial(10))   # 3628800

factorial(5) entfaltet sich so, bevor ein Wert zurückgegeben wird:

factorial(5)
  5 * factorial(4)
        4 * factorial(3)
              3 * factorial(2)
                    2 * factorial(1)
                          1          ← base case

Dann finden die Multiplikationen auf dem Rückweg statt: 1 → 2 → 6 → 24 → 120.

Fibonacci-Folge

Die Fibonacci-Folge ist definiert durch: Jede Zahl ist die Summe der beiden vorherigen — 0, 1, 1, 2, 3, 5, 8, 13, …

def fibonacci(n):
    if n <= 0:   # base case
        return 0
    if n == 1:   # base case
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

for i in range(8):
    print(fibonacci(i), end=" ")
# Output: 0 1 1 2 3 5 8 13

Dies ist korrekt, aber langsam für große n — fibonacci(40) macht Millionen redundanter Aufrufe. Siehe Memoization weiter unten für die Lösung.

Summe einer Liste

Rekursion funktioniert auf Listen natürlich: Verarbeite das erste Element, dann rekurriere auf den Rest.

def sum_list(lst):
    if not lst:              # base case — empty list
        return 0
    return lst[0] + sum_list(lst[1:])

print(sum_list([1, 2, 3, 4, 5]))   # 15
print(sum_list([]))                 # 0

lst[1:] erstellt eine neue Liste mit dem ersten entfernten Element, wodurch das Problem jedes Mal um ein Element kleiner wird.

Eine Zahl potenzieren

def power(base, exp):
    if exp == 0:          # base case: anything to the power 0 is 1
        return 1
    return base * power(base, exp - 1)

print(power(2, 10))   # 1024
print(power(3, 4))    # 81
print(power(5, 0))    # 1

Eine verschachtelte Liste glätten

Manche Probleme sind von Natur aus rekursiv — sie haben auf jeder Ebene dieselbe Struktur. Das Glätten einer beliebig tief verschachtelten Liste ist eines davon.

def flatten(lst):
    result = []
    for item in lst:
        if isinstance(item, list):
            result.extend(flatten(item))   # recurse into sublists
        else:
            result.append(item)
    return result

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

Dies ist mit Iteration allein schwer sauber zu schreiben, da die Verschachtelungstiefe unbekannt ist.

Rekursion vs. Iteration

Die meisten rekursiven Algorithmen können als iterative Schleifen umgeschrieben werden und umgekehrt.

Iterative Fakultät

def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print(factorial_iterative(5))   # 120

Richtlinie: Wähle Rekursion, wenn sich das Problem natürlich in kleinere identische Teilprobleme zerlegt und die Tiefe moderat ist. Wähle Iteration, wenn du hohe Leistung benötigst oder die Tiefe groß sein könnte.

Pythons Rekursionslimit

Python begrenzt den Call-Stack standardmäßig auf 1 000 Frames, um zu verhindern, dass ein Stack-Überlauf den Prozess zum Absturz bringt.

import sys
print(sys.getrecursionlimit())   # 1000

Wenn deine Funktion dieses Limit überschreitet, siehst du:

RecursionError: maximum recursion depth exceeded

Du kannst das Limit mit sys.setrecursionlimit(n) erhöhen, aber tue dies mit Bedacht — ein sehr tiefer Stack kann den Systemspeicher erschöpfen. Bei tatsächlich tiefer Rekursion schreibe den Algorithmus iterativ um oder verwende Python-Generatoren, um einen Stack manuell zu simulieren.

Memoization

Naive rekursive Fibonacci-Implementierungen sind exponentiell langsam, weil sie dieselben Teilprobleme immer wieder lösen. Memoization speichert das Ergebnis jedes eindeutigen Aufrufs zwischen, sodass es nur einmal berechnet wird.

Manueller Cache mit einem Dictionary

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 0:
        return 0
    if n == 1:
        return 1
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

print(fibonacci(10))   # 55
print(fibonacci(30))   # 832040

Verwendung von functools.lru_cache

Die Standardbibliothek stellt einen Decorator bereit, der das Caching automatisch übernimmt:

from functools import lru_cache

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

print(fibonacci(10))   # 55
print(fibonacci(50))   # 12586269025

@lru_cache macht aus einem ansonsten exponentiellen Algorithmus einen linearen Algorithmus mit null zusätzlichem Code im Funktionskörper. Es ist der idiomatische Python-Ansatz zum Memoizen reiner rekursiver Funktionen.

Binäre Suche (Rekursiv)

Die binäre Suche ist ein klassischer Divide-and-Conquer-Algorithmus: Vergleiche das Ziel mit dem mittleren Element, dann rekurriere auf die linke oder rechte Hälfte.

def binary_search(lst, target, low=0, high=None):
    if high is None:
        high = len(lst) - 1
    if low > high:        # base case: search space exhausted
        return -1
    mid = (low + high) // 2
    if lst[mid] == target:
        return mid
    elif lst[mid] < target:
        return binary_search(lst, target, mid + 1, high)
    else:
        return binary_search(lst, target, low, mid - 1)

nums = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(nums, 7))    # 3
print(binary_search(nums, 1))    # 0
print(binary_search(nums, 15))   # 7
print(binary_search(nums, 4))    # -1  (not found)

Häufige Fallstricke

Fehlender Basisfall

# This will raise RecursionError
def broken(n):
    return n * broken(n - 1)   # no base case!

Frage immer: „Was ist die einfachste Eingabe, die diese Funktion ohne Selbstaufruf behandeln muss?"

Endlose Rekursion durch einen falschen Basisfall

# factorial of a negative number loops forever
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)   # n goes -1, -2, -3 ...

# Fix: guard at the top
def factorial(n):
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return 1
    return n * factorial(n - 1)

Mutabler Standardparameter als Memo

Die Verwendung von memo={} als Standardparameter ist praktisch, teilt aber den Zustand über alle Aufrufe auf oberster Ebene hinweg. Übergebe den Cache für Produktionscode explizit oder verwende @lru_cache.

Wann Rekursion verwendet werden sollte

Rekursion eignet sich natürlich für:

• Baum- und Graphentraversierung — Verzeichnislisten, DOM-Traversierung, Entscheidungsbäume
• Divide-and-Conquer-Algorithmen — Merge Sort, Quicksort, binäre Suche
• Mathematische Definitionen — Fakultät, Fibonacci, Kombinatorik
• Backtracking — Lösen von Labyrinthen, Sudoku, Permutationsgenerierung
• Verschachtelte Datenstrukturen — JSON/XML-Parsing, Glätten verschachtelter Listen

Für einfache sequentielle Schleifen oder große Tiefen bevorzuge for-Schleifen oder while-Schleifen.

Verwandte Kapitel

• Python-Funktionen — die Bausteine, auf denen Rekursion aufbaut
• Python-Scope — verstehen, wie lokale Variablen in jedem Frame funktionieren
• Python-While-Schleifen — die iterative Alternative
• Python-Generatoren — speichereffiziente Alternativen für Sequenzen
• Python-Iteratoren — das Iterationsprotokoll, das Pythons Schleifenmodell zugrunde liegt
• Python-Try-Except — RecursionError elegant behandeln

Übungen