Rekursion ist eine besondere Programmiertechnik, bei der sich eine Funktion selbst aufruft, um ein Problem zu lösen.
Zunächst kann diese Idee wie Magie oder ein wenig seltsam erscheinen, aber sie ist ein sehr mächtiges Werkzeug, sobald man sie versteht.

Stell dir vor, du schaust in zwei sich gegenüberstehende Spiegel. Du siehst eine Spiegelung innerhalb einer Spiegelung, die immer weitergeht … bis sie schließlich verblasst. Bei der Rekursion ist dieses "Verblassen" entscheidend — wir nennen es den Basisfall, und er stoppt die Wiederholung.

Wie Rekursion funktioniert

Eine rekursive Funktion:

1. Prüft, ob sie stoppen soll — das ist der Basisfall.
2. Wenn nicht, ruft sie sich selbst auf, aber mit einer kleineren oder einfacheren Version des ursprünglichen Problems.

Indem das Problem immer wieder in kleinere Teile zerlegt wird, kann die Rekursion die einfachste Version des Problems erreichen, diese lösen und dann die Antwort schrittweise zurückgeben, während sie von den Aufrufen zurückkehrt.

Beispiel: Fakultätsberechnung

Nehmen wir die Fakultät einer Zahl.
In der Mathematik bedeutet die Fakultät von n (geschrieben als n!):

n! = n × (n-1) × (n-2) × ... × 1

Zum Beispiel:

5! = 5 × 4 × 3 × 2 × 1 = 120

Hier die rekursive Version in Python:

def factorial(n):
    if n == 0:  # Basisfall
        return 1
    return n * factorial(n - 1)

print(factorial(5))  # 120

Was hier passiert:

• Wenn n 0 ist, haben wir den Basisfall erreicht — per Definition ist 0! gleich 1.
• Andernfalls multipliziere n mit factorial(n - 1) (einer kleineren Version desselben Problems).
• Dies wiederholt sich, bis der Basisfall erreicht ist.

Warum Rekursion verwenden?

Rekursion kann:

• Elegant und prägnant sein bei Problemen, die von Natur aus eine wiederholende Struktur haben.
• Perfekt für mathematische Probleme wie Fakultäten oder Fibonacci-Zahlen.
• Unverzichtbar für Navigation durch baumartige Datenstrukturen (Dateisysteme, Stammbäume, Spiel-KI-Suche).

Manchmal kann Rekursion sogar Schleifen ersetzen, obwohl sie nicht immer die effizienteste Methode ist.

TIPP: Rekursion ist oft leichter zu verstehen, wenn man sie als „Teile das Problem in kleinere Versionen, bis du es direkt lösen kannst“ sieht.

Häufige Fallstricke

WICHTIG!: Definiere immer einen Basisfall — ohne ihn ruft die Funktion sich endlos selbst auf, bis Python einen RecursionError wirft.

Fehlerbehebung:

• „RecursionError: maximum recursion depth exceeded“ → Du hast den Basisfall nicht erreicht oder der Basisfall ist falsch definiert.
• Wenn Rekursion zu komplex für das Problem erscheint, versuche stattdessen eine Schleife.

Rekursion kann anfangs verwirrend erscheinen, ist aber einfach eine andere Methode, deinen Code intelligenter und anpassungsfähiger zu machen. Sobald du sie an ein paar Problemen geübt hast, wirst du sehen, dass sie nicht nur mächtig ist, sondern auch deinen Code überraschend kurz und elegant machen kann.