C Recursão

Na aula Funções você viu que uma função pode chamar outra. Ela também pode chamar a si mesma. Isso se chama recursão. Parece um truque de mágica (como uma função que ainda não terminou pode usar a si própria?), mas é só uma forma de resolver um problema grande com a versão menor do mesmo problema. Nesta aula você vai escrever suas primeiras funções recursivas, ver a "pilha de chamadas" crescer e encolher, descobrir quando a recursão fica lenta demais e ver o programa morrer quando ela não tem fim.

Todos os programas foram compilados com o gcc 15.2 na máquina fictícia da Ana (usuária ana, computador notebook), na pasta ~/c, com o comando padrão do guia: gcc -std=c23 -Wall -Wextra arquivo.c -o programa. Você pode repetir cada um no editor do guia.

A ideia: as bonecas russas

A Ana ganhou uma matriosca, aquela boneca russa que tem uma boneca menor dentro, que tem outra menor dentro, e assim por diante. Para chegar à bonequinha do centro, ela segue uma única regra:

• Se a boneca é a menorzinha (não abre mais), achei! Parei.
• Senão, abro a boneca e faço a mesma coisa com a boneca de dentro.

Repare que a regra usa a si mesma ("faço a mesma coisa"), mas sempre com uma boneca menor. Por isso ela termina: uma hora chega a boneca que não abre. Toda função recursiva tem essas duas partes:

Esqueça o caso base, ou faça o problema não diminuir, e a função chama a si mesma para sempre (bom, quase: a seção 5 mostra como o programa morre).

1. A primeira função recursiva: contagem regressiva

A Ana quer uma contagem para a largada da corrida da escola: 3... 2... 1... Já!. Com um laço seria fácil (for). Com recursão, o raciocínio é: "contar a partir de 3 é mostrar 3 e depois contar a partir de 2".

#include <stdio.h>

void contagem(int n) {
    if (n == 0) {
        printf("Já!\n");
        return;
    }
    printf("%d...\n", n);
    contagem(n - 1);
}

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

void contagem(int n)

Uma função comum, que recebe um número (Parâmetros) e não devolve nada.

if (n == 0) { printf("Já!\n"); return; }

O caso base: quando a contagem chega a zero, a função mostra Já! e não chama mais ninguém. O return; sai da função na hora (Valor de Retorno).

printf("%d...\n", n);

Mostra o número atual.

contagem(n - 1);

O passo recursivo: a função chama a si mesma com um número menor. Cada chamada chega mais perto do zero.

$ gcc -std=c23 -Wall -Wextra contagem.c -o contagem
$ ./contagem
3...
2...
1...
Já!

O que aconteceu, chamada por chamada:

1. O main chama contagem(3). Como 3 não é 0, ela mostra 3... e chama contagem(2).
2. contagem(2) mostra 2... e chama contagem(1).
3. contagem(1) mostra 1... e chama contagem(0).
4. contagem(0) cai no caso base: mostra Já! e retorna.
5. Então contagem(1) termina (não há mais nada depois da chamada), depois contagem(2), depois contagem(3), e o programa volta ao main.

Um detalhe importante: contagem(3), contagem(2), contagem(1) e contagem(0) são quatro chamadas diferentes, e cada uma tem o seu próprio n. É como na aula Escopo: a variável local nasce a cada chamada. O n que vale 3 continua lá, esperando, enquanto as chamadas de dentro rodam com os seus n.

A ida e a volta

Uma chamada recursiva divide a função em duas partes: o que vem antes dela roda na ida (abrindo as bonecas); o que vem depois só roda na volta, quando a chamada de dentro termina (fechando as bonecas). Veja com dois printf, um de cada lado:

#include <stdio.h>

void boneca(int n) {
    printf("abrindo a boneca %d\n", n);
    if (n > 1) {
        boneca(n - 1);
    }
    printf("fechando a boneca %d\n", n);
}

int main(void) {
    boneca(3);
    return 0;
}

$ gcc -std=c23 -Wall -Wextra idavolta.c -o idavolta
$ ./idavolta
abrindo a boneca 3
abrindo a boneca 2
abrindo a boneca 1
fechando a boneca 1      « a boneca 1 é o caso base: não abre outra
fechando a boneca 2
fechando a boneca 3

Aqui o caso base está escrito "ao contrário": em vez de if (n == 1) return;, a função só chama a si mesma se n > 1. As duas formas são comuns. O que importa é que existe um valor de n em que a função não chama mais ninguém.

