Was ist Rekursion?

Question

Was ist Rekursion?

Accepted Answer

**Rekursion** ist, wenn eine Funktion sich selbst aufruft, um eine kleinere Version desselben Problems zu lösen. Jede Rekursion benötigt einen **Basisfall (base case)**, der sie stoppt, und einen **rekursiven Fall (recursive case)**, der sich dem Basisfall annähert.

## Die Idee

Teilen Sie ein Problem in kleinere identische Unterproblem auf. Jeder Aufruf legt einen Frame auf dem **Call Stack** ab; Rückgaben entfernen sie wieder.

## Beispiel

```python
def factorial(n):
    if n <= 1:            # base case: stop recursing
        return 1
    return n * factorial(n - 1)   # recursive case: smaller problem

factorial(4)             # 4 * 3 * 2 * 1 -> 24
```

## Verfolgung

```text
factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * 3 * 2 * 1 = 24
```

## Komplexität

Hier **O(n)** Zeit und **O(n)** Stack-Speicher (ein Frame pro Aufruf).

## Fallstricke

- **Fehlender Basisfall** -> unendliche Rekursion -> Stack-Überlauf.
- Tiefe Rekursion kann den Stack erschöpfen; einige Sprachen unterstützen keine Tail-Call-Optimierung.
- Die Neuberechnung überlappender Unterproblem kann zu exponentieller Zeit führen (mit Memoization beheben).

## Warum es wichtig ist

Rekursion drückt natürlicherweise selbstähnliche Probleme aus — Bäume, Graphen, Divide and Conquer — viel sauberer als Schleifen.

Sie ist das gedankliche Modell hinter Merge Sort, Backtracking und dynamischer Programmierung.

Das Verständnis des Call Stack macht Sie auch besser beim Debuggen und beim Denken über Speicher.