Tutorial de Recursão em C | Fatorial e Fibonacci Visualizados

O que é recursão?

Recursão é uma técnica de programação em que uma função chama a si mesma.
Qualquer coisa que você pode expressar com um laço também pode ser escrita de forma recursiva, mas a recursão é especialmente útil quando o problema se repete em subproblemas menores.

Toda função recursiva precisa de um caso-base (uma condição de parada). Sem um, as chamadas continuam para sempre e isso causa um estouro de pilha.

Fatorial

n! = n × (n-1) × ... × 1 pode ser escrito recursivamente assim:

int factorial(int n) {
    if (n <= 1) return 1;   // caso-base
    return n * factorial(n - 1); // chamada recursiva
}

Fluxo de execução para n=4:
factorial(4) → 4 × factorial(3) → 4 × 3 × factorial(2) → 4 × 3 × 2 × factorial(1) → 4 × 3 × 2 × 1 = 24

Visualizador da pilha de chamadas

Veja como as chamadas recursivas são empilhadas e depois desempilhadas conforme cada uma retorna.

Sequência de Fibonacci

A sequência de Fibonacci (0, 1, 1, 2, 3, 5, 8, 13, ...) é um exemplo clássico de uma função que faz duas chamadas recursivas.

int fib(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}

Atenção: esta implementação ingênua fica exponencialmente mais lenta à medida que n cresce — até fib(40) pode levar vários segundos. Na prática, use um laço ou memoização.

n =

Coisas para tomar cuidado

Estouro de pilha
Sem um caso-base, a recursão nunca para. A pilha se esgota e seu programa quebra.

Desempenho
Recursão que repete o mesmo trabalho várias vezes é ineficiente. Considere memoização (armazenar em cache os resultados) ou reescrever como um laço.

Onde a recursão é especialmente útil
Percurso em árvores, algoritmos de dividir para conquistar (como merge sort) e qualquer problema que se encaixe no padrão de indução matemática.

Teste de Revisão

int mystery(int n) {
    if (n == 0) return 0;
    return n + mystery(n - 1);
}
printf("%d\n", mystery(5));

Qual é a saída?

120

Explicação: mystery(5) = 5 + mystery(4) = 5 + 4 + 3 + 2 + 1 + 0 = 15.
Esta função calcula a soma de 1 até n — não confunda com fatorial (n!).