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, e é um jeito de resolver um problema grande resolvendo uma versão menor do mesmo problema, até chegar a uma versão tão pequena que a resposta é óbvia. Nesta aula você vai escrever funções recursivas, acompanhar a "pilha" de chamadas passo a passo, contar quantas chamadas um Fibonacci ingênuo faz, ver o programa cair quando falta o ponto de parada, e decidir quando um laço é melhor.

Todos os programas desta aula foram compilados com o g++ 15 na máquina fictícia da Ana, na pasta ~/cpp, com o comando padrão do guia, g++ -std=c++23 -Wall -Wextra arquivo.cpp -o programa.

A ideia: a fila do cinema

A Ana está numa fila escura de cinema e quer saber em que posição está. Ela não consegue contar todo mundo. Então pergunta para a pessoa da frente: "qual é a sua posição?". Essa pessoa também não sabe, e pergunta para a da frente dela, e assim por diante. Até que a pergunta chega à primeira pessoa da fila, que não tem ninguém na frente e responde: "sou a 1ª". A resposta volta: a segunda diz "sou a 2ª", a terceira "sou a 3ª"… até chegar na Ana.

Repare nas duas partes do raciocínio:

Toda função recursiva tem essas duas partes. Sem o caso base, a pergunta nunca para de ser passada adiante.

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

#include <iostream>

void contagem(int n) {
    if (n == 0) {
        std::cout << "Já!\n";
        return;
    }
    std::cout << n << "...\n";
    contagem(n - 1);
}

int main() {
    contagem(3);
}

if (n == 0) { … return; }

O caso base: quando chega a zero, mostra "Já!" e para. Nenhuma nova chamada.

std::cout << n << "...\n";

O trabalho desta chamada: mostrar o número atual.

contagem(n - 1);

O passo recursivo: a função chama a si mesma com um problema menor (um número a menos). É essa diminuição que garante que um dia o caso base chega.

$ g++ -std=c++23 -Wall -Wextra contagem.cpp -o contagem
$ ./contagem
3...
2...
1...
Já!

1. contagem(3): 3 não é 0. 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): caso base. Mostra Já! e volta. Cada chamada anterior também termina, uma por uma.

Cada chamada é uma execução separada da função, com o seu próprio n (lembre da aula Escopo: parâmetros são locais). Quando contagem(1) roda, o n de contagem(3) continua guardado, valendo 3, esperando a volta.

2. Funções recursivas que devolvem valores: o fatorial

O fatorial de um número (escrito 4!) é a multiplicação dele por todos os inteiros menores até 1: 4! = 4 × 3 × 2 × 1 = 24. Ele aparece em contas de combinações: de quantas formas a Ana pode arrumar 4 produtos na vitrine? 24.

Repare que 4! = 4 × 3!, e 3! = 3 × 2!… O fatorial de um número é ele vezes o fatorial do anterior. É uma definição recursiva, e vira código quase palavra por palavra:

#include <iostream>

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

int main() {
    std::cout << "4! = " << fatorial(4) << "\n";
    std::cout << "10! = " << fatorial(10) << "\n";
    std::cout << "20! = " << fatorial(20) << "\n";
}

long long

O fatorial cresce muito rápido; long long é um inteiro grande, que aguenta até 20! (aula Inteiros). A partir de 21!, nem ele aguenta.

if (n <= 1) return 1;

Caso base: 1! = 1 (e, por definição, 0! = 1). Usar <= 1 em vez de == 1 também protege contra zero.

return n * fatorial(n - 1);

Passo recursivo: "o fatorial de n é n vezes o fatorial de n - 1". A multiplicação só acontece depois que a chamada de dentro devolver o resultado.

$ g++ -std=c++23 -Wall -Wextra fatorial.cpp -o fatorial
$ ./fatorial
4! = 24
10! = 3628800
20! = 2432902008176640000

A pilha de chamadas, passo a passo