Repare na ordem da volta: 1, 2, 3. A última boneca aberta é a primeira a ser fechada. As chamadas se empilham como pratos: o último prato colocado na pilha é o primeiro a sair.

#include <stdio.h>

void boneca(int n) {
    printf("abrindo a boneca %d\n", n);
    if (n > 1) {
        boneca(n - 1);
    }
    printf("fechando a boneca %d\n", n);
}

int main(void) {
    boneca(3);
    return 0;
}

2. Devolver um valor: o fatorial

O fatorial de um número, escrito n!, é a multiplicação de todos os inteiros de 1 até ele: 4! = 4 × 3 × 2 × 1 = 24. Ele responde, por exemplo, de quantas formas diferentes 4 pessoas podem formar uma fila. Repare que dentro de 4! está escondido o 3!:

• 4! = 4 × (3 × 2 × 1) = 4 × 3!
• e, em geral, n! = n × (n - 1)!;
• com o caso base 1! = 1 (e, por convenção da matemática, 0! = 1).

Essa definição vira código quase palavra por palavra:

#include <stdio.h>

int fatorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * fatorial(n - 1);
}

int main(void) {
    for (int i = 0; i <= 5; i++) {
        printf("%d! = %d\n", i, fatorial(i));
    }
    return 0;
}

int fatorial(int n)

Agora a função devolve um int: o resultado da conta.

if (n <= 1) { return 1; }

O caso base: 0! e 1! valem 1. O <= (em vez de ==) cobre os dois de uma vez.

return n * fatorial(n - 1);

O passo recursivo. Para devolver o resultado, a função primeiro precisa saber quanto vale fatorial(n - 1): ela chama a si mesma, espera a resposta, multiplica por n e só então devolve.

$ gcc -std=c23 -Wall -Wextra fatorial.c -o fatorial
$ ./fatorial
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120

A pilha de chamadas, passo a passo

Como fatorial(4) chega a 24? Cada chamada fica "pendurada", esperando a resposta da chamada de dentro. O computador guarda as chamadas pendentes numa estrutura chamada pilha de chamadas (call stack): cada chamada ganha uma "bandeja" com as suas variáveis, empilhada em cima da anterior.

A pilha de chamadas é a mesma pilha de memória onde moram as variáveis locais. Ela tem um tamanho limitado (no Linux, 8 MB), o que vai importar na seção 5. A aula Pilha e Heap, no Nível 2, mostra essa memória em detalhes.

O fatorial cresce rápido

O fatorial cresce tão depressa que estoura o int logo no 13. Com long long (Inteiros) vai até o 20:

#include <stdio.h>

int fatorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * fatorial(n - 1);
}

long long fatorial_ll(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * fatorial_ll(n - 1);
}

int main(void) {
    printf("12! com int:       %d\n", fatorial(12));
    printf("13! com int:       %d\n", fatorial(13));
    printf("13! com long long: %lld\n", fatorial_ll(13));
    printf("20! com long long: %lld\n", fatorial_ll(20));
    printf("21! com long long: %lld\n", fatorial_ll(21));
    return 0;
}

$ gcc -std=c23 -Wall -Wextra fatorial13.c -o fatorial13
$ ./fatorial13
12! com int:       479001600
13! com int:       1932053504               « errado: o certo é 6227020800
13! com long long: 6227020800
20! com long long: 2432902008176640000
21! com long long: -4249290049419214848     « estourou até o long long

Nenhum aviso: o compilador não sabe com que números você vai chamar a função. O estouro de um inteiro com sinal é comportamento indefinido; aqui ele apareceu como um número errado. Isso não é culpa da recursão: um laço daria os mesmos números. É só um lembrete de escolher um tipo que caiba o resultado.

soma(1) = 1
soma(4) = 10
soma(100) = 5050

#include <stdio.h>

int soma(int n) {
    if (n == 1) {
        return 1;
    }
    return 0;   // troque o 0 pelo passo recursivo
}

int main(void) {
    printf("soma(1) = %d\n", soma(1));
    printf("soma(4) = %d\n", soma(4));
    printf("soma(100) = %d\n", soma(100));
    return 0;
}

#include <stdio.h>

int soma(int n) {
    if (n == 1) {
        return 1;
    }
    return n + soma(n - 1);
}

int main(void) {
    printf("soma(1) = %d\n", soma(1));
    printf("soma(4) = %d\n", soma(4));
    printf("soma(100) = %d\n", soma(100));
    return 0;
}

3. Usar a volta: um número em binário

