rekursion

Recursion (Rekursion)

Kurz: Eine Technik, bei der eine Funktion sich selbst aufruft, um ein Problem zu lösen, indem es in kleinere, gleichartige Teilprobleme zerlegt wird.

Genauer: Jede rekursive Funktion braucht einen Abbruchfall (Basisfall), der ohne weiteren rekursiven Aufruf direkt beantwortet wird — fehlt dieser, ruft sich die Funktion endlos selbst auf, bis der Speicher (Stack) überläuft. Viele rekursive Lösungen lassen sich auch iterativ mit einer Schleife umsetzen; Rekursion ist oft eleganter lesbar, iterative Lösungen sind meist speicher- und performanceschonender.

Im Detail

Das klassische Einstiegsbeispiel ist die Fakultät (n! = n × (n-1) × (n-2) × ... × 1):

def fakultaet(n):
    if n <= 1:              # Basisfall - stoppt die Rekursion
        return 1
    return n * fakultaet(n - 1)   # rekursiver Aufruf mit kleinerem Problem
 
fakultaet(5)  # 5 * fakultaet(4) = 5 * (4 * fakultaet(3)) = ... = 120

Jeder rekursive Aufruf legt einen neuen “Stack Frame” auf den Aufrufstapel — er merkt sich, wo im Code weitergemacht werden muss, sobald der tiefere Aufruf sein Ergebnis zurückliefert. Bei fakultaet(5) entstehen so fünf verschachtelte, noch nicht abgeschlossene Aufrufe, bevor der Basisfall erreicht wird und sich die Kette rückwärts wieder “auflöst”.

Fehlt der Basisfall oder wird er nie erreicht (z. B. weil sich das Argument nicht in die richtige Richtung verändert), wächst dieser Stapel unbegrenzt — bis der verfügbare Speicher erschöpft ist und das Programm mit einem “Stack Overflow” abstürzt. Das ist der rekursive Bruder der Endlosschleife.

Manche Probleme lassen sich sowohl rekursiv als auch mit einer Schleife lösen — beide Varianten der Fakultät im Vergleich:

# Iterativ - kein zusätzlicher Stack-Verbrauch
def fakultaet_iterativ(n):
    ergebnis = 1
    for i in range(2, n + 1):
        ergebnis *= i
    return ergebnis

Rekursion glänzt vor allem bei Problemen, die sich NATÜRLICH in gleichartige Teilprobleme zerlegen lassen (Baumstrukturen durchlaufen, Divide-and-Conquer-Algorithmen wie Quick Sort, mathematische Definitionen wie die Fibonacci-Folge) — dort ist rekursiver Code oft deutlich kürzer und näher an der mathematischen Definition als die iterative Variante. Bei einfachen, linearen Wiederholungen (z. B. “zähle von 1 bis n”) ist eine Schleife dagegen fast immer klarer UND ressourcenschonender, weil sie keinen zusätzlichen Stack-Speicher pro Durchlauf benötigt.

Siehe auch: Schleifen, Algorithms