Rekursion verstehen: Wenn Funktionen sich selbst aufrufen

Manche Konzepte in der Programmierung fühlen sich beim ersten Kontakt wie ein kleiner Zaubertrick an. Rekursion gehört definitiv dazu: eine Funktion, die sich selbst aufruft, um ein Problem zu lösen. Klingt paradox – wie soll eine Funktion jemals fertig werden, wenn sie sich ständig neu startet? In diesem Beitrag entzaubern wir die Rekursion Schritt für Schritt, schauen hinter die Kulissen und du wirst sehen, dass dahinter ein erstaunlich elegantes Prinzip steckt.

Was ist Rekursion?

Rekursion bedeutet, dass ein Problem gelöst wird, indem man es auf eine kleinere Version desselben Problems zurückführt. Statt eine Aufgabe in einem Rutsch zu erledigen, zerlegst du sie in einen winzigen Teil, den du sofort beantworten kannst, und einen Rest, der genauso aussieht wie das ursprüngliche Problem – nur ein bisschen kleiner.

Ein anschauliches Bild sind russische Matrjoschka-Puppen: Du öffnest eine Puppe und findest darin eine kleinere Puppe, die du nach demselben Verfahren öffnest. Irgendwann stößt du auf die kleinste Puppe, die sich nicht mehr öffnen lässt – und genau dieser Punkt ist in der Programmierung entscheidend.

Basisfall und Rekursionsfall: die zwei Pflichtbausteine

Jede korrekte rekursive Funktion besteht aus zwei Teilen:

• Der Basisfall (engl. base case) ist die Abbruchbedingung. Er beantwortet die kleinste, einfachste Variante des Problems direkt – ohne einen weiteren rekursiven Aufruf.
• Der Rekursionsfall ruft die Funktion erneut auf, allerdings mit einem Argument, das dem Basisfall einen Schritt näher kommt.

Fehlt der Basisfall oder wird er nie erreicht, läuft die Funktion endlos weiter. Schauen wir uns das am Klassiker schlechthin an – der Fakultät einer Zahl (5! = 5 · 4 · 3 · 2 · 1):

def fakultaet(n):
    if n <= 1:                    # Basisfall
        return 1
    return n * fakultaet(n - 1)   # Rekursionsfall

print(fakultaet(5))  # 120

Der Basisfall ist hier n <= 1: Die Fakultät von 1 ist 1, hier endet die Kette. Im Rekursionsfall multiplizieren wir n mit dem Ergebnis von fakultaet(n - 1) – dem exakt gleichen Problem, nur für eine kleinere Zahl.

Der Aufrufstack: was hinter den Kulissen passiert

Um Rekursion wirklich zu verstehen, hilft ein Blick auf den Aufrufstack (call stack). Jeder Funktionsaufruf wird vom Programm auf einen Stapel gelegt und erst dann endgültig abgearbeitet, wenn die in ihm enthaltenen Aufrufe zurückgekehrt sind. Nehmen wir eine Funktion, die die Summe einer Liste bildet:

def summe(zahlen):
    if not zahlen:                # Basisfall: leere Liste
        return 0
    return zahlen[0] + summe(zahlen[1:])

print(summe([1, 2, 3, 4]))  # 10

Bei summe([1, 2, 3, 4]) türmen sich die Aufrufe zunächst auf: 1 + summe([2, 3, 4]) wartet auf 2 + summe([3, 4]), das wiederum auf 3 + summe([4]) wartet und so weiter. Erst wenn der Basisfall mit der leeren Liste eine 0 zurückgibt, löst sich der Stapel von oben nach unten wieder auf und die Teilergebnisse werden zusammengerechnet.

Wichtig zu wissen: Dieser Stapel hat eine begrenzte Tiefe. Python bricht standardmäßig nach rund 1000 verschachtelten Aufrufen mit einem RecursionError ab, um einen echten Programmabsturz zu verhindern.

Rekursion in der Praxis: verschachtelte Strukturen durchlaufen

Rekursion ist kein reines Lehrbuch-Thema. Sie glänzt überall dort, wo Daten selbst eine verschachtelte, baumartige Struktur haben. Eine einfache Schleife stößt hier schnell an Grenzen, weil sie nicht weiß, wie tief die Verschachtelung reicht. Eine rekursive Funktion ist dagegen die natürliche Lösung – etwa um eine beliebig tief verschachtelte Liste flach zu klopfen:

def flatten(liste):
    ergebnis = []
    for element in liste:
        if isinstance(element, list):
            ergebnis.extend(flatten(element))  # rekursiver Abstieg
        else:
            ergebnis.append(element)
    return ergebnis

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

Die Funktion läuft durch jedes Element. Ist es selbst eine Liste, steigt sie per flatten(element) eine Ebene tiefer hinab; andernfalls landet der Wert direkt im Ergebnis. Egal wie tief die Schachtelung – der Code bleibt kurz und lesbar. Typische Einsatzgebiete sind:

• Baum- und Graphstrukturen wie Dateisysteme, JSON-Daten oder das DOM einer Webseite
• Teile-und-herrsche-Algorithmen wie Quicksort oder die binäre Suche
• Mathematische Definitionen, die selbst rekursiv formuliert sind

Typische Fallstricke: Endlosrekursion und Performance

So elegant Rekursion ist – zwei Stolpersteine solltest du kennen. Der erste ist die Endlosrekursion: Vergisst du den Basisfall oder näherst dich ihm nie an, läuft die Funktion bis zum RecursionError. Prüfe deshalb bei jeder rekursiven Funktion zuerst, ob es eine klare Abbruchbedingung gibt und ob das Argument bei jedem Aufruf wirklich kleiner wird.

Der zweite Stolperstein ist die Performance. Die berühmte Fibonacci-Folge lässt sich wunderbar rekursiv ausdrücken, ist in der naiven Variante aber eine Falle:

def fib(n):
    if n < 2:                 # Basisfall: fib(0)=0, fib(1)=1
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(10))  # 55

Das Problem: fib(10) berechnet fib(8) mehrfach, fib(7) noch öfter – die Zahl der Aufrufe wächst exponentiell. Schon fib(40) dauert spürbar lange. Die Lösung heißt Memoisierung: Wir merken uns bereits berechnete Ergebnisse. In Python genügt dafür ein einziger Dekorator aus der Standardbibliothek:

from functools import lru_cache

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

print(fib(50))  # 12586269025 – in Millisekunden statt Minuten

Mit @lru_cache wird jedes Ergebnis nur einmal berechnet und danach aus einem Zwischenspeicher geholt. Aus einer quälend langsamen Funktion wird so eine, die selbst fib(50) in Sekundenbruchteilen liefert.

Fazit

Rekursion ist kein Selbstzweck und keine Magie, sondern eine Denkweise: Zerlege ein Problem in eine kleinere Version seiner selbst und definiere einen klaren Punkt, an dem Schluss ist. Mit einem sauberen Basisfall und einem Rekursionsfall, der diesem Basisfall näher kommt, hast du das Werkzeug bereits in der Hand. Behalte den Aufrufstack im Hinterkopf, hüte dich vor Endlosrekursion und greife bei teuren Berechnungen zur Memoisierung. Am besten verinnerlichst du das Prinzip, indem du es selbst ausprobierst – schreib die Fakultät, die Listensumme oder einen Verzeichnis-Durchlauf einmal von Hand nach. Sobald es bei dir „Klick" macht, willst du Rekursion nicht mehr missen.