Iteration vs rekursion — hvad er kompromiserne?

Question

Accepted Answer

**Iteration** bruger løkker; **rekursion** bruger selvkald. De er lige så kraftfulde (alt hvad du kan gøre med det ene kan du gøre med det andet), men de adskiller sig i klarhed og omkostning.

## Side om side

```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)
```

## Sammenligning

| Aspekt | Iteration | Rekursion |
|--------|-----------|-----------||
| Hukommelse | O(1) ekstra | O(dybde) stack |
| Læsbarhed | fantastisk til lineært arbejde | fantastisk til træer / del-og-erobring |
| Risiko | uendelig løkke | stack overflow |
| Hastighed | normalt hurtigere (ingen opkaldsforbrug) | opkaldsforbrug pr. ramme |

## Hvornår skal man bruge hvad

- Brug **iteration** til enkle lineære gennemgange og når stakdybden kunne være stor.
- Brug **rekursion** når problemet er naturligt rekursivt (træer, grafer, backtracking) og dybden er afgrænset.

## Faldgruber

Dyb rekursion risikerer stack overflow; konverter hot rekursiv kode til iteration (ofte med en eksplicit stack) når dybden er ubegrænset.

## Hvorfor det betyder noget

At vælge den rigtige stil holder koden både korrekt og læsbar.

Rekursion gør træ- og grafkode elegant, men ved at kende dens hukommelsesomkostning kan du undgå styrt på dybe input.

Denne vurdering af kompromis er præcis hvad interviewere sonder når de beder dig om at "konvertere dette til iterativt."