05. Recursividade — Curso C# para desenvolvedores Node JS

Uma função que resolve um problema chamando a si mesma para resolver uma versão menor do mesmo problema — e por que isso não é mágica, é a pilha de chamadas trabalhando por baixo.

1. O que é recursividade

Uma função é recursiva quando, na sua própria definição, ela chama a si mesma para resolver uma versão menor (ou mais simples) do problema original. Pode soar circular à primeira vista — "como uma função pode chamar a si mesma sem entrar num loop infinito?" — mas a resposta está numa peça obrigatória de toda função recursiva: o caso base.

2. O caso base é obrigatório

Toda função recursiva precisa de duas partes: o caso base, uma condição simples o suficiente para ser resolvida diretamente, sem nova chamada recursiva; e o caso recursivo, onde a função chama a si mesma com uma entrada menor, progressivamente mais próxima do caso base.

Atenção

Uma função recursiva sem caso base (ou com um caso base que nunca é alcançado, por exemplo porque a entrada não diminui a cada chamada) não é diferente de um ENQUANTO VERDADEIRO sem condição de parada: ela vai chamar a si mesma indefinidamente, até estourar a memória disponível para a pilha de chamadas — um erro comumente chamado de stack overflow.

3. Fatorial: o exemplo clássico

O fatorial de um número n (escrito n!) é o produto de todos os inteiros positivos de 1 até n. Por definição, o fatorial de 0 é 1. Essa definição já é naturalmente recursiva: n! = n × (n-1)!, com o caso base sendo 0! = 1.

PSEUDOCÓDIGO fatorial.txt

FUNÇÃO fatorial(n)
    SE n = 0 ENTÃO           // caso base
        RETORNE 1
    SENÃO
        RETORNE n × fatorial(n - 1)   // caso recursivo
    FIM SE
FIM FUNÇÃO

4. Traçando a pilha de chamadas

Para entender o que acontece de verdade ao chamar fatorial(4), vale lembrar do capítulo anterior: toda chamada de função é empilhada na pilha de chamadas (call stack) e só é removida (desempilhada) quando a função termina e retorna um valor. Recursão usa exatamente esse mecanismo — cada chamada recursiva empilha uma nova "instância" da função, esperando o resultado da chamada seguinte antes de poder terminar a própria conta.

Fig. 1 — Pilha de chamadas de fatorial(4): empilha até o caso base, depois desempilha multiplicando os resultados.

O ponto-chave: nenhuma multiplicação acontece de verdade até o caso base ser alcançado. A partir daí, as chamadas empilhadas vão sendo resolvidas — desempilhadas — de baixo para cima, cada uma completando sua própria conta com o resultado que recebeu da chamada seguinte.

5. Outro exemplo: soma de um vetor

Fatorial não é o único jeito de pensar recursivamente. Qualquer problema que possa ser quebrado em "resolver uma peça pequena + delegar o resto para uma versão menor do mesmo problema" é candidato a uma solução recursiva. Somar os elementos de um vetor é um bom segundo exemplo:

PSEUDOCÓDIGO soma-recursiva.txt

FUNÇÃO somaRecursiva(vetor, índice)
    SE índice = tamanho(vetor) ENTÃO   // caso base: vetor esgotado
        RETORNE 0
    SENÃO
        RETORNE vetor[índice] + somaRecursiva(vetor, índice + 1)
    FIM SE
FIM FUNÇÃO

// chamada inicial: somaRecursiva(vetor, 0)

O caso base aqui não é um número fixo como 0, é uma condição: "não sobrou mais nada para somar". Isso reforça a regra geral — o caso base é qualquer situação simples o bastante para ser respondida sem uma nova chamada recursiva, e cada chamada recursiva precisa se aproximar dele.

Nota

Fibonacci é outro exemplo clássico de recursão, definido como fib(n) = fib(n-1) + fib(n-2), com caso base fib(0) = 0 e fib(1) = 1. Vale notar que essa versão "ingênua" de Fibonacci recalcula os mesmos valores repetidamente e acaba sendo exponencial em complexidade — um lembrete de que recursão elegante nem sempre é recursão eficiente.

6. Recursão vs. iteração

Praticamente todo problema resolvido com recursão também pode ser resolvido com um laço (iteração), e vice-versa. A escolha entre as duas abordagens é um trade-off, não uma regra fixa:

PSEUDOCÓDIGO fatorial-recursivo.txt

FUNÇÃO fatorial(n)
    SE n = 0 ENTÃO
        RETORNE 1
    SENÃO
        RETORNE n × fatorial(n - 1)
    FIM SE
FIM FUNÇÃO

PSEUDOCÓDIGO fatorial-iterativo.txt

FUNÇÃO fatorial(n)
    resultado ← 1
    PARA i DE 1 ATÉ n
        resultado ← resultado × i
    FIM PARA
    RETORNE resultado
FIM FUNÇÃO

Aspecto	Recursão	Iteração
Legibilidade	Costuma espelhar a definição matemática/conceitual do problema, ficando mais direta de ler	Pode exigir mais código para controlar estado manualmente
Uso de memória	Cada chamada ocupa espaço na pilha de chamadas — entrada muito grande pode causar stack overflow	Usa memória constante independente do tamanho da entrada (normalmente)
Melhor para	Estruturas naturalmente recursivas: árvores, algumas divisões e conquistas	Laços simples sobre coleções, quando performance de memória importa

Não existe resposta universal sobre qual é "melhor" — depende do problema. Estruturas de dados hierárquicas (o assunto do próximo capítulo, árvores) costumam ficar muito mais claras resolvidas com recursão do que com iteração pura. Já processar uma lista simples de valores, como no exemplo do fatorial, normalmente é resolvido de forma mais direta e econômica com iteração.

Recursividade