Rekursion — Wenn Funktionen sich selbst aufrufen

Einführung

Stell dir vor, du stehst zwischen zwei Spiegeln. Du siehst dein Bild — und darin wieder dein Bild — und darin wieder dein Bild. Das geht im Prinzip unendlich weiter. Das ist das Bild, das viele bei Rekursion im Kopf haben.

In der Informatik ist Rekursion ein Konzept, bei dem eine Funktion sich selbst aufruft — um ein Problem zu lösen, indem es auf kleinere Versionen desselben Problems reduziert wird. Das klingt zunächst zirkulär und seltsam. Aber Rekursion ist eines der mächtigsten Werkzeuge der Programmierung.

Viele Algorithmen — Sortieren (Mergesort), Suchen in Bäumen, Traversieren von Verzeichnissen, Berechnen mathematischer Folgen — werden durch Rekursion elegant und kompakt ausgedrückt. Und das Konzept steckt auch hinter dem Teile-und-Herrsche-Prinzip, das du aus den Sortieralgorithmen kennst.

Grundidee

Eine rekursive Lösung eines Problems hat immer zwei Teile:

1. Basisfall: Die einfachste Version des Problems, die direkt gelöst werden kann — ohne weiteren Selbstaufruf.
2. Rekursiver Fall: Das Problem wird auf eine etwas kleinere Version seiner selbst reduziert, die dann per Selbstaufruf gelöst wird.

Denk an eine Matroschka-Puppe: Um die kleinste Puppe zu finden, nimmst du die äußerste Puppe auf (Basisfall: leere Puppe oder einzige Puppe), sonst öffnest du sie und machst dasselbe mit der nächsten innen (rekursiver Fall).

Erklärung

Fakultät: Ein einfaches Beispiel

Die Fakultät einer natürlichen Zahl n (geschrieben n!) ist das Produkt aller Zahlen von 1 bis n:

• 0! = 1 (per Definition)
• 1! = 1
• 5! = 5 × 4 × 3 × 2 × 1 = 120

Rekursive Definition:

• fakultaet(0) = 1 (Basisfall)
• fakultaet(n) = n × fakultaet(n - 1) (rekursiver Fall)

Wie läuft das ab?

fakultaet(4)
= 4 × fakultaet(3)
= 4 × 3 × fakultaet(2)
= 4 × 3 × 2 × fakultaet(1)
= 4 × 3 × 2 × 1 × fakultaet(0)
= 4 × 3 × 2 × 1 × 1
= 24

Die Funktion ruft sich immer wieder mit kleineren Argumenten auf — bis sie den Basisfall erreicht. Dann werden die Ergebnisse „von unten nach oben” zusammengesetzt.

Der Call Stack

Wie weiß der Computer, wo er weitermachen soll, wenn eine rekursive Funktion zurückkommt?

Der Call Stack (Aufrufstapel) ist ein Speicherbereich, der festhält, welche Funktionsaufrufe gerade aktiv sind. Jedes Mal, wenn eine Funktion aufgerufen wird, wird ein neuer Stack Frame angelegt: er speichert die lokalen Variablen, Parameter und die Rücksprungadresse.

Beim Aufruf von fakultaet(4) schichtet der Stack:

| fakultaet(0) | ← gerade aktiv
| fakultaet(1) |
| fakultaet(2) |
| fakultaet(3) |
| fakultaet(4) |

Wenn fakultaet(0) fertig ist, kehrt es zurück, der Frame wird vom Stapel entfernt, und fakultaet(1) kann weitermachen.

Stack Overflow (Stapelüberlauf)

Was passiert, wenn kein Basisfall existiert — oder die Rekursion zu tief wird?

Der Stack wächst mit jedem Aufruf. Wenn er den verfügbaren Speicher überschreitet, kommt es zu einem Stack Overflow — das Programm bricht mit einem Fehler ab. In Python (und anderen Sprachen) gibt es ein eingebautes Rekursionslimit (oft 1.000 Ebenen), um das zu verhindern.

Deshalb ist der Basisfall unverzichtbar: Er stellt sicher, dass die Rekursion irgendwann endet.

Fibonacci: Ein tückisches Beispiel

Die Fibonacci-Folge: 0, 1, 1, 2, 3, 5, 8, 13, 21, …

Rekursive Definition:

• fib(0) = 0
• fib(1) = 1
• fib(n) = fib(n-1) + fib(n-2)

Das Problem: Diese naive Rekursion berechnet dieselben Werte wieder und wieder.

fib(5)
= fib(4) + fib(3)
= (fib(3) + fib(2)) + (fib(2) + fib(1))
= ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ...

fib(3) wird dabei zweimal berechnet, fib(2) dreimal, fib(1) fünfmal. Die Laufzeit wächst exponentiell — O(2^n). Das ist eine klassische Falle.

Memoization

Die Lösung: Memoization. Speichere jeden berechneten Wert zwischen. Bevor du ihn neu berechnest, schau nach, ob er schon bekannt ist.

Mit Memoization ist Fibonacci in O(n) berechenbar. Das ist eines der wichtigsten Prinzipien der dynamischen Programmierung: Teilergebnisse merken statt neu berechnen.

