O Que É Recursão? Uma Função Que Chama a Si Mesma
Recursão é resolver um problema fazendo com que uma função chame a si mesma sobre uma versão menor do problema, até alcançar um caso base simples que ela consegue responder diretamente.
Recursão expressa um problema em termos de si mesmo. Uma função recursiva trata um caso base minúsculo diretamente e reduz cada caso maior em direção a esse caso base chamando a si mesma sobre uma entrada menor. É elegante para dados naturalmente aninhados como árvores e sistemas de arquivos, mas cada chamada consome espaço na pilha, então a recursão sem limite pode estourar a pilha.
As duas partes da recursão
Toda função recursiva correta precisa de um caso base (uma condição que interrompe a recursão e retorna uma resposta direta) e um caso recursivo (que reduz o problema e chama a si mesma). Perca o caso base, ou falhe em avançar em direção a ele, e a recursão nunca termina.
Quando a recursão brilha
- Travessia de árvores e grafos, onde a estrutura é naturalmente aninhada.
- Algoritmos de dividir para conquistar como quicksort e mergesort.
- Percorrer dados hierárquicos como diretórios ou o DOM.
- Problemas definidos recursivamente, como fatoriais ou números de Fibonacci.
Recursão vs iteração
Qualquer coisa recursiva pode ser escrita com um loop, e vice-versa. A recursão costuma ser mais clara para estruturas aninhadas, mas usa espaço na pilha por chamada. A iteração usa espaço de pilha constante e é mais segura para problemas muito profundos, a algum custo de legibilidade.
O custo da pilha
Cada chamada recursiva empilha um quadro na pilha. Recursão profunda pode esgotar a pilha de chamadas limitada e causar um stack overflow. Algumas linguagens otimizam chamadas de cauda para evitar isso, mas muitas não o fazem, então recursão profunda é arriscada.
Um exemplo rápido
Um fatorial é factorial(n) = n <= 1 ? 1 : n * factorial(n - 1). O caso base (n <= 1) interrompe a recursão; cada chamada encolhe n em direção a ele.
Recursão em CI
Um bug de recursão (um caso base ausente ou inalcançável) aparece como um stack overflow que falha de forma idêntica em toda execução, então repetir nunca ajuda. A Latchkey distingue falhas determinísticas de falhas transitórias de infraestrutura, repetindo apenas as últimas para que um bug real de recursão permaneça visível.
Principais conclusões
- Recursão resolve um problema chamando a si mesma sobre entradas menores até um caso base.
- Ela precisa de um caso base alcançável e progresso real, ou nunca termina.
- Recursão profunda pode estourar a pilha; isso é um bug determinístico, não uma instabilidade.