Recursão: Quando uma Função Chama a Si Mesma

Abrimos a Fase 5 com uma das ideias mais elegantes e, à primeira vista, mais desconcertantes da programação: uma função que chama a si mesma. Parece um paradoxo — como algo pode se definir em termos de si próprio sem girar para sempre? Mas a recursão, quando bem compreendida, é uma ferramenta poderosa que expressa certos problemas com uma clareza que a repetição comum não alcança. E há uma razão especial para estudá-la agora, no início desta fase: as estruturas de dados que vamos construir — listas, árvores — têm natureza recursiva, e percorrê-las com recursão será quase natural.

A ideia central: um problema definido em termos de si mesmo

A recursão funciona quando um problema pode ser dividido em uma versão menor de si mesmo. Pense no fatorial de um número: 5! é 5 × 4!, que é 5 × 4 × 3!, e assim por diante. Cada fatorial é definido em termos de um fatorial menor. Essa autossimilaridade é o sinal de que a recursão se encaixa.

Toda função recursiva precisa de duas partes, e a ausência de qualquer uma é fatal. O caso base é a condição de parada — o menor problema, cuja resposta é conhecida diretamente, sem mais recursão. O caso recursivo é onde a função chama a si mesma com uma versão menor do problema, aproximando-se do caso base. Sem caso base, a recursão nunca para (e estoura a pilha); sem progresso rumo a ele, idem.

O exemplo canônico: fatorial

#include <stdio.h>

long fatorial(int n) {
    if (n <= 1) {          // CASO BASE: 0! = 1! = 1
        return 1;
    }
    return n * fatorial(n - 1); // CASO RECURSIVO: n! = n × (n-1)!
}

int main(void) {
    for (int i = 0; i <= 6; i++) {
        printf("%d! = %ld\n", i, fatorial(i));
    }
    return 0;
}

Saída:

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720

Acompanhe o que acontece ao chamar fatorial(3). A função vê que 3 > 1, então retorna 3 * fatorial(2). Para calcular isso, ela chama fatorial(2), que retorna 2 * fatorial(1). E fatorial(1) atinge o caso base, retornando 1 diretamente. Agora as chamadas "desempilham": fatorial(2) completa 2 * 1 = 2, fatorial(3) completa 3 * 2 = 6. O caso base é o que permite essa cadeia terminar e as respostas voltarem.

Recursão e a pilha: o que acontece por baixo

Aqui reconectamos com a aula A Pilha e o Heap: Onde Cada Coisa Vive, sobre a pilha. Cada chamada recursiva cria um novo stack frame na pilha, com sua própria cópia dos parâmetros e variáveis locais. Quando você chama fatorial(3), empilham-se os frames de fatorial(3), fatorial(2) e fatorial(1), um sobre o outro. Só quando o caso base é atingido é que eles começam a desempilhar, cada um devolvendo seu resultado ao anterior.

Essa é a beleza e o perigo da recursão. A beleza: a pilha guarda automaticamente o "estado" de cada nível, sem que você precise gerenciá-lo. O perigo: cada nível consome espaço da pilha, que é limitada. Uma recursão profunda demais (ou infinita, por falta de caso base) causa o stack overflow que estudamos — a pilha se esgota e o programa é encerrado. É por isso que o caso base não é um detalhe: é o que garante que a pilha volte a esvaziar.

Comparando recursão e iteração

Todo problema recursivo pode ser reescrito com um laço (iteração), e vice-versa. O fatorial, por exemplo, é igualmente simples de forma iterativa:

#include <stdio.h>

long fatorial_iterativo(int n) {
    long resultado = 1;
    for (int i = 2; i <= n; i++) {
        resultado *= i;
    }
    return resultado;
}

Qual usar? Depende. A versão iterativa costuma ser mais eficiente (não há custo de chamadas de função nem consumo de pilha) e é preferível quando o problema é naturalmente sequencial, como este. A versão recursiva brilha quando o problema é intrinsecamente recursivo — quando a solução recursiva é muito mais clara e direta que a iterativa. Para o fatorial, a iteração é perfeitamente adequada. Mas para percorrer uma árvore, como veremos, a recursão será tão mais simples que a iteração pareceria contorcida. A regra prática: use recursão quando ela tornar o código mais claro; prefira iteração quando a recursão for apenas uma complicação desnecessária.

Um caso onde a recursão é natural: percorrer estruturas

Para antecipar por que a recursão importa nesta fase, veja como ela expressa naturalmente a soma dos dígitos de um número — um problema que se define em termos menores (o último dígito, mais a soma dos demais):

#include <stdio.h>

int soma_digitos(int n) {
    if (n == 0) {              // caso base
        return 0;
    }
    return (n % 10) + soma_digitos(n / 10); // último dígito + resto
}

