O que é recursão?

Question

O que é recursão?

Accepted Answer

**Recursão** é quando uma função chama a si mesma para resolver uma versão menor do mesmo problema. Toda recursão precisa de um **caso base** que a interrompe e de um **caso recursivo** que avança em direção à base.

## A ideia

Quebre um problema em subproblemas menores e idênticos. Cada chamada coloca um frame na **pilha de chamadas** (call stack); retornos os removem.

## Exemplo

```python
def factorial(n):
    if n <= 1:            # base case: stop recursing
        return 1
    return n * factorial(n - 1)   # recursive case: smaller problem

factorial(4)             # 4 * 3 * 2 * 1 -> 24
```

## Rastreamento

```text
factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * 3 * 2 * 1 = 24
```

## Complexidade

Aqui **O(n)** de tempo e **O(n)** de espaço de pilha (um frame por chamada).

## Armadilhas

- **Caso base ausente** -> recursão infinita -> overflow de pilha.
- Recursão profunda pode esgotar a pilha; algumas linguagens carecem de otimização tail-call.
- Recomputar subproblemas sobrepostos pode resultar em tempo exponencial (corrija com memoização).

## Por que isso importa

Recursão expressa naturalmente problemas autossimilares — árvores, grafos, divisão e conquista — muito mais claramente do que loops.

É o modelo mental por trás de merge sort, backtracking e programação dinâmica.

Compreender a pilha de chamadas também o torna melhor em depuração e raciocínio sobre memória.