Recursão e por que Python (não) a ama 🌀

Se em uma entrevista pedirem para você escrever fatorial ou números de Fibonacci usando recursão — escreva. Mas se você a usa com frequência na prática...
Sim, a recursão é conceitualmente bonita, matematicamente elegante, mas se você se empolgar, pode derrubar a produção e encher toda a RAM com frames de pilha.

Vamos analisar o que acontece nos bastidores e por que Python, ao contrário de linguagens funcionais, não gosta muito de recursão.

1️⃣ O custo: pilha de chamadas
Cada chamada de função não é gratuita. É a criação de um novo stack frame na memória. Nesse frame são armazenadas variáveis locais e o endereço de retorno.
Imagine uma matriosca onde cada boneca seguinte pesa o mesmo que a anterior. Em Python, esse "peso" recai sobre a RAM.
Um loop while ou for usa um bloco de memória. A recursão consome memória linearmente (ou exponencialmente) proporcional à profundidade da chamada.

2️⃣ Por que não há otimização de cauda
Em linguagens como Haskell ou C++, o compilador é inteligente. Se a chamada recursiva é a última ação na função (recursão de cauda), ele a substitui por um simples salto (GOTO), sem criar um novo frame. Isso é chamado de Tail Call Optimization (TCO).

Em Python, TCO não existe e não existirá. Guido van Rossum (BDFL) é fundamentalmente contra TCO em Python. O argumento é simples: "Queremos ver tracebacks completos de erros". Se a pilha for colapsada, você nunca saberá em qual nível da recursão tudo falhou.
Portanto, o limite de 1000 chamadas (padrão) não é um bug, mas um protetor contra estouro de pilha. Pode-se aumentá-lo via sys.setrecursionlimit? Pode. Mas se você precisou fazer isso, 99% de chance de que errou na arquitetura.

3️⃣ Quando a recursão é má e quando é necessária?
❌ Estruturas lineares (por exemplo, listas): Cálculo de fatorial, números de Fibonacci ou percorrer uma lista plana. Um loop iterativo while/for será sempre mais rápido e econômico em memória (memória O(1) contra O(N)).
✅ Estruturas ramificadas (árvores, grafos, dicts aninhados): Parse de JSON, percorrer sistema de arquivos, árvore DOM ou algoritmos do tipo Dividir e Conquistar (QuickSort, MergeSort). Aqui a recursão reduz a carga cognitiva e torna o código legível.

4️⃣ Remédio para lentidão: @lru_cache
O exemplo clássico de burrice é calcular Fibonacci "na marra". Complexidade O(2^n). Isso significa que para calcular o 50º número, o programa morrerá antes de terminar.
Solução — Memoização.
O decorador @functools.lru_cache armazena em cache os resultados das chamadas. Se a função já foi calculada com aquele argumento, Python simplesmente pega o valor pronto da tabela hash. Isso transforma o horror exponencial em complexidade linear O(N).

Resumo: Python não é Haskell nem Lisp. Aqui, a recursão é um cidadão de segunda classe. Use-a para árvores e grafos, mas para todo o resto existem loops.

#anatomia_do_python