Iteración vs recursión — ¿cuáles son los compromisos?

Question

Accepted Answer

**Iteración** utiliza bucles; **recursión** utiliza llamadas recursivas. Son igualmente poderosos (cualquier cosa que puedas hacer con uno puedes hacerlo con el otro), pero difieren en claridad y costo.

## Lado a lado

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

## Comparación

| Aspecto | Iteración | Recursión |
|--------|-----------|-----------||
| Memoria | O(1) adicional | O(profundidad) stack |
| Legibilidad | excelente para trabajo lineal | excelente para árboles / divide y vencerás |
| Riesgo | bucle infinito | desbordamiento de stack |
| Velocidad | normalmente más rápido (sin overhead de llamadas) | overhead de llamadas por frame |

## Cuándo usar cuál

- Usa **iteración** para recorridos lineales simples y cuando la profundidad del stack podría ser grande.
- Usa **recursión** cuando el problema es naturalmente recursivo (árboles, gráficos, backtracking) y la profundidad está acotada.

## Trampas

La recursión profunda arriesga desbordamiento de stack; convierte código recursivo caliente a iteración (a menudo con un stack explícito) cuando la profundidad es ilimitada.

## Por qué es importante

Elegir el estilo correcto mantiene el código tanto correcto como legible.

La recursión hace que el código de árbol y gráfico sea elegante, pero conocer su costo de memoria te permite evitar bloqueos en entradas profundas.

Este juicio de compromiso es exactamente lo que los entrevistadores investigan cuando te piden que "conviertas esto a iterativo."