Para ver a "ida" e a "volta", a Ana colocou mensagens dentro da função, com um recuo de dois espaços para cada nível:

#include <iostream>
#include <string>

long long fatorial(int n) {
    std::string recuo(2 * (4 - n), ' ');
    std::cout << recuo << "fatorial(" << n << ") começou\n";
    if (n <= 1) {
        std::cout << recuo << "fatorial(" << n << ") devolve 1\n";
        return 1;
    }
    long long resultado = n * fatorial(n - 1);
    std::cout << recuo << "fatorial(" << n << ") devolve " << resultado << "\n";
    return resultado;
}

int main() {
    fatorial(4);
}

$ g++ -std=c++23 -Wall -Wextra rastro.cpp -o rastro
$ ./rastro
fatorial(4) começou
  fatorial(3) começou
    fatorial(2) começou
      fatorial(1) começou
      fatorial(1) devolve 1        « caso base: a descida para aqui
    fatorial(2) devolve 2          « 2 * 1
  fatorial(3) devolve 6            « 3 * 2
fatorial(4) devolve 24             « 4 * 6

(std::string recuo(2 * (4 - n), ' ') cria um texto com vários espaços; é só enfeite para ver os níveis.) O desenho em forma de "V" mostra a pilha de chamadas: cada chamada fica empilhada esperando a de cima terminar, como pratos numa pilha. A última que entrou, fatorial(1), é a primeira que sai. Cada prato ocupa um pedaço da memória chamado pilha (em inglês, stack), e essa memória é limitada, como você vai ver na seção 4. Mais sobre a pilha em Como a Memória Funciona.

#include <iostream>

int soma(int n) {
    // caso base

    // passo recursivo
}

int main() {
    std::cout << "soma(4) = " << soma(4) << "\n";
    std::cout << "soma(100) = " << soma(100) << "\n";
}

#include <iostream>

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

int main() {
    std::cout << "soma(4) = " << soma(4) << "\n";
    std::cout << "soma(100) = " << soma(100) << "\n";
}

3. Fibonacci e o custo escondido

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 com duas chamadas: fib(n) = fib(n - 1) + fib(n - 2). A versão em C++ é curta e bonita. Para ver o preço dessa beleza, a Ana passou um contador de chamadas por referência (aula Por Valor × Por Referência):

#include <iostream>

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

int main() {
    for (int n : {5, 10, 20, 30, 35}) {
        long long chamadas = 0;
        long long resultado = fib(n, chamadas);
        std::cout << "fib(" << n << ") = " << resultado
                  << "  (" << chamadas << " chamadas)\n";
    }
}

$ g++ -std=c++23 -Wall -Wextra fib.cpp -o fib
$ ./fib
fib(5) = 5  (15 chamadas)
fib(10) = 55  (177 chamadas)
fib(20) = 6765  (21891 chamadas)
fib(30) = 832040  (2692537 chamadas)
fib(35) = 9227465  (29860703 chamadas)

Para calcular o 35º número, foram quase 30 milhões de chamadas. E a cada 5 a mais no n, o número de chamadas fica mais de 10 vezes maior. Por quê? Porque a função recalcula as mesmas coisas o tempo todo:

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2) ...
│   │   └── fib(1)
│   └── fib(2) ...          « fib(2) de novo
└── fib(3)                  « fib(3) inteiro de novo!
    ├── fib(2) ...
    └── fib(1)

Cada chamada se divide em duas, que se dividem em duas… Esse crescimento se chama exponencial. No relógio, com dois programas que só calculam e mostram fib(35) e fib(40) (a mesma função, sem o contador):

$ time ./fib35
9227465

real	0m0,112s
user	0m0,109s
sys	0m0,003s
$ time ./fib40          « só 5 a mais
102334155

real	0m1,240s           « mais de 10 vezes mais lento
user	0m1,239s
sys	0m0,001s

