Recursão é uma técnica de programação onde uma função chama a si mesma para resolver um problema menor da mesma natureza. Em C, como em muitas linguagens, a recursão permite escrever código mais limpo e próximo da definição matemática do problema, especialmente para estruturas como árvores, listas encadeadas e algoritmos de divisão e conquista.

Entender recursão exige compreender dois elementos fundamentais: o caso base (que interrompe a recursão) e a pilha de chamadas (que gerencia o retorno das chamadas). Nesta aula, vamos explorar esses conceitos com exemplos práticos e discutir os limites da recursão em C.

Conceito

Recursão ocorre quando uma função, durante sua execução, invoca a si mesma. Cada chamada recursiva cria uma nova instância da função, com seus próprios parâmetros e variáveis locais. O problema original é decomposto em subproblemas menores, até que um subproblema seja trivial o suficiente para ser resolvido diretamente (caso base).

Por exemplo, o cálculo do fatorial de um número n (n!) pode ser definido recursivamente: n! = n * (n-1)!, com 0! = 1. Em C, isso se traduz em uma função que chama a si mesma com n-1 até atingir n=0.

#include <stdio.h>

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

int main() {
    int n = 5;
    printf("Fatorial de %d = %d\n", n, fatorial(n));
    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 infinitamente (até estourar a pilha). O caso base deve ser alcançável e não deve conter chamadas recursivas. Em geral, é uma condição simples, como um valor mínimo ou uma estrutura vazia.

No exemplo do fatorial, o caso base é n == 0, que retorna 1. Para a sequência de Fibonacci, o caso base é n == 0 ou n == 1, retornando n. Escolher o caso base correto é essencial para que a recursão funcione e termine.

int fibonacci(int n) {
    if (n == 0 || n == 1) {   // caso base
        return n;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

Pilha de chamadas

A pilha de chamadas (call stack) é uma estrutura de dados que gerencia a execução das funções. Cada vez que uma função é chamada, um novo registro de ativação (stack frame) é empilhado, contendo endereço de retorno, parâmetros e variáveis locais. Quando a função retorna, seu frame é desempilhado e o controle volta ao ponto de chamada.

Na recursão, múltiplos frames são empilhados sequencialmente. Por exemplo, ao calcular fatorial(3), a pilha recebe frames para fatorial(3), fatorial(2), fatorial(1) e fatorial(0). Quando fatorial(0) retorna 1, o frame é desempilhado, e então fatorial(1) completa, e assim por diante. Isso significa que a recursão consome memória proporcional à profundidade da recursão.

// Simulação da pilha para fatorial(3):
// fatorial(3) chama fatorial(2)
// fatorial(2) chama fatorial(1)
// fatorial(1) chama fatorial(0)
// fatorial(0) retorna 1
// fatorial(1) retorna 1*1 = 1
// fatorial(2) retorna 2*1 = 2
// fatorial(3) retorna 3*2 = 6

Exemplos e limites

Além do fatorial e Fibonacci, a recursão é útil para percorrer estruturas como árvores binárias (busca, inserção) e algoritmos como quick sort, merge sort e busca binária. No entanto, a recursão tem limitações práticas em C:

  • Estouro de pilha (stack overflow): Se a profundidade da recursão for muito grande (ex.: milhares de chamadas), a pilha pode exceder o limite de memória reservada para ela, causando falha no programa.
  • Desempenho: Recursão pode ser mais lenta que iteração devido ao overhead de chamadas de função e uso de pilha. Fibonacci recursivo tem complexidade exponencial O(2^n), enquanto a versão iterativa é O(n).
  • Limite de profundidade: Em sistemas embarcados ou com recursos limitados, a profundidade máxima da recursão é pequena.

Para evitar estouro, pode-se usar recursão de cauda (tail recursion) quando possível, embora o compilador C não garanta otimização (TCO). Em muitos casos, a iteração é preferível para problemas que exigem muitas repetições.

// Exemplo de recursão de cauda (fatorial com acumulador)
int fatorial_tail(int n, int acc) {
    if (n == 0) return acc;
    return fatorial_tail(n - 1, n * acc);
}
// Uso: fatorial_tail(5, 1) retorna 120

Boas práticas

1. Sempre defina um caso base claro e verificável.
2. Certifique-se de que a cada chamada recursiva você se aproxima do caso base.
3. Evite recursão profunda (mais de alguns milhares) em C; prefira iteração.
4. Use recursão para problemas naturalmente recursivos (árvores, grafos, divisão e conquista).
5. Teste com valores pequenos antes de escalar.

Referências

Exercícios

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

    ✓ Resposta:
    int soma_naturais(int n) {
    if (n == 0) {
        return 0;
    } else {
        return n + soma_naturais(n - 1);
    }
}

  2. Implemente uma função recursiva que inverta uma string (modificando a string original).

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

  3. Crie uma função recursiva que retorne o n-ésimo termo da sequência de Tribonacci (T0=0, T1=0, T2=1, Tn = Tn-1 + Tn-2 + Tn-3).

    ✓ Resposta:
    int tribonacci(int n) {
    if (n == 0 || n == 1) return 0;
    if (n == 2) return 1;
    return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3);
}

  4. Escreva uma função recursiva que conte o número de dígitos de um inteiro positivo.

    ✓ Resposta:
    int contar_digitos(int n) {
    if (n == 0) return 0;
    return 1 + contar_digitos(n / 10);
}
// Para n=0, retornar 1 se desejar; mas aqui tratamos 0 como 0 dígitos.

  5. Implemente uma função recursiva que calcule o máximo divisor comum (MDC) de dois números usando o algoritmo de Euclides.

    ✓ Resposta:
    int mdc(int a, int b) {
    if (b == 0) {
        return a;
    }
    return mdc(b, a % b);
}