Às vezes a recursão é a forma mais simples de resolver o problema. Para escrever um número em binário (a base 2, explicada em Operadores de Bits), o jeito clássico é dividir por 2 várias vezes e anotar os restos. O problema: os restos saem de trás para a frente. Para 6: 6 % 2 = 0, 3 % 2 = 1, 1 % 2 = 1, e o binário de 6 é 110, os restos lidos do último para o primeiro.

Com recursão, a inversão sai de graça. A função primeiro escreve o resto do número (chamando a si mesma com n / 2) e só na volta escreve o último dígito:

#include <stdio.h>

void binario(int n) {
    if (n >= 2) {
        binario(n / 2);
    }
    printf("%d", n % 2);
}

int main(void) {
    int numeros[] = {5, 6, 13, 255};
    for (int i = 0; i < 4; i++) {
        printf("%3d em binário: ", numeros[i]);
        binario(numeros[i]);
        printf("\n");
    }
    return 0;
}

if (n >= 2) { binario(n / 2); }

Se o número tem mais de um dígito em binário, escreva primeiro os dígitos da frente, que são o binário de n / 2. Quando n é 0 ou 1 (caso base), não há nada na frente.

printf("%d", n % 2);

Depois da chamada, na volta: escreve o último dígito, o resto da divisão por 2.

$ gcc -std=c23 -Wall -Wextra binario.c -o binario
$ ./binario
  5 em binário: 101
  6 em binário: 110
 13 em binário: 1101
255 em binário: 11111111

Para binario(6): a chamada com 6 chama a com 3, que chama a com 1. A com 1 escreve 1; na volta, a com 3 escreve 3 % 2 = 1; por último, a com 6 escreve 6 % 2 = 0. Resultado: 110. Troque a ordem (o printf antes do if) e os dígitos saem invertidos.

4. O custo escondido: Fibonacci

A sequência de Fibonacci começa com 0 e 1, e cada número seguinte é a soma dos dois anteriores: 0, 1, 1, 2, 3, 5, 8, 13, 21… A definição é recursiva, e o código parece perfeito:

#include <stdio.h>

long long chamadas = 0;

long long fib(int n) {
    chamadas++;
    if (n < 2) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

int main(void) {
    int testes[] = {10, 20, 30, 40};
    for (int i = 0; i < 4; i++) {
        chamadas = 0;
        long long r = fib(testes[i]);
        printf("fib(%d) = %lld, com %lld chamadas\n", testes[i], r, chamadas);
    }
    return 0;
}

long long chamadas = 0;

Uma variável global (Escopo), só para medir: cada vez que fib roda, ela soma 1. Num programa de verdade evitaríamos a global; aqui ela serve de contador.

if (n < 2) { return n; }

Dois casos base de uma vez: fib(0) é 0 e fib(1) é 1.

return fib(n - 1) + fib(n - 2);

Aqui está a novidade: duas chamadas recursivas. Cada uma delas, por sua vez, faz mais duas…

$ gcc -std=c23 -Wall -Wextra fib.c -o fib
$ time ./fib
fib(10) = 55, com 177 chamadas
fib(20) = 6765, com 21891 chamadas
fib(30) = 832040, com 2692537 chamadas
fib(40) = 102334155, com 331160281 chamadas

real	0m1,064s
user	0m1,042s
sys	0m0,000s

Mais de 331 milhões de chamadas para calcular fib(40)! (O time antes do comando mede quanto tempo o programa levou: real é o tempo no relógio, cerca de 1 segundo.) O motivo é que a função recalcula as mesmas coisas muitas vezes. fib(5) chama fib(4) e fib(3); mas fib(4) também chama fib(3). O fib(3) é calculado duas vezes, o fib(2) três vezes, e assim por diante:

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1)
│   │   │   └── fib(0)
│   │   └── fib(1)
│   └── fib(2)
│       ├── fib(1)
│       └── fib(0)
└── fib(3)
    ├── fib(2)
    │   ├── fib(1)
    │   └── fib(0)
    └── fib(1)

Na saída acima, cada vez que n aumenta 10, o número de chamadas fica cerca de 123 vezes maior (331 160 281 ÷ 2 692 537 ≈ 123). O fib(50) levaria uns dois minutos; o fib(60), horas. Um laço que guarda só os dois últimos números faz a mesma conta num instante:

#include <stdio.h>

long long fib(int n) {
    long long anterior = 0;
    long long atual = 1;
    if (n == 0) {
        return 0;
    }
    for (int i = 2; i <= n; i++) {
        long long proximo = anterior + atual;
        anterior = atual;
        atual = proximo;
    }
    return atual;
}

int main(void) {
    printf("fib(40) = %lld\n", fib(40));
    printf("fib(90) = %lld\n", fib(90));
    return 0;
}

