Iterazione vs ricorsione — quali sono i compromessi?

Question

IT Interview Practice · Accepted Answer

**L'iterazione** usa cicli; **la ricorsione** usa auto-chiamate. Sono ugualmente potenti (qualsiasi cosa tu possa fare con una puoi farla con l'altra), ma differiscono in chiarezza e costo.

## Confronto diretto

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

## Confronto

| Aspetto | Iterazione | Ricorsione |
|--------|-----------|-----------|  
| Memoria | O(1) extra | O(profondità) stack |
| Leggibilità | ottima per lavoro lineare | ottima per alberi / divide-and-conquer |
| Rischio | ciclo infinito | stack overflow |
| Velocità | solitamente più veloce (nessun overhead di chiamata) | overhead di chiamata per frame |

## Quando usare quale

- Usa **iterazione** per attraversamenti lineari semplici e quando la profondità dello stack potrebbe essere grande.
- Usa **ricorsione** quando il problema è naturalmente ricorsivo (alberi, grafi, backtracking) e la profondità è limitata.

## Insidie

La ricorsione profonda rischia lo stack overflow; converti il codice ricorsivo critico in iterazione (spesso con uno stack esplicito) quando la profondità è illimitata.

## Perché è importante

Scegliere lo stile giusto mantiene il codice sia corretto che leggibile.

La ricorsione rende il codice di alberi e grafi elegante, ma conoscere il suo costo di memoria ti permette di evitare crash su input profondi.

Questo giudizio di compromesso è esattamente quello che i colloquiatori sondano quando ti chiedono di "convertire questo a iterativo."

Aspetto	Iterazione	Ricorsione
Memoria	O(1) extra	O(profondità) stack
Leggibilità	ottima per lavoro lineare	ottima per alberi / divide-and-conquer
Rischio	ciclo infinito	stack overflow
Velocità	solitamente più veloce (nessun overhead di chiamata)	overhead di chiamata per frame

Confronto diretto

Confronto

Quando usare quale

Insidie

Perché è importante

Domande correlate