[392] 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.

O que vem a seguir

Hoje abrimos a Fase 5 com a recursão: uma função que se chama, dividindo um problema em versões menores de si mesmo, sempre com um caso base para parar. Vimos como ela se apoia na pilha, como se compara à iteração, e onde brilha ou tropeça. Guardamos a intuição de que "processar o primeiro e recorrer no resto" é o padrão natural para estruturas encadeadas. Na próxima aula, faremos uma pausa nos temas de estruturas para explorar a manipulação de bits — operar diretamente sobre os 0s e 1s que compõem os dados, uma habilidade de baixo nível que revela o C em sua essência mais próxima da máquina.

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)?