Docs executáveis de C: recursão

Q: O que é recursão em C?

É uma função que chama a si mesma para resolver uma versão menor do mesmo problema. Toda função recursiva precisa de duas coisas: um caso base que retorna sem recursar, e um caso recursivo que se aproxima mensuravelmente dele. Sem o caso base as chamadas nunca param e o programa trava com um estouro de pilha.

Q: Como escrever uma função fatorial em C?

int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); }. O caso base trata 0 e 1, e cada chamada recursiva reduz n em um até chegar lá. Note que int transborda em 13! - use unsigned long long para valores maiores.

Q: Por que o Fibonacci recursivo é tão lento em C?

Porque fib(n) chama fib(n-1) e fib(n-2), que recalculam os mesmos subproblemas repetidamente - o número de chamadas cresce exponencialmente, então fib(50) levaria anos. Reescrevê-lo como um laço que guarda os dois últimos valores o torna linear e instantâneo.

Q: O que causa um estouro de pilha na recursão em C?

Cada chamada ocupa um quadro de memória na pilha para seus parâmetros e variáveis locais, e a pilha tem só alguns megabytes. Um caso base ausente ou inalcançável significa recursão infinita e travamento imediato; mesmo uma recursão correta que desce centenas de milhares de níveis pode esgotar a pilha.

Uma função que chama a si mesma

Nada impede uma função em C de chamar a si mesma. O próprio nome dela está em escopo dentro do seu corpo, então isto é legal:

void countdown(int n) {
    printf("%d\n", n);
    countdown(n - 1);      /* chama a si mesma - mas nunca para! */
}

Também está quebrada. Ela imprime para sempre, entrando nos negativos, até o programa travar. O que falta é um caso base: uma condição sob a qual a função retorna sem chamar a si mesma.

#include <stdio.h>

void countdown(int n) {
    if (n <= 0) {              /* caso base: para */
        printf("Decolar!\n");
        return;
    }
    printf("%d\n", n);
    countdown(n - 1);          /* caso recursivo: um problema menor */
}

int main(void) {
    countdown(5);
    return 0;
}

Toda função recursiva tem exatamente estas duas partes:

Um caso base - a menor entrada, respondida diretamente, sem mais nenhuma chamada.
Um caso recursivo - resolve o problema em termos de uma versão estritamente menor de si mesmo.

"Estritamente menor" é a parte que as pessoas erram. countdown(n - 1) se move em direção a 0 a cada chamada. countdown(n) não se moveria, e countdown(n / 2) também não, se n pudesse ser 1 para sempre. Todo caminho precisa encolher o problema, ou o caso base nunca é alcançado.

Fatorial

O primeiro exemplo clássico. n! é n × (n-1) × ... × 1, e 0! é definido como 1. Essa definição já é recursiva: n! = n × (n-1)!.

#include <stdio.h>

unsigned long long factorial(int n) {
    if (n <= 1) {                       /* caso base: 0! e 1! sao ambos 1 */
        return 1;
    }
    return n * factorial(n - 1);        /* caso recursivo */
}

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

Acompanhe factorial(4) para ver como a resposta é montada. As chamadas descem, e as multiplicações acontecem na volta:

factorial(4)  -> 4 * factorial(3)
                      factorial(3) -> 3 * factorial(2)
                                           factorial(2) -> 2 * factorial(1)
                                                                factorial(1) -> 1   (caso base)
                                           factorial(2) = 2 * 1  = 2
                      factorial(3) = 3 * 2  = 6
factorial(4)  = 4 * 6  = 24

Nada é multiplicado até o caso base retornar. Cada chamada pendente fica esperando, segurando o seu próprio n, que é o ponto que vale internalizar: essas chamadas em espera ocupam memória.

Repare no tipo de retorno. int transborda por volta de 13!, produzindo silenciosamente um número errado - o C não verifica. unsigned long long leva você até 20! e não além, porque 21! passa de 64 bits. A recursão não é o fator limitante aqui; o tipo é.

O caso base usa n <= 1 em vez de n == 1 deliberadamente: factorial(0) deve ser 1, e o <= cuida disso. Com n == 1, chamar factorial(0) recursaria até -1, -2, e nunca terminaria - uma boa ilustração de como um caso base "obviamente correto" pode deixar passar uma entrada.

