Iteracija versus rekurzija — kakšni so kompromisi?

Question

Accepted Answer

**Iteracija** uporablja zanke; **rekurzija** uporablja samodejne klice. Sta enako zmogljivi (kar lahko naredite z eno, lahko naredite tudi z drugo), vendar se razlikujeta v jasnosti in ceni.

## Primerjava drug ob drugem

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

## Primerjava

| Vidik | Iteracija | Rekurzija |
|--------|-----------|----------|
| Pomnilnik | O(1) dodatno | O(globina) stack |
| Berljivost | odlično za linearno delo | odlično za drevesa / deljenje in vladavina |
| Tveganje | neskončna zanka | stack overflow |
| Hitrost | običajno hitreje (brez stroškov klica) | stroški klica na okvir |

## Kdaj uporabiti kaj

- Uporabite **iteracijo** za enostavne linearne prevoze in ko je globina stacka lahko velika.
- Uporabite **rekurzijo**, ko je problem naravno rekurziven (drevesa, grafi, backtracking) in je globina omejena.

## Pasti

Globoka rekurzija tvega stack overflow; konvertirajte vroče rekurzivno kodo na iteracijo (pogosto z eksplicitnim stackom), ko je globina neomejena.

## Zakaj je to pomembno

Izbira pravega stila drži kodo pravilno in berljivo.

Rekurzija naredi kodo drevesa in grafa elegantno, toda poznavanje njenih stroškov pomnilnika vam omogoči, da se izognete padcem na globokih vhodih.

Ta kompromis pri presoji je natanko tisto, kar intervjuwarji preiskujejo, ko vas prosijo, da "konvertirate to v iterativno."

Vidik	Iteracija	Rekurzija
Pomnilnik	O(1) dodatno	O(globina) stack
Berljivost	odlično za linearno delo	odlično za drevesa / deljenje in vladavina
Tveganje	neskončna zanka	stack overflow
Hitrost	običajno hitreje (brez stroškov klica)	stroški klica na okvir