Pelo mesmo ritmo, fib(50) levaria mais de dois minutos, e fib(60), horas. (Os tempos mudam de máquina para máquina; a proporção, não.) Agora a versão com um laço, que guarda só os dois últimos números e anda para a frente:

#include <iostream>

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() {
    for (int n : {5, 10, 20, 30, 35, 90}) {
        std::cout << "fib(" << n << ") = " << fib(n) << "\n";
    }
}

$ time ./fiblaco
fib(5) = 5
fib(10) = 55
fib(20) = 6765
fib(30) = 832040
fib(35) = 9227465
fib(90) = 2880067194370816120

real	0m0,002s                « inclusive o fib(90)
user	0m0,001s
sys	0m0,001s

Para fib(90), o laço faz 89 voltas. A recursão simples faria mais chamadas do que um computador consegue em milhares de anos. A lição não é "recursão é lenta": é que recursão com duas chamadas que repetem o mesmo trabalho explode. (Existe uma técnica para manter a recursão e guardar os resultados já calculados, a memoização; ela usa um std::map ou um vetor como "caderninho".)

4. Sem caso base: a pilha estoura

O que acontece se a Ana esquecer o caso base do fatorial?

#include <iostream>

long long fatorial(int n) {
    return n * fatorial(n - 1);
}

int main() {
    std::cout << fatorial(4) << "\n";
}

