Iteracija prema rekurziji — koji su trade-off-ovi?

Question

Accepted Answer

**Iteracija** koristi petlje; **rekurzija** koristi samopozive. Jednako su moćne (sve što možeš učiniti s jednom, možeš učiniti s drugom), ali se razlikuju u jasnoći i trošku.

## Uporedo

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

## Usporedba

| Aspekt | Iteracija | Rekurzija |
|--------|-----------|----------|
| Memorija | O(1) dodatno | O(dubina) stack |
| Čitljivost | odličan za linearni rad | odličan za stabla / podijeli-pa-vladaj |
| Rizik | beskonačna petlja | stack overflow |
| Brzina | obično brži (bez overhead poziva) | overhead poziva po okviru |

## Kada koristiti što

- Koristi **iteraciju** za jednostavne linearne prelazke i kada bi dubina stack-a mogla biti velika.
- Koristi **rekurziju** kada je problem prirodno rekurzivan (stabla, grafovi, vraćanje) i dubina je ograničena.

## Zamke

Duboka rekurzija rizira stack overflow; pretvori vrući rekurzivni kod u iteraciju (često sa eksplicitnim stack-om) kada je dubina neograničena.

## Zašto je to važno

Odabir pravilnog stila čini kod ispravnim i čitljivim.

Rekurzija čini kod stabla i grafa elegantnima, ali poznavanje njezine memorijske cijene omogućava ti da izbjegneš rušenja na dubokim ulazima.

Ova procjena trade-off-a je upravo ono što interviewer-i istražuju kada te pitaju "pretvori ovo u iterativno."

Aspekt	Iteracija	Rekurzija
Memorija	O(1) dodatno	O(dubina) stack
Čitljivost	odličan za linearni rad	odličan za stabla / podijeli-pa-vladaj
Rizik	beskonačna petlja	stack overflow
Brzina	obično brži (bez overhead poziva)	overhead poziva po okviru