Rekursion: Wenn eine Funktion sich selbst aufruft

Rekursion ist eine Programmiertechnik, bei der sich eine Funktion direkt oder indirekt selbst aufruft, um ein Problem in kleinere Teilprobleme zu zerlegen. Sie ist eine elegante Alternative zu Schleifen und besonders stark bei Problemen mit verschachtelter Struktur, etwa Baum- oder Verzeichnisdurchläufen.

Wie funktioniert Rekursion?

Eine rekursive Funktion besteht aus zwei Teilen: einem Basisfall (Abbruchbedingung), der die Kette beendet, und einem Rekursionsschritt, der das Problem verkleinert und die Funktion erneut aufruft. Ohne Basisfall läuft die Funktion endlos und endet mit einem Stack-Überlauf.

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

print(fakultaet(5))   # 120

Rekursion vs. Iteration

  • Rekursion: liest sich oft klarer und näher an der mathematischen Definition, braucht aber pro Aufruf Speicher auf dem Aufrufstapel (Stack).
  • Iteration (Schleifen wie for/while): spart Speicher und ist bei vielen Sprachen schneller, kann aber unübersichtlicher werden.
  • Manche Sprachen optimieren „Endrekursion" (Tail Recursion) automatisch zu einer Schleife — bei anderen (z.B. Python) führt sehr tiefe Rekursion zu einem RecursionError.

Typische Einsatzgebiete

  • Durchlaufen von Bäumen (z.B. Dateisysteme, DOM, Suchbäume)
  • Sortier- und Suchalgorithmen (Quicksort, Mergesort, Binäre Suche)
  • Backtracking (z.B. Labyrinth-Lösung, Schach)
  • Mathematische Definitionen (Fakultät, Fibonacci, Fraktale)

Praktische Tipps

  • Immer einen klaren Basisfall definieren, der garantiert erreicht wird.
  • Vor dem Einsatz die maximale Rekursionstiefe der Sprache prüfen.
  • Für einfache Zählprobleme ist eine Schleife oft die robustere Wahl.

Verwandte Grundlagen: Algorithmus, Stack, Callback.