Recursão versus iteração: profundidade da pilha, limites e quando converter

O que é

Uma função recursiva resolve um problema chamando a si mesma sobre instâncias menores; cada chamada ainda não concluída mantém um frame na pilha de chamadas (call stack). A pilha é finita. O Python impõe um limite de recursão, que pode ser lido com sys.getrecursionlimit(); a documentação descreve esse limite como uma proteção para que uma recursão infinita não estoure a pilha do C e derrube o interpretador. Ao ultrapassá-lo, é lançado RecursionError. Já o código nativo é limitado pelo tamanho da pilha da thread (no caso da thread principal, o limite é RLIMIT_STACK, de getrlimit(2)); estourá-la causa uma falha de segmentação (segmentation fault), não uma exceção. A iteração guarda o estado em variáveis ou em uma pilha ou fila explícita no heap, cujo tamanho é limitado pela memória e não por uma pilha de tamanho fixo.

Por que importa

Recursão cuja profundidade acompanha a entrada é uma superfície para negação de serviço: um JSON profundamente aninhado, uma árvore de diretórios com milhares de níveis, uma estrutura encadeada longa ou um parser de colchetes aninhados podem ser derrubados por uma entrada especialmente construída. Não presuma eliminação de chamadas em cauda (tail-call elimination), a menos que a especificação da linguagem a garanta; a maioria das linguagens populares não a oferece, de modo que um "laço com recursão em cauda" ainda consome um frame por iteração.

Como aplicar

• Reserve a recursão para problemas cuja profundidade é limitada pela estrutura, não pelo tamanho da entrada: árvores balanceadas, árvores sintáticas geradas por um parser com limite de tamanho, divisão e conquista sobre metades (profundidade logarítmica).
• Converta quando a profundidade for linear em relação à entrada: percorra a árvore com uma pilha explícita (busca em profundidade) ou uma fila (busca em largura); substitua a recursão linear por um laço com acumulador.
• Onde a recursão permanecer, passe um parâmetro de profundidade e falhe de forma limpa em um máximo documentado, antes de atingir o limite do runtime, com um erro que nomeie o limite.
• Trate o aumento do limite de recursão como um paliativo: ele troca um RecursionError por um possível estouro da pilha do C, e o tamanho da pilha das outras threads é definido separadamente do da thread principal.
• Use memoização em funções recursivas com subproblemas sobrepostos (veja programação dinâmica); a memoização reduz o trabalho, não a profundidade.

Armadilhas

Converter para iteração altera a ordem de visita, a menos que os filhos sejam empilhados em ordem inversa. A recursão mútua esconde a profundidade entre várias funções. Cadeias profundas de geradores delegantes (yield from) são percorridas a cada retomada; trate a profundidade delas como profundidade de recursão. Exceções que desenrolam uma pilha profunda são lentas e geram tracebacks enormes. __eq__, __repr__ ou serializadores recursivos sobre dados cíclicos nunca terminam; registre os objetos já visitados.

O limite de profundidade vale também para a forma iterativa

Substituir a recursão por uma pilha explícita não limita a profundidade; apenas desloca o limite da pilha de chamadas para o heap, onde a falha é a morte de todo o processo por falta de memória (out-of-memory), em vez de um RecursionError que pode ser capturado. Para aninhamento controlado pela entrada (JSON, colchetes, árvores de diretórios), mantenha uma profundidade máxima documentada nas duas formas: verifique o parâmetro de profundidade na versão recursiva e o tamanho da pilha explícita na versão iterativa, falhando com um erro que nomeie o limite. Parsers costumam trazer um limite desse tipo (por exemplo, o serde_json recusa por padrão documentos aninhados em mais de 128 níveis). Com um limite definido, a escolha entre recursão e iteração passa a ser uma questão de clareza e do custo de frames no runtime, não de segurança.