Recursividade em Algoritmos: caso-base, chamada recursiva e pilha de execução
Recursividade é uma técnica de construção de algoritmos em que uma função resolve um problema chamando a si mesma, direta ou indiretamente, sobre uma versão menor ou mais simples do problema original. Em termos didáticos, uma função recursiva transforma um problema maior em subproblemas da mesma natureza até alcançar uma situação simples, previamente conhecida, chamada caso-base.
Cormen et al. (2022) explicam a recursão como uma estratégia em que o algoritmo chama a si mesmo uma ou mais vezes para resolver subproblemas fortemente relacionados ao problema inicial. Essa ideia, descrita na Figura 1, aproxima a programação de raciocínios matemáticos baseados em definição indutiva, como fatorial, potências, árvores, recorrências e estruturas hierárquicas.
Fonte: Autoria própria.
A importância da recursividade em programação aparece em três dimensões principais: lógica, teórica e prática. A primeira (lógica) envolve simplificar alguns problemas para ficarem mais claros quando escritos de forma recursiva, especialmente aqueles naturalmente compostos por partes semelhantes ao todo. A segunda é mais teórica, pois a recursividade ajuda o estudante a compreender indução matemática, prova de correção e análise de recorrências, que são temas centrais em algoritmos (Cormen et al., 2022). Por fim, a terceira é prática, já que muitas estruturas de dados, como árvores, grafos, diretórios de arquivos e expressões sintáticas, são frequentemente percorridas por algoritmos recursivos (Sedgewick; Wayne, 2011).
Em uma linguagem como C++, a recursividade é implementada por meio de chamadas de função. Cada chamada cria um novo contexto de execução com seus próprios parâmetros, variáveis locais e ponto de retorno. Esse mecanismo torna a recursividade poderosa, mas também exige cuidado, pois uma função sem condição de parada adequada pode consumir a pilha de execução até causar erro de execução, situação conhecida como estouro de pilha ou stack overflow. Por isso, estudar recursividade significa compreender tanto a lógica do algoritmo quanto o comportamento da memória durante a execução.
Conceitos fundamentais
Função recursiva
Uma função recursiva é uma função que participa de sua própria definição operacional. Em vez de resolver tudo em um único bloco de comandos, ela identifica uma parte simples do problema e delega o restante para uma nova chamada da mesma função. Segundo Knuth (1997), a recursão é uma das técnicas fundamentais da ciência da computação porque permite descrever processos computacionais complexos a partir de definições menores, estruturadas e repetíveis.
O exemplo matemático mais conhecido é o fatorial. Para um número natural n, define-se que 0! = 1 e que n! = n × (n - 1)! para n > 0. Essa definição contém exatamente os dois elementos essenciais da recursividade: uma condição de parada e uma regra de redução do problema. A função não calcula n! diretamente; ela calcula n × fatorial(n - 1), até que n chegue a zero.
Observe o código abaixo:
#include <iostream>
using namespace std;
long long calcularFatorial(int numero) {
if (numero == 0) {
return 1; // caso-base
}
return numero * calcularFatorial(numero - 1); // caso recursivo
}
int main() {
int numero = 5;
cout << "Fatorial de " << numero << " = " << calcularFatorial(numero) << endl;
return 0;
}Nesse código, calcularFatorial(5) depende de calcularFatorial(4), que depende de calcularFatorial(3), e assim sucessivamente. A cadeia termina quando a função recebe 0, retornando 1. Depois disso, as chamadas pendentes começam a ser resolvidas no caminho de volta: ( 1 ), (2 × 1), (3 × 2), (4 × 6) e (5 × 24).
Caso-base
O caso-base é a situação em que a função consegue responder sem fazer nova chamada recursiva (condição de parada). Ele impede que o algoritmo continue se chamando indefinidamente. Em termos de correção, o caso-base funciona como o ponto inicial de uma definição indutiva: se o algoritmo sabe resolver o menor caso possível, e se cada passo recursivo aproxima o problema desse caso, então a solução tende a ser bem definida.
Para Cormen et al. (2022), algoritmos recursivos devem ser analisados considerando a decomposição em subproblemas e a combinação das soluções obtidas. Sem um caso-base, essa decomposição nunca termina. No fatorial, o caso-base é numero == 0. Em uma busca recursiva em array, pode ser o índice ultrapassar o fim da estrutura. Em uma árvore binária, pode ser encontrar um ponteiro nulo. O caso-base varia conforme o domínio do problema.
Um erro comum entre iniciantes é escrever a chamada recursiva antes de garantir que há uma condição de parada alcançável. O problema não é esquecer o de escrever o comando if, mas criar uma chamada que não reduz o problema. Uma função como calcularFatorial(numero) chamando novamente calcularFatorial(numero) não se aproxima de lugar algum. Portanto, lembre-se que o algoritmo precisa “caminhar” para o caso-base.
Caso recursivo
O caso recursivo é a parte da função que reduz o problema original a um subproblema menor (passo indutivo). Ele também é chamado de passo indutivo porque se assemelha ao raciocínio da indução matemática, onde assume-se que a solução funciona para uma instância menor e usa-se essa solução para resolver a instância atual.
No fatorial, o passo indutivo é dado por numero * calcularFatorial(numero - 1). Na sequência de Fibonacci, o passo é fibonacci(n - 1) + fibonacci(n - 2). Na soma dos elementos de um array, o passo pode ser vetor[indice] + somar(vetor, indice + 1, tamanho). Em todos esses casos, a função resolve uma parte do problema e transfere o restante para uma chamada menor ou mais avançada.
A relação entre caso-base e caso recursivo define a qualidade do algoritmo. Um bom algoritmo recursivo possui uma condição de parada simples, uma redução clara do problema e uma garantia de progresso. Sedgewick e Wayne (2011) chamam atenção para o fato de que programas recursivos devem sempre incluir uma condição de parada e chamadas que convergem para essa condição.
Pilha de execução (call stack)
Como a memória funciona durante chamadas recursivas
Quando uma função é chamada em C++, o programa cria um registro de ativação na pilha de execução. Esse registro guarda informações necessárias para a função executar e depois retornar, tais como parâmetros, variáveis locais, endereço de retorno e outros dados de controle. Em uma chamada comum, esse registro é removido quando a função termina. Em uma chamada recursiva, vários registros da mesma função podem coexistir, cada um com valores próprios.
Tanenbaum e Bos (2015) explicam que sistemas operacionais organizam a execução de programas por meio de espaços de endereçamento, pilhas e áreas de memória associadas aos processos. Na prática do programador, isso significa que a chamada de função não é apenas uma abstração lógica sem consequências, pois ela tem custo de memória e tempo. Ou seja, cada chamada recursiva ocupa espaço na pilha.
A Figura 2 apresenta uma explicação visual da operação recursiva em linguagem C++ a partir da perspectiva da memória principal (conhecida vulgarmente como RAM).
Fonte: Autoria própria.
Considere o problema de calcularFatorial(4). Antes de chegar ao caso-base, a pilha terá chamadas pendentes para 4, 3, 2, 1 e 0. Quando 0 retorna 1, a pilha começa a ser desempilhada, conforme visto na Figura 2. Cada chamada retoma do ponto em que parou e conclui seu cálculo. Esse processo explica por que a recursividade é elegante, mas também pode ser perigosa quando a profundidade de chamadas cresce demais.
calcularFatorial(4)
calcularFatorial(3)
calcularFatorial(2)
calcularFatorial(1)
calcularFatorial(0) -> retorna 1
retorna 1 * 1
retorna 2 * 1
retorna 3 * 2
retorna 4 * 6Estouro de pilha (stack overflow)
O estouro de pilha ocorre quando o programa tenta empilhar mais chamadas do que a memória reservada para a pilha permite. Em recursividade, isso geralmente acontece por dois motivos: 1) ausência de caso-base ou 2) profundidade recursiva grande demais. A ausência de caso-base é um erro lógico, enquanto a profundidade grande demais pode ocorrer mesmo em algoritmos logicamente corretos, pois o tamanho da entrada é muito elevado.
Observe e digite em seu computador o código em C++ a seguir:
#include <iostream>
using namespace std;
void contarSemParar(int numero) {
cout << numero << endl;
contarSemParar(numero + 1); // não há caso-base
}
int main() {
contarSemParar(1);
return 0;
}Esse código tende a falhar porque a função nunca para de chamar a si mesma e cada chamada consome mais espaço na pilha. Em algum momento, o programa excede o limite disponível. Em C++, esse comportamento pode resultar em encerramento abrupto, falha de segmentação ou outro erro dependente do ambiente de execução.
A prevenção exige três cuidados: 1) definir um caso-base correto; 2) garantir que cada chamada se aproxime dele e; 3) avaliar se a profundidade máxima é aceitável. Em alguns problemas, uma solução iterativa com for ou while é mais segura. Em outros, como percursos em árvores, a recursividade permanece natural, desde que a altura da estrutura seja controlada.
Tipos de recursividade
Recursividade direta
A recursividade direta ocorre quando uma função chama a si mesma explicitamente. É a forma mais comum e a mais simples de identificar. O fatorial é um exemplo direto, pois a função calcularFatorial chama calcularFatorial.
No exemplo abaixo, nosso código tem como objetivo contar regressivamente os números inteiros de 5 até 1. Poderíamos fazer isso com um simples laço de repetição? Sim! Este é um exemplo extremamente básico e poderia ser abordado de forma mais simples. Contudo, como estamos dizendo há alguns parágrafos, existem cenários em que precisaremos de mais “poder de fogo” para simplificar o entendimento da lógica e clarear a separação das responsabilidades nos algoritmos. Portanto, estamos aplicando recursividade aqui para treinamento de casos simples.
#include <iostream>
using namespace std;
int contarRegressivamente(int numero) {
if (numero == 0) {
return 0;
}
cout << numero << " ";
return contarRegressivamente(numero - 1);
}
int main() {
contarRegressivamente(5);
return 0;
}Como dito antes, esse exemplo imprime os números de 5 até 1. A função contarRegressivamente reduz o valor da variável numero a cada nova chamada, fazendo-o convergir para 0, que é a condição de parada dentro do if.
Recursividade indireta
A recursividade indireta ocorre quando uma função chama outra função, que em algum momento chama a primeira. O ciclo recursivo envolve duas ou mais funções. Esse padrão aparece em analisadores sintáticos, máquinas de estado, validações alternadas e decomposição de problemas em subfunções complementares.
Vejamos um exemplo mais simples do conceito. Considere um programa para descobrir se um dado número é par ou ímpar. Uma possível implementação para este problema pode ser:
#include <iostream>
using namespace std;
// assinaturas (ou protótipos) das funções/procedimentos
bool ehPar(int numero);
bool ehImpar(int numero);
bool ehPar(int numero) {
if (numero == 0) {
return true;
}
return ehImpar(numero - 1);
}
bool ehImpar(int numero) {
if (numero == 0) {
return false;
}
return ehPar(numero - 1);
}
int main() {
int numero = 7;
if (ehImpar(numero)) {
cout << numero << " é ímpar" << endl;
} else {
cout << numero << " é par" << endl;
}
return 0;
}Nesse caso, ehPar e ehImpar dependem uma da outra. O caso-base permanece essencial e igual em ambas (numero == 0). Sem ele, a alternância entre as funções continuaria até esgotar a pilha.
Recursividade em cauda (tail recursion)
A recursividade em cauda ocorre quando a chamada recursiva é a última operação executada pela função. Não há cálculo pendente depois que a chamada retorna. Esse formato é importante porque alguns compiladores e linguagens conseguem otimizar chamadas em cauda, reaproveitando o registro de ativação em vez de criar novos registros. Essa técnica é conhecida como otimização de chamada em cauda.
C++ não garante, pela especificação da linguagem, que toda recursão em cauda será otimizada. Alguns compiladores podem aplicar a otimização em determinados níveis de otimização, mas o programador não deve depender dela para evitar estouro de pilha em código portátil. Ainda assim, conhecer esse padrão ajuda a escrever funções recursivas mais próximas de uma forma iterativa.
Voltemos ao exemplo do fatorial. Observe e digite a versão alternativa abaixo:
#include <iostream>
using namespace std;
long long calcularFatorialCauda(int numero, long long acumulador) {
if (numero == 0) {
return acumulador;
}
return calcularFatorialCauda(numero - 1, numero * acumulador);
}
int main() {
int numero = 5;
cout << "Fatorial de " << numero << " = " << calcularFatorialCauda(numero, 1) << endl;
return 0;
}Nessa versão alternativa, o resultado parcial é mantido no parâmetro acumulador. Quando numero chega a zero, o acumulador já contém a resposta que buscamos encontrar. Dessa forma, diferentemente da versão clássica do fatorial, não há multiplicação pendente após o retorno da chamada recursiva.
Exemplos clássicos de prática
Vamos demonstrar alguns problemas clássicos na literatura para reforçar os conceitos discutidos até aqui. Leia atentamente cada algoritmo, digite-o e execute-o para ver seus resultados.
Fatorial
O fatorial é um bom primeiro exemplo porque possui uma estrutura matemática simples. Ele reforça a ideia de decrescimento: a cada chamada, o valor de numero diminui até chegar a zero.
#include <iostream>
using namespace std;
long long calcularFatorial(int numero) {
if (numero < 0) {
return -1; // valor usado para indicar entrada inválida neste exemplo didático
}
if (numero == 0) {
return 1;
}
return numero * calcularFatorial(numero - 1);
}
int main() {
int numero;
cout << "Digite um número inteiro não negativo: ";
cin >> numero;
long long resultado = calcularFatorial(numero);
if (resultado == -1) {
cout << "Entrada inválida." << endl;
} else {
cout << numero << "! = " << resultado << endl;
}
return 0;
}O programa acima é útil para cenários introdutórios, mas possui limites. Por exemplo, o tipo long long não comporta fatoriais muito grandes. Além disso, valores elevados aumentam a profundidade da recursão.
Sequência de Fibonacci
A sequência de Fibonacci é definida por F(0) = 0, F(1) = 1 e F(n) = F(n - 1) + F(n - 2) para n >= 2. Ela é didaticamente importante porque mostra uma recursividade com duas chamadas. Entretanto, a implementação ingênua recalcula muitas vezes os mesmos valores.
O código demonstrado na sequência expressa diretamente em forma de algoritmo a definição matemática do Fibonacci. Contudo, destacamos que ele não é eficiente para grandes entradas de dados.
#include <iostream>
using namespace std;
long long calcularFibonacci(int posicao) {
if (posicao == 0) {
return 0;
}
if (posicao == 1) {
return 1;
}
return calcularFibonacci(posicao - 1) + calcularFibonacci(posicao - 2);
}
int main() {
int posicao = 10;
cout << "Fibonacci(" << posicao << ") = " << calcularFibonacci(posicao) << endl;
return 0;
}Cormen et al. (2022) destacam que a análise de algoritmos deve considerar o crescimento do tempo de execução em função do tamanho da entrada. No Fibonacci recursivo ingênuo, há muitas chamadas repetidas, o que torna o algoritmo exponencial. Para produção, seria melhor usar programação dinâmica, memoização (técnica de otimização em programação que guarda o resultado de uma função no cache) ou uma solução iterativa.
Soma de dígitos
A soma de dígitos mostra como a recursividade pode decompor números inteiros. A cada chamada, separa-se o último dígito com % 10 e reduz-se o número com / 10.
O algoritmo que escrevemos recebe o valor 4729 e chama a função somarDigitos, passando a variável número como parâmetro inicial. A função somarDigitos faz duas verificações e, caso passe direto por elas, dá um return com a operação de soma do dígito separado com a chamada recursiva.
#include <iostream>
using namespace std;
int somarDigitos(int numero) {
if (numero < 0) {
numero = -numero;
}
if (numero < 10) {
return numero;
}
return (numero % 10) + somarDigitos(numero / 10);
}
int main() {
int numero = 4729;
cout << "Soma dos dígitos de " << numero << " = " << somarDigitos(numero) << endl;
return 0;
}Em outras palavras, para o valor 4729, o algoritmo calcula 9 + somarDigitos(472), depois 2 + somarDigitos(47), depois 7 + somarDigitos(4). O caso-base neste exemplo é alcançado quando o número possui apenas um dígito (numero < 10).
Soma de elementos de um array
Arrays também podem ser percorridos recursivamente. Em vez de usar um laço for, a função recebe um índice e soma o elemento atual com a soma do restante do array. O caso-base ocorre quando indice == tamanho, indicando que todos os elementos já foram processados.
#include <iostream>
using namespace std;
int somarArray(const int valores[], int indice, int tamanho) {
if (indice == tamanho) {
return 0;
}
return valores[indice] + somarArray(valores, indice + 1, tamanho);
}
int main() {
int notas[] = {80, 75, 90, 65, 100};
int tamanho = 5;
int soma = somarArray(notas, 0, tamanho);
cout << "Soma dos valores = " << soma << endl;
return 0;
}Esse exemplo mostra que a recursividade não serve apenas para manipular fórmulas matemáticas. Ela também pode percorrer estruturas lineares. É importante que um(a) desenvolver(a) mantenha essa ideia em mente.
Busca recursiva em array
A busca linear recursiva é outra possibilidade onde pode-se aplicar recursividade. Nesse caso, o algoritmo deve verificar um elemento por vez. Se o valor procurado está no índice atual, o algoritmo deve retornar esse índice. Caso contrário, chama a si mesmo para verificar o próximo índice.
#include <iostream>
using namespace std;
int buscarValor(const int valores[], int indice, int tamanho, int procurado) {
if (indice == tamanho) {
return -1;
}
if (valores[indice] == procurado) {
return indice;
}
return buscarValor(valores, indice + 1, tamanho, procurado);
}
int main() {
int codigos[] = {101, 203, 305, 407, 509};
int tamanho = 5;
int procurado = 407;
int posicao = buscarValor(codigos, 0, tamanho, procurado);
if (posicao == -1) {
cout << "Valor não encontrado." << endl;
} else {
cout << "Valor encontrado no índice " << posicao << endl;
}
return 0;
}Esse algoritmo ilustra a estrutura geral de muitos percursos recursivos. Basicamente, o algoritmo recursivo deve verificar se ele chegou ao fim (caso-base), processar o elemento atual e delegar o restante da tarefa para a próxima chamada.
Exemplo real de recursividade
Um cenário real e simples onde pode-se aplicar recursividade é o cálculo do tamanho total de uma pasta de arquivos em um sistema.
Imagine um analista de sistemas trabalhando em um módulo de armazenamento de documentos. Uma empresa possui pastas como “Contratos”, “Notas Fiscais”, “Projetos” e, dentro delas, outras subpastas. Para mostrar ao usuário quanto espaço uma pasta ocupa, o sistema precisa somar os arquivos da pasta principal e também os arquivos de todas as subpastas.
Esse problema é naturalmente recursivo porque uma pasta pode conter arquivos e outras pastas. Cada subpasta tem exatamente a mesma estrutura da pasta principal: pode conter arquivos e novas subpastas. Assim, a função “calcular tamanho da pasta” precisa chamar a si mesma para calcular o tamanho das subpastas.
Uma versão simples para resolver o exemplo em C++17 pode ser:
#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Arquivo {
string nome;
int tamanhoEmKB;
};
struct Pasta {
string nome;
vector<Arquivo> arquivos;
vector<Pasta> subpastas;
};
int calcularTamanhoDaPasta(const Pasta& pasta) {
int total = 0;
// Soma os arquivos da pasta atual
for (const Arquivo& arquivo : pasta.arquivos) {
total += arquivo.tamanhoEmKB;
}
// Soma o tamanho das subpastas
for (const Pasta& subpasta : pasta.subpastas) {
total += calcularTamanhoDaPasta(subpasta);
}
return total;
}
int main() {
Pasta contratos {
"Contratos",
{
{"contrato_cliente_a.pdf", 120},
{"contrato_cliente_b.pdf", 180}
},
{}
};
Pasta notasFiscais {
"Notas Fiscais",
{
{"nota_001.pdf", 90},
{"nota_002.pdf", 110}
},
{}
};
Pasta documentos {
"Documentos",
{
{"manual_interno.pdf", 300}
},
{
contratos,
notasFiscais
}
};
int tamanhoTotal = calcularTamanhoDaPasta(documentos);
cout << "Tamanho total da pasta "
<< documentos.nome
<< ": "
<< tamanhoTotal
<< " KB"
<< endl;
return 0;
}Nesse exemplo, a pasta Documentos tem um arquivo próprio e duas subpastas: Contratos e Notas Fiscais. Portanto, a função calcularTamanhoDaPasta primeiro soma os arquivos da pasta atual e depois, para cada subpasta, chama novamente calcularTamanhoDaPasta.
A recursividade é importante aqui porque o(a) programador(a) não precisa saber previamente quantos níveis de subpastas existem. Pode haver uma pasta dentro de outra pasta, dentro de outra pasta, e o mesmo código continua funcionando. Esse é um tipo de problema comum em sistemas de arquivos, menus hierárquicos, organogramas, categorias de produtos, comentários com respostas e estruturas de permissões.
Recursividade, iteração e escolha técnica
Recursividade e iteração são formas diferentes de expressar repetição. A iteração usa comandos como for, while e do while, enquanto a recursividade usa chamadas de função. Muitos algoritmos recursivos podem ser reescritos de forma iterativa, e muitos algoritmos iterativos podem ser reformulados recursivamente.
A escolha técnica depende do problema. Para percorrer arrays simples, a iteração costuma ser mais direta e econômica. Para árvores, divisões sucessivas, busca em profundidade, ordenação por divisão e conquista e processamento de estruturas aninhadas, a recursividade tende a expressar melhor a natureza do problema. Cormen et al. (2022) usam extensivamente a recursão em algoritmos de divisão e conquista, como merge sort e quicksort, justamente porque esses algoritmos quebram o problema em subproblemas semelhantes.
A escolha técnica sobre qual ferramenta utilizar deve avaliar legibilidade, custo de memória, profundidade máxima e desempenho. Um algoritmo recursivo curto e elegante pode ser inadequado se gerar chamadas demais. Por outro lado, um algoritmo iterativo pode ser mais eficiente, mas menos aderente à estrutura conceitual do problema. Então, a competência profissional está em escolher a representação mais clara e segura para cada caso.
Conclusão
Recursividade é uma técnica central para a formação em algoritmos porque conecta programação, matemática discreta, estruturas de dados e análise de complexidade. Uma função recursiva bem construída possui caso-base, caso recursivo e progresso garantido em direção à condição de parada. Esses três elementos formam a base para compreender por que o algoritmo termina e como ele constrói sua resposta.
O estudo da pilha de execução mostra que a recursividade não deve ser tratada como uma ideia abstrata, já que cada chamada consome memória, cria um novo contexto e precisa retornar corretamente. Por isso, erros de recursividade podem produzir estouro de pilha, consumo excessivo de memória ou tempo de execução elevado. Conhecer esses limites ajuda o programador a escrever soluções mais robustas.
Obrigado pela leitura e bons estudos!
Referências
CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford. Introduction to algorithms. 4th ed. Cambridge: MIT Press, 2022.
KNUTH, Donald E. The art of computer programming: fundamental algorithms. 3rd ed. Boston: Addison-Wesley, 1997. v. 1.
SEDGEWICK, Robert; WAYNE, Kevin. Algorithms. 4th ed. Boston: Addison-Wesley, 2011.
TANENBAUM, Andrew S.; BOS, Herbert. Modern operating systems. 4th ed. Boston: Pearson, 2015.
