Iteration vs Rekursion — was sind die Kompromisse?

Question

Accepted Answer

**Iteration** verwendet Schleifen; **Rekursion** verwendet Selbstaufrufe. Sie sind gleich mächtig (alles, was du mit dem einen tun kannst, kannst du mit dem anderen tun), aber sie unterscheiden sich in Klarheit und Kosten.

## Nebeneinander

```python
# Iterative sum: constant extra space
def sum_iter(n):
    total = 0
    for i in range(1, n + 1):
        total += i        # accumulate in a loop
    return total

# Recursive sum: uses the call stack
def sum_rec(n):
    if n == 0:
        return 0
    return n + sum_rec(n - 1)
```

## Vergleich

| Aspekt | Iteration | Rekursion |
|--------|-----------|-----------||
| Speicher | O(1) zusätzlich | O(Tiefe) Stack |
| Lesbarkeit | großartig für lineare Arbeit | großartig für Bäume / Teile-und-Herrsche |
| Risiko | Endlosschleife | Stack-Überlauf |
| Geschwindigkeit | normalerweise schneller (kein Aufrufaufwand) | Aufrufaufwand pro Frame |

## Wann man welche nutzen sollte

- Verwende **Iteration** für einfache lineare Durchläufe und wenn die Stack-Tiefe groß sein könnte.
- Verwende **Rekursion**, wenn das Problem von Natur aus rekursiv ist (Bäume, Graphen, Backtracking) und die Tiefe begrenzt ist.

## Fallstricke

Tiefe Rekursion riskiert Stack-Überlauf; konvertiere heißen rekursiven Code zu Iteration (oft mit einem expliziten Stack), wenn die Tiefe unbegrenzt ist.

## Warum es wichtig ist

Die Wahl des richtigen Stils hält Code sowohl korrekt als auch lesbar.

Rekursion macht Baum- und Graphen-Code elegant, aber das Wissen um ihre Speicherkosten lässt dich Abstürze bei tiefen Eingaben vermeiden.

Diese Kompromissbewertung ist genau das, was Interviewer erforschen, wenn sie dich bitten, "das zu iterativ zu konvertieren."