# Recursão

Casos base, decomposição recursiva, o limite de recursão e exemplos com fatorial e listas aninhadas.

Página: https://resumos.rgo.pt/cadeiras/fp/recursao/

Uma função **recursiva** resolve um problema chamando-se a si própria com uma versão mais pequena do mesmo problema. A ideia parece circular, mas funciona desde que duas condições se verifiquem: cada chamada trata um caso estritamente mais pequeno, e existe um **caso base** que se resolve diretamente, sem nova chamada.

## O modelo mental

Pensa em recursão como uma delegação com contrato. Para calcular `fatorial(4)`, dizes: “`4 * fatorial(3)`, e o `fatorial(3)` logo se resolve”. Cada chamada cria o seu próprio conjunto de variáveis locais, por isso os vários `n` em simultâneo não se confundem. A cadeia de chamadas só termina quando atinge o caso base, e depois os resultados combinam-se no regresso.

```
def fatorial(n):
    if n == 0:
        return 1
    return n * fatorial(n - 1)

print(fatorial(4))
```

Isto escreve `24`. Segue a cadeia: `fatorial(4)` chama `fatorial(3)`, que chama `fatorial(2)`, que chama `fatorial(1)`, que chama `fatorial(0)`. O caso base devolve `1`. No regresso, `1` combina-se em `1 * 1 = 1`, depois `2 * 1 = 2`, depois `3 * 2 = 6`, depois `4 * 6 = 24`. Cada chamada resolve um problema de âmbito mais pequeno até chegar ao caso base.

Sem caso base, ou se o argumento não diminuir, a cadeia nunca termina: cada chamada cria outra, até Python desistir com `RecursionError`. O limite por omissão ronda as 1000 chamadas encadeadas (podes consultá-lo com `sys.getrecursionlimit()`[1](https://resumos.rgo.pt/cadeiras/fp/recursao/#user-content-fn-rec-limit)), e existe precisamente para transformar um esquecimento infinito numa mensagem de erro legível. Quando vires `RecursionError`, a primeira suspeita é o caso base: ou falta, ou a condição nunca se verifica.

A cadeia de `fatorial(4)` desce até ao caso base e o resultado compõe-se no regresso.

![Cadeia de chamadas do fatorial de 4 até ao caso base fatorial de 0, com o regresso a compor 1, 1, 2, 6 e 24.](https://resumos.rgo.pt/cadeiras/fp/recursao/figura-1.svg)

## Iteração contra recursão

Qualquer problema resolvível por iteração também se resolve por recursão, e vice-versa. Como critério prático: a versão iterativa é normalmente mais rápida e usa menos memória, porque evita empilhar chamadas; a versão recursiva é muitas vezes mais fácil de ler quando o problema se decompõe naturalmente (listas aninhadas, árvores, divisões em metades). Se conseguires escrever as duas, compara a legibilidade; se só uma delas te sair, usa essa.

## Exemplo 1: inverter uma string por recursão

Para inverter uma string, separa o primeiro caráter e inverte o resto: `inverter('abc')` é `inverter('bc')` seguido de `'a'`. O caso base é a string com zero ou um caráter, que já está invertida.

```
def inverter(s):
    if len(s) <= 1:
        return s
    return inverter(s[1:]) + s[0]

print(inverter('abc'))
print(inverter(''))
```

Isto escreve `cba` e “(string vazia). Segue`'abc'`: devolve `inverter('bc') + 'a'`; `inverter('bc')`devolve`inverter('c') + 'b'`; `inverter('c')`é o caso base e devolve`'c'`. No regresso: `'c' + 'b'`dá`'cb'`, e `'cb' + 'a'`dá`'cba'`. Repara que a condição do caso base usa `<=`para cobrir também a string vazia; com`== 1`apenas, a chamada com`''` nunca terminaria.

Corre os dois casos e segue a cadeia mentalmente antes de veres o resultado.

```python
def inverter(s):
    if len(s) <= 1:
        return s
    return inverter(s[1:]) + s[0]

print(inverter('abc'))
print(inverter(''))
```

## Exemplo 2: achatar uma lista aninhada

Uma lista pode conter outras listas, que por sua vez contêm outras, sem limite de profundidade. **Achatar** (flatten) é produzir uma lista só com os elementos que não são listas, pela ordem em que aparecem. A recursão é a ferramenta natural: se o elemento é uma lista, achata-a; se não é, guarda-o.

```
def achatar(lista):
    """Devolve os elementos não lista, pela ordem de ocorrência."""
    resultado = []
    for elemento in lista:
        if isinstance(elemento, list):
            resultado.extend(achatar(elemento))
        else:
            resultado.append(elemento)
    return resultado

print(achatar(['Olá', [2, [[], False]], [True]]))
print(achatar([[]]))
```

Isto escreve `['Olá', 2, False, True]` e `[]`. Segue o primeiro exemplo: `'Olá'` não é lista e é acrescentado; `[2, [[], False]]` é lista e achata-se para `[2, False]` (a lista vazia interior contribui com zero elementos); `[True]` achata-se para `[True]`. O `extend` junta os elementos da sublista achatada um a um, enquanto o `append` guardaria a sublista inteira como elemento único. Confundir estes dois métodos é o erro típico deste exercício.

Como escrever uma função recursiva

Escreve primeiro o caso base e testa-o isolado. Depois escreve o passo recursivo assumindo que a chamada mais pequena já funciona (não tentes seguir mentalmente todas as chamadas ao mesmo tempo). Por fim, confirma que cada chamada se aproxima do caso base. Se a função entrar em recursão infinita, verifica estas três coisas por esta ordem: o caso base existe, a condição do caso base é alcançável e o argumento diminui em cada chamada.

[Vídeo: Recursion: what it is and how it works](https://www.youtube.com/watch?v=8YokYDn1J8Q)

A miniatura vem do YouTube. O vídeo só carrega quando clicas. [Abrir no YouTube](https://www.youtube.com/watch?v=8YokYDn1J8Q)

## Notas de rodapé

1.  Documentação oficial do Python, [`sys.getrecursionlimit`](https://docs.python.org/3/library/sys.html#sys.getrecursionlimit). [Voltar](https://resumos.rgo.pt/cadeiras/fp/recursao/#user-content-fnref-rec-limit)