Rekursion vs. Iteration

Alles, was rekursiv gelöst werden kann, lässt sich auch iterativ (mit Schleifen) lösen — und umgekehrt. Welches ist besser?

Aspekt	Rekursion	Iteration
Lesbarkeit	Oft klarer bei natürlich rekursiven Problemen	Oft klarer bei linearen Abläufen
Speicher	Stack wächst mit Tiefe	Konstanter Speicher möglich
Performance	Overhead durch Funktionsaufrufe	Effizienter bei einfachen Schleifen
Stack Overflow	Risiko bei tiefer Rekursion	Kein Stack Overflow

Faustregel: Rekursion, wenn das Problem natürlich hierarchisch oder selbstähnlich ist (Bäume, Teile-und-Herrsche). Iteration für einfache Wiederholungen.

Divide and Conquer

Rekursion ist das Werkzeug hinter dem Teile-und-Herrsche-Prinzip: Teile ein Problem in Teilprobleme, löse jedes Teilproblem rekursiv, kombiniere die Lösungen. Das ist das Grundprinzip von Mergesort, Quicksort, binärer Suche und vielen anderen effizienten Algorithmen.

Beispiel aus dem Alltag

Verzeichnisstruktur durchsuchen:

Wenn du auf einem Computer alle Dateien mit der Endung .pdf suchst, geht das rekursiv:

durchsuche(Ordner):
  für jede Datei in Ordner:
    wenn Datei.endung == ".pdf": gib sie aus
  für jeden Unterordner in Ordner:
    durchsuche(Unterordner)   ← rekursiver Aufruf

Der Basisfall ist implizit: Ein Ordner ohne Unterordner löst keinen weiteren Selbstaufruf aus. Iterativ müsste man eine eigene Stapelstruktur verwalten — das wäre weniger lesbar.

Fraktale:

Fraktale wie das Sierpinski-Dreieck entstehen durch Rekursion: Teile ein Dreieck in drei kleinere, und mache dasselbe mit jedem kleineren Dreieck — bis zu einer Mindestgröße (Basisfall). Unendlich viele Ebenen ergeben eine selbstähnliche Struktur mit fraktaler Geometrie.

Menüs und Baumstrukturen:

Ein Navigationsmenü mit Untermenüs, Sub-Untermenüs und weiteren Ebenen — das ist ein Baum. Ihn zu rendern bedeutet, jeden Knoten zu besuchen und seine Kinder ebenfalls zu besuchen. Das ist rekursive Baumtraversierung.

Anwendung

Schreibe (oder denke durch) eine rekursive Funktion für folgende Aufgabe:

Potenzrechnung: Berechne a hoch n (a^n) rekursiv.

• Was ist der Basisfall?
• Was ist der rekursive Fall?
• Tipp: a^n = a × a^(n-1), und a^0 = 1.

Bonus: Überlege, wie man das effizienter machen kann. Hinweis: a^8 = (a^4)^2 — das ist nur eine Rekursionsebene, nicht acht.

Typische Fehler

Basisfall vergessen: Ohne Basisfall läuft die Rekursion unendlich — bis zum Stack Overflow. Das ist der häufigste Fehler bei rekursiven Programmen.

Falsche Reduktion: Der rekursive Aufruf muss das Problem wirklich verkleinern. Wenn f(n) → f(n) (statt f(n-1)) aufgerufen wird, endet das nie.

Naive Fibonacci für große n: fib(50) ohne Memoization berechnet ~10^10 Einzelaufrufe. Das dauert Ewigkeiten. Mit Memoization: 50 Aufrufe.

Rekursion immer bevorzugen: Manche Probleme sind mit Schleifen klarer und sparsamer. Nicht jede Rekursion ist eleganter als eine Schleife — besonders wenn der Stack tief wird.

Zusammenfassung

• Rekursion bedeutet: Eine Funktion löst ein Problem, indem sie sich selbst mit einer kleineren Version aufruft
• Jede Rekursion braucht einen Basisfall (terminiert die Kette) und einen rekursiven Fall (reduziert das Problem)
• Der Call Stack speichert alle aktiven Aufruf-Frames; zu tiefe Rekursion führt zu Stack Overflow
• Naive Fibonacci ist ein Beispiel für ineffiziente Rekursion; Memoization bringt es von O(2^n) auf O(n)
• Rekursion ist das Werkzeug hinter Teile-und-Herrsche-Algorithmen wie Mergesort und binärer Suche
• Iteration und Rekursion sind equivalent in Ausdrucksstärke; die Wahl hängt von Lesbarkeit und Effizienz ab

Quiz

Frage 1: Was sind Basisfall und rekursiver Fall — und warum ist der Basisfall unverzichtbar?

Frage 2: Was ist ein Call Stack — und was passiert bei einem Stack Overflow?

Frage 3: Warum ist die naive rekursive Fibonacci-Berechnung ineffizient — und wie löst Memoization das Problem?

Frage 4: Wann ist Rekursion gegenüber Iteration vorzuziehen?