Fibonacci, e por que a versão ingênua é uma armadilha

Fibonacci é o outro clássico: cada número é a soma dos dois anteriores, começando em 0 e 1. A definição recursiva se escreve sozinha.

#include <stdio.h>

long long calls = 0;

int fib(int n) {
    calls++;
    if (n < 2) {
        return n;                       /* fib(0) = 0, fib(1) = 1 */
    }
    return fib(n - 1) + fib(n - 2);
}

int main(void) {
    for (int n = 10; n <= 35; n += 5) {
        calls = 0;
        int result = fib(n);
        printf("fib(%2d) = %-8d (%lld chamadas)\n", n, result, calls);
    }
    return 0;
}

Olhe as contagens de chamadas. fib(10) leva 177 chamadas; fib(35) leva quase 30 milhões. Cada passo de 5 multiplica o trabalho por cerca de onze.

A razão fica visível na árvore de chamadas. fib(5) chama fib(4) e fib(3); fib(4) chama fib(3) de novo; e cada um deles recalcula fib(2) do zero. Nada é lembrado, então os mesmos subproblemas são resolvidos repetidas vezes, e o número de chamadas cresce mais ou menos como 1,6ⁿ. fib(50) desse jeito rodaria por dias; fib(100) duraria mais que o universo.

A versão com laço guarda os dois últimos valores e é linear:

#include <stdio.h>

