1. Introducao
A recursao soa como um ato de narcisismo programatico: a funcao olha para o espelho e chama a si mesma mais uma vez. Mas, na verdade, esta e uma tecnica muito disciplinada. Uma funcao recursiva precisa seguir um acordo: ela tem um momento em que para de chamar a si mesma, e tem uma regra de como se aproxima desse momento. Esses dois elementos sao justamente a “base” e o “passo”.
Em termos bem praticos, a recursao consiste em duas partes.
A primeira parte e o caso base (base case): uma situacao em que o problema e tao pequeno que a resposta e obvia, e nao ha necessidade de chamar a si mesmo de novo.
A segunda parte e o passo recursivo (recursive step): a regra de como transformar a tarefa atual em uma tarefa parecida, mas menor, e chamar a funcao novamente.
Esquematicamente, isso pode ser representado assim:
flowchart TD
A["Problema"] --> B{"O problema ja e simples?"}
B -->|sim| C["Resposta imediata (base)"]
B -->|nao| D["Resolver um problema “um pouco menor” com recursao (passo)"]
D --> E["Montar a resposta para o problema atual"]
2. Caso base: o ponto em que paramos de nos aprofundar
O caso base nao e um enfeite nem um “bom, vamos adicionar um if para o compilador nao reclamar”. Ele e a parte central da funcao recursiva. Ele responde a pergunta: quando paramos as autochamadas e comecamos a voltar pela pilha de chamadas. Na aula passada, voce viu que cada chamada cria um quadro na pilha; o caso base e o lugar em que novos quadros deixam de ser criados.
O exemplo mais simples e a soma dos numeros de 1 ate n.
Exemplo: soma de 1 ate n — caso base
Vamos comecar pela definicao: sum_to(n) retorna 1 + 2 + ... + n. Entao, e logico dizer:
- se n == 0, a soma e igual a 0 (isso e a base),
- caso contrario, sum_to(n) = n + sum_to(n - 1) (isso e o passo, sobre o qual falaremos logo mais).
O codigo do caso base fica assim:
int sum_to(int n) {
if (n == 0) return 0; // caso base: a soma ate 0 e 0
return n + sum_to(n - 1);
}
Observe: a resposta base 0 aqui nao e aleatoria. Esse e o chamado “elemento neutro” da adicao: se voce esta somando algo, e conveniente comecar do zero.
Exemplo: fatorial — caso base
O fatorial de n! e 1 * 2 * 3 * ... * n. E logico:
- 0! = 1 — isso e a base,
- n! = n * (n - 1)! — o passo.
long long factorial(int n) {
if (n == 0) return 1; // caso base: 0! = 1
return n * factorial(n - 1);
}
E novamente: 1 aqui nao aparece “porque esta assim no livro”. Esse e o elemento neutro da multiplicacao. Se voce esta construindo um produto, e conveniente considerar o “produto vazio” igual a 1.
A base como o “menor tijolo” do problema
Uma analogia util (e sim, ela e um pouco cotidiana, mas funciona): imagine que voce esta montando um movel seguindo o manual. O passo recursivo e “monte um modulo menor e depois aparafuse-o aqui”. O caso base e “pegue uma tabua”. Se o manual nunca disser “aqui esta a peca mais simples, nao a divida mais”, voce vai dividir o armario em metades infinitamente e nao vai apertar um unico parafuso.
Tabela: como escolher rapidamente um caso base
| Problema | O que reduzimos? | Caso base | Resposta base |
|---|---|---|---|
| Soma de 1..n | |
|
|
| Fatorial n! | |
|
|
| MDC (gcd) | |
|
|
| Percorrer uma string por indice | |
|
“nao fazemos nada” |
A ultima linha e importante: nem sempre a “resposta” e um numero. As vezes a base e apenas o momento em que a funcao para de trabalhar (por exemplo, ao imprimir caracteres).
3. Passo recursivo: tornamos o problema menor e chamamos a nos mesmos
O passo recursivo e a parte que faz a recursao ser recursao: pegamos o problema original e o reduzimos a um problema igual, mas menor. Aqui, o importante nao e tanto “chamar a si mesmo”, mas alterar os parametros de forma que avancemos em direcao ao caso base. Se os parametros nao mudam (ou mudam na direcao errada), a funcao vai chamar a si mesma infinitamente.
O passo recursivo normalmente tem dois componentes.
O primeiro componente e obter o resultado de um problema menor por meio da autochamada.
O segundo componente e “completar” o resultado para o nivel atual (por exemplo, somar n, multiplicar por n, imprimir um caractere).
Modelo de funcao recursiva
Abaixo esta um “esqueleto” util (nao e magia, apenas uma ordem de pensamento habitual):
ReturnType f(Args...) {
if (base_condition) {
return base_value; // base
}
// reduzimos o problema
auto smaller = f(modified_args); // passo: autochamada
// completamos a resposta
return combine(smaller, current_state);
}
As vezes, essa “complementacao” vem antes da chamada; as vezes, depois. Hoje, o importante e outra coisa: o passo precisa levar ao caso base.
Exemplo: soma sum_to(n) — passo
int sum_to(int n) {
if (n == 0) return 0;
return n + sum_to(n - 1); // passo: n diminui em 1
}
Aqui a reducao e obvia: antes era n, agora virou n-1. Mais cedo ou mais tarde, n vai chegar a zero, e a base sera acionada.
Exemplo: MDC (algoritmo de Euclides) — passo
O MDC (gcd) e um bom exemplo porque aqui a recursao nao e “sobre um unico numero”, mas sobre um par. Base: quando b == 0, a resposta e a. Passo: substituir (a, b) por (b, a % b).
int gcd(int a, int b) {
if (b == 0) return a; // base
return gcd(b, a % b); // passo: b diminui por meio do resto
}
Por que isso “aproxima da base”? Porque a % b em modulo e menor que b (se b != 0), o que significa que o segundo numero vai diminuindo aos poucos e, em algum momento, se tornara 0.
4. Verificacao de convergencia: vamos chegar ao caso base?
E muito facil escrever uma recursao que parece bonita, mas que, na pratica, nunca para. Por isso, antes de comemorar, vale a pena fazer algumas “perguntas de verificacao”. Elas soam meio entediantes, mas economizam horas de depuracao e algumas celulas nervosas.
Primeiro, o caso base e alcancavel para todos os dados de entrada validos? Se voce decidiu que o caso base e n == 0, mas o usuario pode passar -5, para onde voce vai diminuir? Para menos infinito? Esse nao e um plano de carreira muito produtivo.
Segundo, o problema diminui a cada passo? Se voce acidentalmente escreveu sum_to(n + 1), a base vai ficar cada vez mais distante, nao mais perto.
Terceiro, o parametro realmente muda? Um passo recursivo do tipo return f(n); e praticamente um ingresso garantido para “estouro de pilha”.
Vamos olhar para duas versoes “ruins” para aprender a reconhece-las de imediato.
Mau exemplo: o parametro nao muda
int sum_bad(int n) {
if (n == 0) return 0;
return n + sum_bad(n); // ERRO: n nao diminui
}
Esta e uma recursao infinita. A base existe, mas ninguem caminha em direcao a ela.
Mau exemplo: a base e inalcançavel
int sum_bad2(int n) {
if (n == 0) return 0;
return n + sum_bad2(n + 1); // ERRO: n cresce, a base fica cada vez mais longe
}
Mais uma vez, infinito: agora a base “foge”.
5. Por que sem o caso base o programa “falha”: a pilha nao e infinita
Quando uma funcao recursiva chama a si mesma, acontece exatamente a mesma coisa que em qualquer chamada de funcao: um novo quadro da pilha e criado. E se voce esqueceu o caso base (ou ele e inalcançavel), vai criar quadros na pilha repetidamente, ate a pilha acabar. Nesse momento, o programa normalmente encerra com falha. E aquele caso em que o computador tentou honestamente atender ao seu pedido, mas bateu na fisica: a memoria reservada para a pilha e limitada.
E importante entender uma armadilha psicologica: a recursao nao “entra em loop” como while(true). Em um loop, voce tem um quadro de pilha e executa o corpo infinitamente. Na recursao, voce cria novos quadros — muitos, muitos mesmo — e isso vai se acumulando.
Visualizacao: uma escada infinita de chamadas
Imagine a seguinte funcao sem caso base:
int boom(int n) {
return boom(n - 1); // nao ha caso base
}
A chamada boom(3) leva a esta sequencia:
boom(3) chama boom(2)
boom(2) chama boom(1)
boom(1) chama boom(0)
boom(0) chama boom(-1)
...
E assim por diante, ate a pilha estourar.
Mini-demonstracao: “recursao sem caso base”
Abaixo esta um exemplo que compila, mas esta logicamente condenado. Ele e util justamente como ilustracao:
int factorial_bad(int n) {
// nao ha caso base -> chamadas infinitas
return n * factorial_bad(n - 1);
}
Mesmo que voce chame factorial_bad(1), a funcao vai entrar em factorial_bad(0), depois em factorial_bad(-1) e continuar descendo.
6. Pratica: rastreamento e miniaplicacao
Quando voce esta aprendendo recursao, e util as vezes literalmente “encenar” as chamadas. Sim, isso parece um jogo de tabuleiro chamado “Pilha de chamadas: edicao para estudantes”, mas vale a pena. O principal e distinguir duas etapas: o que acontece antes da autochamada e o que acontece depois, quando voltamos.
Mini-rastreamento: como o caso base e o passo funcionam
Vamos pegar sum_to(3):
int sum_to(int n) {
if (n == 0) return 0;
return n + sum_to(n - 1);
}
Rastreamento:
sum_to(3) = 3 + sum_to(2)
sum_to(2) = 2 + sum_to(1)
sum_to(1) = 1 + sum_to(0)
sum_to(0) = 0 <-- base
depois vem o retorno:
sum_to(1) = 1 + 0 = 1
sum_to(2) = 2 + 1 = 3
sum_to(3) = 3 + 3 = 6
Isso e importante: embora a linha return n + sum_to(n - 1); esteja “em uma unica linha”, na pratica primeiro e preciso calcular sum_to(n - 1), e so depois somar n.
Exemplo pratico: comandos recursivos em uma aplicacao de console
Para que a recursao nao fique sendo “apenas um fatorial na prateleira”, vamos organizá-la como um pequeno conjunto de comandos em um unico aplicativo. Nao vamos complicar a entrada nem criar um “parser inteligente” de strings — um menu simples com std::cin e algumas funcoes ja basta. O sentido do exemplo e ver que uma funcao recursiva parece uma funcao comum e e chamada da mesma maneira.
Funcoes recursivas
long long factorial(int n) {
if (n == 0) return 1;
return n * factorial(n - 1);
}
int sum_to(int n) {
if (n == 0) return 0;
return n + sum_to(n - 1);
}
main: menu simples
#include <iostream>
long long factorial(int n);
int sum_to(int n);
int main() {
int cmd = 0;
std::cin >> cmd;
if (cmd == 1) {
int n; std::cin >> n;
std::cout << factorial(n) << '\n'; // por exemplo: 120
} else if (cmd == 2) {
int n; std::cin >> n;
std::cout << sum_to(n) << '\n'; // por exemplo: 55
} else {
std::cout << "Unknown command\n"; // Unknown command
}
}
Aqui ha uma ideia importante: recursao nao e um “modo especial do C++”. E apenas uma funcao que chama a si mesma.
7. Erros tipicos
Erro nº 1: “eu escrevi uma recursao, mas esqueci o caso base”.
Esta e a causa mais comum de “por que o programa falha” entre iniciantes. O codigo pode parecer logico, compilar perfeitamente, mas logo na primeira execucao entrar em chamadas infinitas e terminar com falha. A cura e simples e sem glamour: o caso base e escrito primeiro, antes mesmo de voce inventar o passo.
Erro nº 2: o caso base existe, mas e inalcançavel.
Situacao classica: a base verifica n == 0, mas o passo faz n + 1 ou nem altera n. Formalmente, a base esta presente, mas nao existe um “caminho real” ate ela. Um bom habito e se perguntar mentalmente: “em quantos passos eu certamente vou chegar ao caso base?” Se nao houver resposta, ha algo errado.
Erro nº 3: resposta base incorreta (por exemplo, factorial(0) = 0).
As vezes a base foi escrita, o passo realmente reduz o problema, a recursao termina, mas o resultado esta errado. Normalmente, isso significa que a resposta base foi escolhida incorretamente. Para soma, a base quase sempre e 0; para produto, quase sempre e 1. Se voce trocar um pelo outro, os erros serao silenciosos: o programa nao vai falhar, mas vai produzir numeros errados.
Erro nº 4: o passo recursivo nao reduz o problema “na metrica certa”.
Acontece de o parametro mudar, mas nao garantir aproximacao do caso base. Por exemplo, voce reduz n nao em 1, mas faz algo como n = n - 2, esquecendo que n pode ser impar e que a base verifica apenas n == 0. No fim, para n == 1, a recursao vai parar em numeros negativos. Nesses pontos, e importante pensar com antecedencia nos valores de entrada validos e em qual base realmente cobre todos os casos.
Erro nº 5: a chamada recursiva esta “no lugar errado”, e voce nao entende a ordem de execucao.
A linha return n + f(n - 1); parece simples, mas e calculada em duas etapas: primeiro f(n - 1), depois + n. Se voce tenta imprimir algo “no meio do caminho”, e facil confundir o momento em que std::cout sera executado. Aqui ajuda fazer um rastreamento “na mao”: anote 3 ou 4 passos de chamadas e retornos e observe onde voce realmente esta — antes da chamada ou no retorno.
GO TO FULL VERSION