Compreendendo a Recursividade em C

Antes de mergulhar na recursividade, é essencial entender como a pilha de memória funciona. Considere o seguinte exemplo que demonstra o endereçamento de variáveis:

#include <stdio.h>

int main() {
    int primeiro = 15;
    int segundo = 25;
    printf("Endereço de primeiro: %p\n", &primeiro);
    printf("Endereço de segundo: %p\n", &segundo);
    return 0;
}

Em ambientes de 64 bits, as variáveis são alocadas primeiro em endereços mais baixos, mas em arquiteturas de 32 bits, o comportamento da pilha pode inverter, utilizando inicialmente endereços mais altos.

Para ilustrar implicações práticas, observe este código que causa um comportamento indefinido devido a estouro de pilha:

#include <stdio.h>

int main() {
    int contador = 0;
    int matriz[5] = {10, 20, 30, 40, 50};
    for (contador = 0; contador <= 7; contador++) {
        matriz[contador] = 0;
        printf("Iteração %d concluída.\n", contador);
    }
    return 0;
}

Em compilações de depuração, isso pode levar a um loop infinito, enquanto versões otimizadas podem executar sem erros visíveis, evidenciando como a alocação de pilha varia entre modos de depuração e lançamento.

O que é Recursividade?

Recursividade é uma técnica onde uma função chama a si mesma para resolver subproblemas menores de um problema complexo. Ela opera em dois pilares: uma condição base que encerra a recursão e cada chamada deve se aproximar progressivamente dessa condição.

Exemplo Prático: Cálculo de Fatorial

O fatorial de um número n é definido como n * (n-1) para n > 0, e 1 para n = 0. Implementação recursiva:

#include <stdio.h>

int calcular_fatorial(int num) {
    if (num == 0) {
        return 1;
    }
    return num * calcular_fatorial(num - 1);
}

int main() {
    int entrada;
    scanf("%d", &entrada);
    int resultado = calcular_fatorial(entrada);
    printf("Fatorial de %d é %d\n", entrada, resultado);
    return 0;
}

Cada chamada recursiva aloca um espaço na pilha para variáveis locais e contexto, o que pode levar a estouro de pilha se a profundidade for excessiva.

Impressão de Dígitos em Ordem

Para imprimir os dígitos de um inteiro da esquerda para a direita, podemos usar recursão para processar o número divisível:

#include <stdio.h>

void imprimir_digitos(int valor) {
    if (valor > 9) {
        imprimir_digitos(valor / 10);
    }
    printf("%d ", valor % 10);
}

int main() {
    int num;
    scanf("%d", &num);
    imprimir_digitos(num);
    printf("\n");
    return 0;
}

Limitações: Sequência de Fibonacci

A sequência de Fibonacci pode ser implementada recursivamente, mas para valores grandes, a eficiência cai drasticamente devido a chamadas redundantes:

#include <stdio.h>

int fib_recursivo(int n) {
    if (n <= 2) {
        return 1;
    }
    return fib_recursivo(n - 1) + fib_recursivo(n - 2);
}

int main() {
    int termo;
    scanf("%d", &termo);
    printf("Fibonacci(%d) = %d\n", termo, fib_recursivo(termo));
    return 0;
}

Uma abordagem iterativa é muito mais eficiente, evitando sboreposição de cálculos:

#include <stdio.h>

int fib_iterativo(int n) {
    if (n <= 2) return 1;
    int anterior1 = 1, anterior2 = 1, atual = 0;
    for (int i = 3; i <= n; i++) {
        atual = anterior1 + anterior2;
        anterior1 = anterior2;
        anterior2 = atual;
    }
    return atual;
}

int main() {
    int num;
    scanf("%d", &num);
    printf("Fibonacci iterativo de %d é %d\n", num, fib_iterativo(num));
    return 0;
}

Escolha entre Recursão e Iteração

Prefira recursão quando simplifica a lógica e a profundidade é gerenciável. Para problemas com requisitos de desempenho ou risco de estouro, iteração é preferível. Estruturas de dados como árvores frequentemente empregam recursividade de forma natural.