long long fibFast(int n) {
    if (n < 2) {
        return n;
    }
    long long prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        long long next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

int main(void) {
    for (int n = 10; n <= 90; n += 10) {
        printf("fib(%2d) = %lld\n", n, fibFast(n));
    }
    return 0;
}

fib(90) retorna na hora. A lição não é "recursão é lenta" - é que recursão com subproblemas sobrepostos é lenta a não ser que você guarde as respostas. Armazene os resultados num array conforme os calcula (memoização) e a versão recursiva também fica linear.

A pilha de chamadas e o estouro de pilha

Toda chamada de função precisa de algum lugar para guardar seus parâmetros, suas variáveis locais e o endereço de retorno. Esse armazenamento é um quadro de pilha (stack frame), empilhado quando a chamada começa e desempilhado quando ela retorna. A recursão empilha quadros um em cima do outro - factorial(1000) tem mil quadros vivos ao mesmo tempo, cada um com o seu próprio n.

A pilha não é grande. Um padrão típico é de 1 a 8 MB, então algumas dezenas de milhares de quadros é o limite realista, e bem menos se cada quadro guardar um array local grande. Passe disso e o programa morre:

Segmentation fault (core dumped)

Isso é um estouro de pilha, e há duas formas de conseguir um:

Recursão infinita - um caso base ausente ou inalcançável. Isso é um bug, e o travamento é imediato:

int bad(int n) {
    return bad(n - 1);      /* sem caso base - trava numa fracao de segundo */
}

Correta, mas profunda demais - recursar uma vez por elemento numa lista de um milhão de itens. A lógica está certa; a abordagem não cabe na pilha. Reescreva como um laço, ou reestruture para que a profundidade seja logarítmica (recursar sobre metades, como fazem a busca binária e o merge sort, dá uma profundidade de cerca de 20 para um milhão de itens).

Alguns compiladores conseguem transformar a recursão de cauda - em que a chamada recursiva é a última coisa que a função faz, sem trabalho pendente depois dela - num laço, reutilizando um único quadro. O countdown acima é recursivo de cauda; factorial não é, porque a multiplicação ainda precisa acontecer depois que a chamada retorna. Mas o C não exige essa otimização, então ela pode ou não acontecer dependendo do compilador e das flags. Nunca escreva um C que só funciona porque o otimizador eliminou uma chamada de cauda.

Onde a recursão realmente vence

Toda função recursiva pode ser reescrita como um laço, e para contagens simples o laço é claramente melhor. A recursão se justifica quando os próprios dados são recursivos - quando uma estrutura contém cópias menores de si mesma.

A busca binária é um exemplo limpo: procure numa metade, depois na metade dessa metade.

#include <stdio.h>

/* devolve o indice do alvo, ou -1 */
int binarySearch(const int a[], int low, int high, int target) {
    if (low > high) {
        return -1;                          /* caso base: nao sobrou nada */
    }
    int mid = low + (high - low) / 2;       /* evita overflow em indices grandes */

    if (a[mid] == target) {
        return mid;                         /* caso base: achou */
    }
    if (a[mid] < target) {
        return binarySearch(a, mid + 1, high, target);
    }
    return binarySearch(a, low, mid - 1, target);
}

int main(void) {
    int sorted[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(sorted) / sizeof(sorted[0]);

    int targets[] = {23, 2, 91, 50};
    for (int i = 0; i < 4; i++) {
        printf("%2d -> indice %d\n", targets[i], binarySearch(sorted, 0, n - 1, targets[i]));
    }
    return 0;
}

São dois casos base aqui, o que é normal: um para o sucesso e outro para o esgotamento. A profundidade é de cerca de log₂(n), então até um bilhão de elementos precisa de apenas trinta quadros.

Outros lugares em que a recursão é o encaixe natural: percorrer uma árvore ou uma lista encadeada, varrer diretórios, analisar expressões aninhadas e ordenações de dividir-para-conquistar como quicksort e merge sort. Em todos eles o código recursivo é mais curto e mais claro que o laço com pilha explícita que o substituiria.

Recursão ou laço?

Use um laco quando       o problema e linear - contar, somar, varrer
Use recursao quando      os dados sao aninhados - arvores, estruturas aninhadas, dividir para conquistar
Reescreva a recursao     se a profundidade puder crescer sem limite com o tamanho da entrada
Nunca use recursao       quando os subproblemas se sobrepoem, a menos que voce memoize

Duas notas práticas. Chamadas recursivas custam um pouco mais que uma iteração de laço - um quadro para empilhar e desempilhar a cada vez - então para laços quentes e simples a versão iterativa vence tanto em velocidade quanto em memória. E depurar é diferente: um rastro de pilha de uma recursão profunda são centenas de quadros idênticos, então imprima o parâmetro na entrada (como faz o contador calls acima) quando algo não estiver terminando.

Escrevendo uma função recursiva: uma lista de conferência

Ache o caso base primeiro. Qual é a menor entrada, e qual é a resposta dela? Se você não consegue nomeá-la, a função não pode ser escrita.
Assuma que a chamada recursiva funciona. Não a percorra mentalmente - confie que factorial(n - 1) devolve (n-1)! e escreva o único passo que transforma isso na resposta.
Confira se todo caminho encolhe. Cada chamada recursiva precisa se mover em direção ao caso base para toda entrada possível, incluindo 0 e negativos.
Confira a profundidade. Grosso modo, quantos quadros de profundidade isso vai atingir com dados reais? Milhares tudo bem; milhões não.
Confira a sobreposição. Se o mesmo subproblema é calculado duas vezes, você precisa de memoização ou de um laço.

Perguntas frequentes

O que é recursão em C?

É uma função que chama a si mesma para resolver uma versão menor do mesmo problema. Toda função recursiva precisa de duas coisas: um caso base que retorna sem recursar, e um caso recursivo que se aproxima mensuravelmente dele. Sem o caso base as chamadas nunca param e o programa trava com um estouro de pilha.

Como escrever uma função fatorial em C?

int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); }. O caso base trata 0 e 1, e cada chamada recursiva reduz n em um até chegar lá. Note que int transborda em 13! - use unsigned long long para valores maiores.

Por que o Fibonacci recursivo é tão lento em C?

Porque fib(n) chama fib(n-1) e fib(n-2), que recalculam os mesmos subproblemas repetidamente - o número de chamadas cresce exponencialmente, então fib(50) levaria anos. Reescrevê-lo como um laço que guarda os dois últimos valores o torna linear e instantâneo.

O que causa um estouro de pilha na recursão em C?

Cada chamada ocupa um quadro de memória na pilha para seus parâmetros e variáveis locais, e a pilha tem só alguns megabytes. Um caso base ausente ou inalcançável significa recursão infinita e travamento imediato; mesmo uma recursão correta que desce centenas de milhares de níveis pode esgotar a pilha.

Conceitos relacionados