int main(void) {
    printf("%d\n", soma_digitos(12345)); // 15 (1+2+3+4+5)
    return 0;
}

A cada passo, n % 10 extrai o último dígito e n / 10 remove-o, encolhendo o problema até n chegar a zero. A estrutura recursiva reflete diretamente a definição do problema. Quando chegarmos às listas encadeadas e às árvores, veremos que "processar o primeiro elemento e depois processar o resto" é exatamente esse mesmo padrão — e é por isso que a recursão e as estruturas encadeadas combinam tão bem.

Um alerta honesto: recursão mal usada

Nem toda recursão é boa recursão. O exemplo clássico de recursão ineficiente é a sequência de Fibonacci implementada de forma ingênua:

long fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2); // recalcula os mesmos valores muitas vezes!
}

Essa versão é elegante, mas desastrosamente lenta para n grande, porque recalcula os mesmos valores repetidamente — fib(5) calcula fib(3) duas vezes, fib(2) três vezes, e a explosão só piora. É um caso em que a recursão ingênua, embora bonita, é a escolha errada; uma versão iterativa (ou recursão com memoização) resolve em tempo linear. A lição: a recursão é uma ferramenta, não uma virtude em si. Use-a quando ela traz clareza sem penalidade proibitiva, e desconfie quando ela recalcula trabalho ou aprofunda demais a pilha.

Recursão não é técnica de otimização, é forma de descrever problema: quando a estrutura do dado é ela mesma recursiva — uma árvore, uma lista, um diretório dentro de outro — a solução recursiva costuma ser a mais curta e a mais fácil de conferir. O custo aparece na pilha, que cresce a cada chamada e não é infinita; e o caso base, aquele que quase todo mundo escreve por último, é o que separa o algoritmo do travamento.

Fontes e leituras recomendadas

• The C Programming Language (K&R), Kernighan & Ritchie — Cap. 4.10, Recursion
• cppreference — sobre chamadas de função e a pilha — https://en.cppreference.com/w/c/language/functions
• Modern C, Jens Gustedt — seção sobre recursão e o modelo de execução — https://gustedt.gitlabpages.inria.fr/modern-c/
• Algorithms, Robert Sedgewick — tratamento clássico de recursão e sua análise
• The Little Schemer, Friedman & Felleisen — um livro inteiro que ensina a pensar recursivamente

Exercícios

Exercício 1

Escreva uma função recursiva int soma_ate(int n) que calcule a soma dos inteiros de 1 até n (por exemplo, soma_ate(5) = 15). Identifique claramente o caso base e o caso recursivo.

#include <stdio.h>
int soma_ate(int n) {
    if (n <= 0) return 0;        // caso base
    return n + soma_ate(n - 1);  // caso recursivo
}
int main(void) {
    printf("%d\n", soma_ate(5)); // 15
    return 0;
}

Exercício 2

Escreva uma função recursiva int potencia(int base, int expoente) que calcule base elevado a expoente (com expoente ≥ 0), sem usar pow. O caso base é expoente == 0 (resultado 1).

#include <stdio.h>
int potencia(int base, int expoente) {
    if (expoente == 0) return 1;              // caso base: base^0 = 1
    return base * potencia(base, expoente - 1); // caso recursivo
}
int main(void) {
    printf("%d\n", potencia(2, 10)); // 1024
    return 0;
}

Exercício 3

Escreva uma função recursiva que imprima uma contagem regressiva de n até 1 e depois imprima "Fim!". Depois, mova a impressão para depois da chamada recursiva e observe: a contagem agora sai crescente. Explique por quê.

#include <stdio.h>
void regressiva(int n) {
    if (n == 0) { printf("Fim!\n"); return; }
    printf("%d ", n);       // imprime ANTES de recorrer
    regressiva(n - 1);
}

void crescente(int n) {
    if (n == 0) { printf("Fim! "); return; }
    crescente(n - 1);
    printf("%d ", n);       // imprime DEPOIS de recorrer
}

Exercício 4

Reescreva a função soma_digitos do artigo de forma iterativa (com um laço while), produzindo o mesmo resultado. Qual das duas versões você acha mais legível para este problema?

#include <stdio.h>
int soma_digitos(int n) {
    int soma = 0;
    while (n > 0) {
        soma += n % 10; // último dígito
        n /= 10;        // remove o último dígito
    }
    return soma;
}
int main(void) {
    printf("%d\n", soma_digitos(12345)); // 15
    return 0;
}

Exercício 5

Explique por que a versão recursiva ingênua de Fibonacci é tão ineficiente. Se fib(5) chama fib(4) e fib(3), quantas vezes fib(2) acaba sendo calculada no total ao computar fib(5)?