Iterointi vai rekursio — mitkä ovat kompromissit?

Question

Accepted Answer

**Iterointi** käyttää silmukoita; **rekursio** käyttää itseään kutsuvaa kutsua. Ne ovat yhtä tehokkaita (mitä voit tehdä toisella, voit tehdä toisella), mutta ne eroavat selkeydessä ja kustannuksissa.

## Vierekkäin

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

## Vertailu

| Näkökulma | Iterointi | Rekursio |
|--------|-----------|-----------||
| Muisti | O(1) ylimääräinen | O(syvyys) stack |
| Luettavuus | loistava lineaariseen työhön | loistava puille / jaa ja hallitse |
| Riski | ääretön silmukka | stack ylivuoto |
| Nopeus | yleensä nopeampi (ei kutsujen yleiskustannusta) | kutsujen yleiskustannus per kehys |

## Milloin käyttää mitäkin

- Käytä **iterointia** yksinkertaisille lineaarisille läpimenoon ja kun stack-syvyys voi olla suuri.
- Käytä **rekursiota**, kun ongelma on luonnollisesti rekursiivinen (puut, graafit, takaisinotto) ja syvyys on rajattu.

## Sudenkuopat

Syvä rekursio riskii stack ylivuodon; muunna kuuma rekursiivinen koodi iteroinniksi (usein nimenomaisen stackin kanssa) kun syvyys on rajoittamaton.

## Miksi tämä on tärkeää

Oikean tyylin valitseminen pitää koodin sekä oikeana että luettavana.

Rekursio tekee puu- ja graafin koodista tyylikkään, mutta kun tiedät sen muistin kustannukset, voit välttää kaatumisia syvissä tuloksissaan.

Tämä kompromissin arviointi on juuri se, mitä haastattelijat tutkivat kun he pyytävät sinua "muuntamaan tämän iteratiiviseksi."