Iteração versus recursão — quais são os trade-offs?

Question

Accepted Answer

**Iteração** usa loops; **recursão** usa self-calls. Elas são igualmente poderosas (qualquer coisa que você pode fazer com uma você pode fazer com a outra), mas diferem em clareza e custo.

## Side by side

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

## Comparison

| Aspecto | Iteração | Recursão |
|--------|----------|----------|
| Memory | O(1) extra | O(depth) stack |
| Readability | ótimo para trabalho linear | ótimo para árvores / divide-and-conquer |
| Risk | loop infinito | stack overflow |
| Speed | geralmente mais rápido (sem overhead de chamada) | overhead de chamada por frame |

## Quando usar qual

- Use **iteração** para traversais lineares simples e quando a profundidade da stack poderia ser grande.
- Use **recursão** quando o problema é naturalmente recursivo (árvores, grafos, backtracking) e a profundidade é limitada.

## Armadilhas

Recursão profunda arrisca stack overflow; converta código recursivo crítico para iteração (muitas vezes com uma stack explícita) quando a profundidade é ilimitada.

## Por que isso importa

Escolher o estilo certo mantém o código correto e legível.

Recursão torna código de árvore e grafo elegante, mas conhecendo seu custo de memória você consegue evitar travamentos em entradas profundas.

Esse julgamento de trade-off é exatamente o que os entrevistadores investigam quando pedem para você "converter isso para iterativo."

Aspecto	Iteração	Recursão
Memory	O(1) extra	O(depth) stack
Readability	ótimo para trabalho linear	ótimo para árvores / divide-and-conquer
Risk	loop infinito	stack overflow
Speed	geralmente mais rápido (sem overhead de chamada)	overhead de chamada por frame