Recursão em C

1. Introdução à Recursão

Recursão é uma técnica de programação onde uma função chama a si mesma durante sua execução. Uma função recursiva deve conter dois elementos fundamentais: o caso base (condição de parada) e o caso recursivo (chamada à própria função com parâmetros modificados).

O exemplo clássico é o cálculo do fatorial:

int fat(int n) {
    if (n <= 1)          // Caso base
        return 1;
    return n * fat(n-1); // Caso recursivo
}

Para fat(4), a execução ocorre assim: 4 * fat(3) → 3 * fat(2) → 2 * fat(1) → retorna 1, então temos 2 * 1 = 2, 3 * 2 = 6, 4 * 6 = 24.

2. Mecanismo de Pilha (Stack) na Recursão

Cada chamada recursiva cria um novo quadro de pilha (stack frame) na call stack. Esse quadro armazena:

  • Parâmetros da função
  • Variáveis locais
  • Endereço de retorno (para onde voltar após a chamada)
#include <stdio.h>

void recursiva(int n) {
    int local = n * 10;  // Variável local em cada nível
    printf("Entrando: n=%d, local=%d\n", n, local);

    if (n > 0)
        recursiva(n - 1);

    printf("Saindo: n=%d, local=%d\n", n, local);
}

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

Saída:

Entrando: n=3, local=30
Entrando: n=2, local=20
Entrando: n=1, local=10
Entrando: n=0, local=0
Saindo: n=0, local=0
Saindo: n=1, local=10
Saindo: n=2, local=20
Saindo: n=3, local=30

Observe que as variáveis locais são preservadas em cada nível da pilha.

3. Recursão Direta vs. Recursão Indireta

Recursão direta: a função chama a si mesma diretamente, como no exemplo do fatorial.

Recursão indireta (ou mútua): duas ou mais funções se chamam alternadamente:

#include <stdio.h>

int impar(int n);  // Declaração antecipada

int par(int n) {
    if (n == 0) return 1;
    return impar(n - 1);
}

int impar(int n) {
    if (n == 0) return 0;
    return par(n - 1);
}

int main() {
    printf("4 é par? %d\n", par(4));   // 1 (verdadeiro)
    printf("5 é par? %d\n", par(5));   // 0 (falso)
    return 0;
}

4. Recursão de Cauda (Tail Recursion)

Uma função tem recursão de cauda quando a chamada recursiva é a última operação executada. Compiladores modernos podem otimizar isso (tail call optimization), transformando a recursão em iteração para evitar crescimento da pilha.

Fatorial sem recursão de cauda (já visto):

int fat(int n) {
    if (n <= 1) return 1;
    return n * fat(n-1);  // Multiplicação após retorno
}

Fatorial com recursão de cauda:

int fat_tail(int n, int acumulador) {
    if (n <= 1) return acumulador;
    return fat_tail(n - 1, n * acumulador);  // Chamada é a última operação
}

int fat(int n) {
    return fat_tail(n, 1);
}

Com -O2 ou -O3, o GCC pode otimizar a versão tail para usar um simples loop.

5. Recursão vs. Iteração

Aspecto Recursão Iteração
Clareza Código mais próximo da definição matemática Pode ser mais verboso
Memória Overhead da pilha (cada chamada gasta ~32-64 bytes) Apenas algumas variáveis
Performance Mais lenta devido a chamadas de função Mais rápida
Risco Estouro de pilha para recursão profunda Sem risco de estouro

Quando usar recursão:
- Problemas naturalmente recursivos (árvores, grafos, algoritmos de divisão e conquista)
- Quando a profundidade máxima é pequena e previsível
- Quando a clareza do código é mais importante que performance

Quando usar iteração:
- Quando a profundidade pode ser grande (ex.: processar 100.000 itens)
- Em sistemas embarcados com pilha limitada
- Quando performance é crítica

6. Problemas Clássicos com Recursão

Sequência de Fibonacci (versão ingênua)

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);  // Muito ineficiente!
}

Fibonacci com memorização (top-down)

#define MAX 100
int memo[MAX] = {0};

int fib_memo(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fib_memo(n-1) + fib_memo(n-2);
    return memo[n];
}

Torre de Hanói

#include <stdio.h>

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);
}

int main() {
    hanoi(3, 'A', 'C', 'B');
    return 0;
}

Busca binária recursiva

int busca_binaria(int arr[], int esq, int dir, int alvo) {
    if (esq > dir) return -1;  // Não encontrado

    int meio = esq + (dir - esq) / 2;

    if (arr[meio] == alvo) return meio;
    if (arr[meio] > alvo) return busca_binaria(arr, esq, meio-1, alvo);
    return busca_binaria(arr, meio+1, dir, alvo);
}

7. Cuidados e Armadilhas em C

Estouro de pilha: Cada chamada recursiva consome espaço na pilha. Em sistemas embarcados, a pilha pode ter apenas 1KB. Uma recursão de 100 níveis pode estourá-la.

Variáveis estáticas: Cuidado ao usar static em funções recursivas, pois o valor persiste entre chamadas:

int recursiva_com_estatica(int n) {
    static int contador = 0;  // Inicializado apenas uma vez!
    contador++;
    if (n <= 0) return contador;
    return recursiva_com_estatica(n-1);
}

Ponteiros e estruturas recursivas (ex.: lista encadeada):

struct No {
    int dado;
    struct No* proximo;
};

void imprimir_lista(struct No* cabeca) {
    if (cabeca == NULL) return;
    printf("%d ", cabeca->dado);
    imprimir_lista(cabeca->proximo);  // Recursão na estrutura
}

8. Debugging de Funções Recursivas

Usando printf para rastreamento

int busca_arvore(No* raiz, int alvo, int profundidade) {
    if (raiz == NULL) {
        printf("%*sNULL\n", profundidade*2, "");
        return 0;
    }

    printf("%*sBuscando %d em no %d\n", profundidade*2, "", alvo, raiz->valor);

    if (raiz->valor == alvo) return 1;

    int encontrado = busca_arvore(raiz->esq, alvo, profundidade+1) ||
                     busca_arvore(raiz->dir, alvo, profundidade+1);

    printf("%*sRetornando %d\n", profundidade*2, "", encontrado);
    return encontrado;
}

Depuração com GDB

gcc -g programa.c -o programa
gdb ./programa
(gdb) break busca_arvore if raiz->valor == 42
(gdb) run
(gdb) backtrace   # Mostra toda a cadeia de chamadas
(gdb) info frame  # Mostra variáveis do quadro atual
(gdb) frame 3     # Navega para o terceiro quadro da pilha

Referências