$ g++ -std=c++23 -Wall -Wextra semfim.cpp -o semfim
semfim.cpp: In function ‘long long int fatorial(int)’:
semfim.cpp:3:11: warning: infinite recursion detected [-Winfinite-recursion]
    3 | long long fatorial(int n) {
      |           ^~~~~~~~
semfim.cpp:4:24: note: recursive call
    4 |     return n * fatorial(n - 1);
      |                ~~~~~~~~^~~~~~~
$ ./semfim
Falha de segmentação     (imagem do núcleo gravada) ./semfim
$ echo $?
139

warning: infinite recursion detected

"Recursão infinita detectada". O g++ percebeu que não há nenhum caminho pela função que não chame a si mesma. O aviso -Winfinite-recursion vem com o -Wall. No editor do guia, o Clang diz all paths through this function will call itself ("todos os caminhos desta função chamam a si mesma").

note: recursive call

"Chamada recursiva": aponta a linha da chamada.

Falha de segmentação

O programa caiu. fatorial(4) chamou fatorial(3), 2, 1, 0, -1, -2… e cada chamada empilhou mais um prato na pilha, até a memória da pilha acabar. Isso se chama estouro de pilha (em inglês, stack overflow, que deu nome ao famoso site de perguntas). O sistema mata o programa ao ver um acesso fora da área permitida. Em inglês: Segmentation fault (core dumped).

139

O código de saída: 128 + 11, o sinal 11 (SIGSEGV, violação de segmentação).

Quão funda é a pilha?

Para ver quantas chamadas cabem, a Ana fez uma função que desce sem parar e avisa a cada 20 mil níveis:

#include <iostream>

void descer(int nivel) {
    if (nivel % 20000 == 0) {
        std::cout << "nível " << nivel << "\n";
    }
    descer(nivel + 1);
}

int main() {
    descer(1);
}

$ ulimit -s
8192                     « o tamanho da pilha: 8192 KB = 8 MB (o padrão no Linux)
$ ./profundidade
nível 20000
nível 40000
nível 60000
nível 80000
nível 100000
nível 120000
nível 140000
nível 160000
nível 180000
nível 200000
nível 220000
nível 240000
nível 260000
Falha de segmentação     (imagem do núcleo gravada) ./profundidade
$ echo $?
139
$ ulimit -s 1024         « diminui a pilha deste terminal para 1 MB
$ ./profundidade
nível 20000
Falha de segmentação     (imagem do núcleo gravada) ./profundidade
$ echo $?
139

Com a pilha padrão de 8 MB, coube um pouco mais de 260 mil chamadas desta função pequena; com 1 MB, um pouco mais de 20 mil. ulimit -s é um comando do terminal que mostra ou muda o tamanho máximo da pilha dos programas abertos nele (só naquele terminal, até fechá-lo). Funções com mais variáveis locais ocupam pratos maiores, e cabem menos. No Windows, a pilha padrão costuma ser de só 1 MB.

O caso base que nunca chega

Ter um caso base não basta: o passo recursivo precisa chegar nele. Nesta versão da contagem, a Ana pulou de 2 em 2:

#include <iostream>

void contagem(int n) {
    if (n == 0) {
        std::cout << "Já!\n";
        return;
    }
    std::cout << n << "...\n";
    contagem(n - 2);
}

int main() {
    contagem(3);
}

$ g++ -std=c++23 -Wall -Wextra basecerta.cpp -o basecerta      « nenhum aviso desta vez
$ ./basecerta
3...
1...
-1...                    « passou direto pelo zero
-3...
-5...
-7...                    « … e assim por mais de 260 mil linhas …
Falha de segmentação     (imagem do núcleo gravada) ./basecerta
$ echo $?
139

Desta vez o g++ não avisou nada: existe um caminho que para (n == 0), só que, começando do 3 e descendo de 2 em 2, ele nunca é alcançado. A correção é um caso base que pegue todos os finais possíveis: if (n <= 0).

5. Recursão × laço

Todo problema que se resolve com recursão também se resolve com um laço (às vezes com mais trabalho), e vice-versa. O fatorial com for:

#include <iostream>

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

int main() {
    std::cout << "4! = " << fatorial(4) << "\n";
    std::cout << "20! = " << fatorial(20) << "\n";
}

$ g++ -std=c++23 -Wall -Wextra fatlaco.cpp -o fatlaco
$ ./fatlaco
4! = 24
20! = 2432902008176640000

Regra prática para quem está começando: se um laço simples resolve, use o laço. Guarde a recursão para quando o problema tiver a forma de "algo que contém versões menores de si mesmo", em que o laço ficaria complicado. E sempre que escrever uma função recursiva, faça duas perguntas: qual é o caso base? e cada chamada chega mais perto dele?

Quando dá errado

Referência rápida

Exercícios

Missão final: potência recursiva

2^10 = 1024
3^4 = 81
5^0 = 1

#include <iostream>

long long potencia(long long base, int exp) {
    // caso base e passo recursivo aqui
}

int main() {
    std::cout << "2^10 = " << potencia(2, 10) << "\n";
    std::cout << "3^4 = " << potencia(3, 4) << "\n";
    std::cout << "5^0 = " << potencia(5, 0) << "\n";
}

#include <iostream>

long long potencia(long long base, int exp) {
    if (exp == 0) {
        return 1;
    }
    return base * potencia(base, exp - 1);
}

int main() {
    std::cout << "2^10 = " << potencia(2, 10) << "\n";
    std::cout << "3^4 = " << potencia(3, 4) << "\n";
    std::cout << "5^0 = " << potencia(5, 0) << "\n";
}

Resumo

• Recursão: uma função que chama a si mesma com um problema menor.
• Toda função recursiva precisa de um caso base (resolve sem nova chamada) e de um passo recursivo que chegue mais perto dele a cada chamada.
• As chamadas se empilham na pilha e voltam na ordem inversa: a última a entrar é a primeira a sair.
• Duas chamadas que repetem trabalho (Fibonacci) crescem de forma exponencial: fib(35) fez quase 30 milhões de chamadas; o laço resolve fib(90) na hora.
• Sem caso base (ou com um que nunca chega): estouro de pilha, Falha de segmentação, código 139. O -Wall avisa os casos óbvios com -Winfinite-recursion.
• Se um laço simples resolve, use o laço. Recursão brilha em estruturas que contêm versões menores de si mesmas.
• Próxima aula: Lambdas, funções sem nome escritas no meio do código.