Aula 16 — Recursão

1. O que é Recursão?

Até agora todas as funções que escrevemos chamavam outras funções. Recursão é a técnica em que uma função chama a si mesma para resolver uma versão menor do mesmo problema, repetindo esse processo até chegar a um caso simples que pode ser resolvido diretamente.

A estrutura obrigatória de toda função recursiva

tipo funcaoRecursiva(parametros) {

    /* CASO BASE — condição de parada: resolve sem chamar a si mesma */
    if (condicaoDeParada)
        return valorSimples;

    /* CASO RECURSIVO — chama a si mesma com problema menor */
    return funcaoRecursiva(parametrosMenores);
}

2. Primeiro Exemplo: Contagem Regressiva

Antes de exemplos matemáticos, vamos ver recursão da forma mais visual possível: uma contagem regressiva.

#include <stdio.h>

void contagem(int n) {
    /* Caso base: quando n chega a 0, encerra */
    if (n == 0) {
        printf("Fim!\n");
        return;
    }

    /* Caso recursivo: imprime n e chama com n-1 */
    printf("%d...\n", n);
    contagem(n - 1);
}

int main() {
    contagem(5);
    return 0;
}

O que acontece passo a passo

3. A Pilha de Chamadas (Call Stack)

Cada chamada de função reserva um espaço na pilha de memória (stack) para armazenar seus parâmetros e variáveis locais. Com recursão, várias chamadas ficam empilhadas ao mesmo tempo, aguardando umas às outras:

Após o caso base retornar, cada chamada desempilha em ordem inversa: contagem(0) retorna para contagem(1), que retorna para contagem(2), e assim por diante até voltar ao main.

4. Fatorial — O Exemplo Clássico

O fatorial de um número inteiro positivo n é o produto de todos os inteiros de 1 até n. A definição matemática já é naturalmente recursiva:

#include <stdio.h>

long fatorial(int n) {
    /* Caso base */
    if (n == 0) return 1;

    /* Caso recursivo: n! = n × (n-1)! */
    return n * fatorial(n - 1);
}

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

Expandindo fatorial(4) passo a passo

5. Fibonacci — Dois Casos Base

A sequência de Fibonacci começa com 0 e 1, e cada número seguinte é a soma dos dois anteriores: 0, 1, 1, 2, 3, 5, 8, 13, 21... É um exemplo com dois casos base e duas chamadas recursivas:

#include <stdio.h>

long fib(int n) {
    /* Dois casos base */
    if (n == 0) return 0;
    if (n == 1) return 1;

    /* Caso recursivo */
    return fib(n - 1) + fib(n - 2);
}

int main() {
    for (int i = 0; i <= 12; i++)
        printf("fib(%2d) = %ld\n", i, fib(i));
    return 0;
}

Árvore de chamadas de fib(4) — o problema do retrabalho

                    fib(4)
                   /      \
              fib(3)      fib(2)
             /     \      /    \
         fib(2)  fib(1) fib(1) fib(0)
         /    \
      fib(1) fib(0)

6. Outros Exemplos Práticos

6.1 — Soma dos elementos de um vetor

#include <stdio.h>

int somaVetor(int v[], int n) {
    if (n == 0) return 0;                       // vetor vazio: soma é 0
    return v[0] + somaVetor(v + 1, n - 1);     // primeiro + soma do resto
}

int main() {
    int notas[] = {7, 8, 6, 9, 5};
    int total = somaVetor(notas, 5);
    printf("Soma: %d | Media: %.1f\n", total, total / 5.0f);
    return 0;
}

6.2 — Potência (base elevada ao expoente)

#include <stdio.h>

double potencia(double base, int exp) {
    if (exp == 0) return 1.0;                   // base^0 = 1
    return base * potencia(base, exp - 1);      // base^n = base × base^(n-1)
}

int main() {
    printf("2^10  = %.0f\n",  potencia(2,   10));
    printf("3^5   = %.0f\n",  potencia(3,    5));
    printf("1.5^4 = %.4f\n",  potencia(1.5,  4));
    return 0;
}

6.3 — Maior Divisor Comum (algoritmo de Euclides)

Um dos algoritmos mais antigos da matemática — e um dos exemplos mais elegantes de recursão. A ideia: mdc(a, b) = mdc(b, a % b), com caso base mdc(a, 0) = a.

#include <stdio.h>

int mdc(int a, int b) {
    if (b == 0) return a;           // caso base: MDC(a, 0) = a
    return mdc(b, a % b);           // caso recursivo
}

int main() {
    printf("MDC(48, 18)  = %d\n", mdc(48, 18));   // 6
    printf("MDC(100, 75) = %d\n", mdc(100, 75));  // 25
    printf("MDC(17, 5)   = %d\n", mdc(17,  5));   // 1 — primos entre si
    return 0;
}

Acompanhando mdc(48, 18) passo a passo

6.4 — Impressão dos dígitos de um número

#include <stdio.h>

void imprimirDigitos(int n) {
    if (n < 10) {                   // caso base: um único dígito
        printf("%d ", n);
        return;
    }
    imprimirDigitos(n / 10);        // imprime todos exceto o último
    printf("%d ", n % 10);          // depois imprime o último
}

int main() {
    printf("Digitos de 7483: ");
    imprimirDigitos(7483);
    printf("\n");
    return 0;
}

7. Recursão vs. Iteração — Quando Usar Cada Uma

Qualquer problema resolvível com recursão também pode ser resolvido com loops, e vice-versa. A escolha depende de qual deixa o código mais claro e eficiente para aquele problema específico.

Fatorial: recursão vs. iteração lado a lado

long fatorial(int n) {
    if (n == 0) return 1;
    return n * fatorial(n - 1);
}

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

8. C vs. Java — Recursão

Side-by-side: fatorial recursivo

long fatorial(int n) {
    if (n == 0) return 1;
    return n * fatorial(n - 1);
}

static long fatorial(int n) {
    if (n == 0) return 1;
    return n * fatorial(n - 1);
}

A estrutura é praticamente idêntica. A única diferença é que em Java o método precisa ser static para ser chamado sem instância de objeto, enquanto em C funções já são naturalmente estáticas no sentido de pertencer ao arquivo.