Recursão é uma técnica de programação onde uma função chama a si mesma para resolver um problema. Em C, funções recursivas são amplamente utilizadas para problemas que podem ser decompostos em subproblemas semelhantes, como cálculos matemáticos, travessia de estruturas de dados e algoritmos de busca. A recursão pode tornar o código mais claro e conciso, mas requer cuidado para evitar loops infinitos e consumo excessivo de memória.

Nesta aula, vamos explorar os fundamentos da recursão, entender como a pilha de chamadas funciona e ver exemplos práticos. Também discutiremos os limites da recursão e boas práticas para usá-la de forma segura.

Conceito

Uma função recursiva é aquela que, durante sua execução, chama a si mesma. Isso permite que um problema seja resolvido em termos de versões menores de si mesmo. Por exemplo, o fatorial de um número n (n!) pode ser definido recursivamente: n! = n * (n-1)!, com 0! = 1.

Em C, uma função recursiva se parece com qualquer outra função, mas contém uma chamada para si mesma dentro do seu corpo. É essencial que haja uma condição de parada (caso base) para evitar chamadas infinitas.

#include <stdio.h>

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

int main() {
    int num = 5;
    printf("Fatorial de %d = %d\n", num, fatorial(num));
    return 0;
}

Caso base

O caso base é a condição que interrompe a recursão. Sem ele, a função continuaria chamando a si mesma indefinidamente, resultando em estouro de pilha (stack overflow). O caso base geralmente trata o menor subproblema possível, cuja resposta é conhecida diretamente.

No exemplo do fatorial, o caso base é n == 0, retornando 1. Outro exemplo clássico é a sequência de Fibonacci, onde os casos base são fib(0) = 0 e fib(1) = 1. É importante garantir que toda chamada recursiva se aproxime do caso base.

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

Pilha de chamadas

Cada chamada de função em C cria um novo registro na pilha de chamadas (call stack), contendo variáveis locais, parâmetros e endereço de retorno. Em funções recursivas, cada chamada recursiva empilha um novo quadro. Quando o caso base é atingido, as chamadas começam a retornar, desempilhando os quadros.

Isso significa que a recursão consome memória proporcional à profundidade da recursão. Para problemas com grande profundidade, como calcular o fatorial de 10000, a pilha pode estourar. Por isso, em alguns casos, é preferível usar iteração.

// Exemplo visual: imprimir contagem regressiva
void contagem(int n) {
    if (n == 0) {
        printf("Fim!\n");
        return;
    }
    printf("%d ", n);
    contagem(n - 1);
    printf("%d ", n); // executa após retorno
}

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

Exemplos e limites

Além de fatorial e Fibonacci, a recursão é útil em algoritmos como busca binária, travessia de árvores, quicksort e torre de Hanói. No entanto, a recursão tem limites práticos. Em C, o tamanho da pilha é limitado (tipicamente alguns MB). Chamadas recursivas muito profundas podem causar stack overflow.

Por exemplo, uma função recursiva que imprime números de 1 a 100000 provavelmente falhará. Nesses casos, a iteração é mais adequada. Além disso, a recursão pode ser ineficiente se houver chamadas repetidas (como Fibonacci sem memoização).

// Torre de Hanói
void hanoi(int n, char origem, char destino, char auxiliar) {
    if (n == 1) {
        printf("Mover disco 1 de %c para %c\n", origem, destino);
        return;
    }
    hanoi(n - 1, origem, auxiliar, destino);
    printf("Mover disco %d de %c para %c\n", n, origem, destino);
    hanoi(n - 1, auxiliar, destino, origem);
}

Boas práticas

1. Sempre defina um caso base claro. 2. Certifique-se de que cada chamada recursiva se aproxima do caso base. 3. Considere a profundidade máxima da recursão e o tamanho da pilha. 4. Para problemas com muitos subproblemas repetidos, use memoização ou iteração. 5. Prefira recursão quando a solução iterativa for complexa ou menos legível.

Referências

Exercícios

  1. Escreva uma função recursiva que calcule a soma dos primeiros n números naturais (1 + 2 + ... + n).

    2. ✓ Resposta:
    int soma_naturais(int n) {
    if (n == 0) return 0;
    return n + soma_naturais(n - 1);
}
  2. Implemente uma função recursiva que inverta uma string (in-place).

    3. ✓ Resposta:
    #include <string.h>

void inverte(char *str, int inicio, int fim) {
    if (inicio >= fim) return;
    char temp = str[inicio];
    str[inicio] = str[fim];
    str[fim] = temp;
    inverte(str, inicio + 1, fim - 1);
}

// Uso: inverte(str, 0, strlen(str)-1);
  3. Qual a saída do seguinte código?
    int func(int x) {
    if (x == 0) return 0;
    printf("%d ", x);
    return func(x - 1);
}
int main() { func(3); return 0; }

    4. ✓ Resposta: 3 2 1
  4. Escreva uma função recursiva que verifique se uma string é palíndromo.

    5. ✓ Resposta:
    #include <stdbool.h>

bool palindromo(char *s, int inicio, int fim) {
    if (inicio >= fim) return true;
    if (s[inicio] != s[fim]) return false;
    return palindromo(s, inicio + 1, fim - 1);
}

// Uso: palindromo(str, 0, strlen(str)-1);
  5. Explique por que a função recursiva de Fibonacci sem otimização é ineficiente e sugira uma melhoria.

    6. ✓ Resposta: A função recursiva ingênua de Fibonacci recalcula os mesmos valores muitas vezes, resultando em complexidade exponencial. Uma melhoria é usar memoização (armazenar resultados em um array) ou implementar iterativamente.