$ gcc -std=c23 -Wall -Wextra fiblaco.c -o fiblaco
$ time ./fiblaco
fib(40) = 102334155
fib(90) = 2880067194370816120

real	0m0,001s
user	0m0,001s
sys	0m0,000s

O laço fez 39 voltas para o fib(40), contra 331 milhões de chamadas da versão recursiva. A lição não é "recursão é lenta", e sim: cuidado com a recursão que se divide em várias chamadas e repete trabalho. O fatorial e o binário fazem uma chamada só por vez e não têm esse problema.

#include <stdio.h>

long long chamadas = 0;

long long fib(int n) {
    chamadas++;
    if (n < 2) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

int main(void) {
    int testes[] = {10, 20, 30, 40};
    for (int i = 0; i < 4; i++) {
        chamadas = 0;
        long long r = fib(testes[i]);
        printf("fib(%d) = %lld, com %lld chamadas\n", testes[i], r, chamadas);
    }
    return 0;
}

5. Sem caso base: a pilha estoura

Cada chamada que ainda não terminou ocupa uma bandeja na pilha. Uma função que chama a si mesma sem parar empilha bandejas até a pilha (8 MB no Linux) acabar. Este programa desce os andares de um prédio sem fim e avisa a cada 50 000 andares:

#include <stdio.h>

void descer(int andar) {
    if (andar % 50000 == 0) {
        printf("andar %d\n", andar);
    }
    descer(andar + 1);
}

int main(void) {
    descer(1);
    return 0;
}

$ gcc -std=c23 -Wall -Wextra infinita.c -o infinita
infinita.c: In function ‘descer’:
infinita.c:3:6: warning: infinite recursion detected [-Winfinite-recursion]
    3 | void descer(int andar) {
      |      ^~~~~~
infinita.c:7:5: note: recursive call
    7 |     descer(andar + 1);
      |     ^~~~~~~~~~~~~~~~~
$ ./infinita
andar 50000
andar 100000
andar 150000
andar 200000
andar 250000
Falha de segmentação     (imagem do núcleo gravada) ./infinita
$ echo $?
139

warning: infinite recursion detected

"Recursão infinita detectada". O gcc percebeu que todo caminho pela função chama a função de novo: não há caso base. O if aqui só decide se mostra o andar; com ou sem printf, a chamada acontece.

note: recursive call

"Chamada recursiva": a linha que causa o problema.

andar 250000 … Falha de segmentação

Depois de mais de 250 mil chamadas empilhadas, a pilha acabou e o sistema matou o programa. É o estouro de pilha (stack overflow). O código 139 é o mesmo de qualquer falha de segmentação: a mensagem não diz que a culpa é da recursão.

No editor do guia, o Clang avisa com outras palavras: warning: all paths through this function will call itself [-Winfinite-recursion] ("todos os caminhos por esta função vão chamar a ela mesma"). O programa também morre com Falha de segmentação (imagem do núcleo gravada) e código 139, só que mais cedo, logo depois do andar 50000: no WebAssembly cada chamada ocupa mais espaço na pilha.

O caso base que nunca chega

Pior que esquecer o caso base é ter um que a função pula. A Ana fez uma contagem de 2 em 2:

#include <stdio.h>

void contagem2(int n) {
    if (n == 0) {
        printf("Já!\n");
        return;
    }
    printf("%d ", n);
    contagem2(n - 2);
}

int main(void) {
    contagem2(6);
    contagem2(5);
    return 0;
}

$ gcc -std=c23 -Wall -Wextra pula.c -o pula     « nenhum aviso: existe um caso base
$ ./pula
6 4 2 Já!
5 3 1 -1 -3 -5 -7 -9 -11 -13 -15 -17 -19 -21 -23 -25 -27 -29 -31 -33 -35 -37 -39
                         « cortamos aqui: são mais de 260 mil números, tela após tela
-523829 -523831 -523833 -523835 -523837 -5238Falha de segmentação     (imagem do núcleo gravada) ./pula
$ echo $?
139

Com 6 funcionou: 6, 4, 2, 0. Com 5, a contagem passou por cima do zero: 5, 3, 1, −1, −3… e nunca mais encontrou o n == 0. Ela seguiu pelos negativos até a pilha estourar, depois de mais de 260 mil chamadas. Desta vez o compilador não avisou (nem o gcc, nem o Clang do editor), porque existe um caminho que para; ele não tem como saber que esse caminho nunca vai ser usado. Repare no último número, cortado no meio (-5238): o resto estava no balde do printf, esperando um \n, e se perdeu quando o programa morreu.

6 4 2 Já!
5 3 1 Já!

#include <stdio.h>

void contagem2(int n) {
    if (n == 0) {
        printf("Já!\n");
        return;
    }
    printf("%d ", n);
    contagem2(n - 2);
}

int main(void) {
    contagem2(6);
    contagem2(5);
    return 0;
}

#include <stdio.h>

void contagem2(int n) {
    if (n <= 0) {
        printf("Já!\n");
        return;
    }
    printf("%d ", n);
    contagem2(n - 2);
}

int main(void) {
    contagem2(6);
    contagem2(5);
    return 0;
}

Recursão × laço: qual usar

Tudo o que uma recursão faz, um laço também consegue (às vezes com mais trabalho). O fatorial, por exemplo:

#include <stdio.h>

int fatorial(int n) {
    int resultado = 1;
    for (int i = 2; i <= n; i++) {
        resultado = resultado * i;
    }
    return resultado;
}

int main(void) {
    printf("5! = %d\n", fatorial(5));
    return 0;
}

$ gcc -std=c23 -Wall -Wextra fatlaco.c -o fatlaco
$ ./fatlaco
5! = 120

Regra prática: se o laço é simples, use o laço. Use recursão quando o problema se divide naturalmente em pedaços menores do mesmo tipo e a profundidade é pequena (dezenas ou milhares de chamadas, não milhões). Duas funções que chamam uma à outra também são recursão; a aula Protótipos mostra um exemplo (par e ímpar) e por que ele precisa de protótipo.

Quando dá errado

#include <stdio.h>

int fatorial(int n) {
    if (n <= 1) {
        return 1;
    }
    n * fatorial(n - 1);
}

int main(void) {
    printf("5! = %d\n", fatorial(5));
    return 0;
}

$ gcc -std=c23 -Wall -Wextra semreturn.c -o semreturn
semreturn.c: In function ‘fatorial’:
semreturn.c:7:7: warning: value computed is not used [-Wunused-value]
    7 |     n * fatorial(n - 1);
      |     ~~^~~~~~~~~~~~~~~~~
semreturn.c:8:1: warning: control reaches end of non-void function [-Wreturn-type]
    8 | }
      | ^
$ ./semreturn
5! = 1

Referência rápida

Exercícios

Missão final: a soma dos dígitos

soma_digitos(7) = 7
soma_digitos(2026) = 10
soma_digitos(9999) = 36

#include <stdio.h>

int soma_digitos(int n) {
    // caso base: um algarismo só

    // passo recursivo: último algarismo + soma dos outros
    return 0;
}

int main(void) {
    printf("soma_digitos(7) = %d\n", soma_digitos(7));
    printf("soma_digitos(2026) = %d\n", soma_digitos(2026));
    printf("soma_digitos(9999) = %d\n", soma_digitos(9999));
    return 0;
}

#include <stdio.h>

int soma_digitos(int n) {
    if (n < 10) {
        return n;
    }
    return n % 10 + soma_digitos(n / 10);
}

int main(void) {
    printf("soma_digitos(7) = %d\n", soma_digitos(7));
    printf("soma_digitos(2026) = %d\n", soma_digitos(2026));
    printf("soma_digitos(9999) = %d\n", soma_digitos(9999));
    return 0;
}

Para soma_digitos(2026), a pilha fica com quatro chamadas: 2026, 202, 20 e 2. A última é o caso base e devolve 2; na volta, as somas vão se acumulando: 2 + 0 = 2, 2 + 2 = 4, 4 + 6 = 10.

Resumo

• Uma função recursiva chama a si mesma. Ela sempre tem um caso base (responde sem chamar de novo) e um passo recursivo (chama com um problema menor).
• Cada chamada tem as suas próprias variáveis locais. O código antes da chamada roda na ida; o código depois roda na volta, na ordem inversa.
• As chamadas pendentes ficam na pilha de chamadas, que é limitada (8 MB no Linux). Recursão sem fim estoura a pilha: Falha de segmentação, código 139. O -Wall avisa quando não há caso base (infinite recursion detected), mas não quando o caso base é pulado.
• Numa função que devolve valor, escreva return no passo recursivo: return n * fatorial(n - 1);.
• Recursão com várias chamadas por vez (Fibonacci) pode repetir trabalho e ficar lentíssima; um laço resolve.
• Se um laço simples resolve, prefira o laço. Use recursão quando o problema é "o mesmo problema, menor" e a profundidade é pequena.
• Próxima aula: Matemática (math.h).