C++: Recursão

Última atualização: 2026-08-26

Recursão é uma função chamando a si mesma.

Parece estranho — como uma função pode chamar a si mesma? Não vai entrar em loop infinito?

Desde que você escreva uma "condição de saída" adequada, a recursão funciona corretamente — e pode resolver muitos problemas que são difíceis de escrever com loops.

1. O que é Recursão?

(1) 1.1 Recursão no Dia a Dia

Ideia central da recursão: Decompor um problema grande em problemas menores do mesmo tipo, até que o problema seja pequeno o suficiente para ser resolvido diretamente.

(2) 1.2 Duas Condições para Recursão

Toda função recursiva deve ter:

1. Caso Base: A condição para sair da recursão (o caso mais simples)
2. Caso Recursivo: Decompor o problema em problemas menores do mesmo tipo

2. Exemplo de Recursão: Fatorial

(1) 2.1 Definição de Fatorial

n! = n × (n-1) × (n-2) × ... × 1

Definição recursiva:

n! = n × (n-1)! （caso recursivo）
0! = 1 （caso base）

▶ Exemplo 1: Calculando Fatorial com Recursão (Dificuldade ⭐⭐)

#include <iostream>

// Função recursiva：Calcular n fatorial
long long factorial(int n) {
 // Caso base
 if (n == 0) {
 return 1;
 }
 // Caso recursivo
 return n * factorial(n - 1);
}

int main() {
 int n;
 std::cout << "Please enter a non-negative integer: ";
 std::cin >> n;
 
 std::cout << n << "! = " << factorial(n) << std::endl;
 
 return 0;
}

Saída:

Please enter a non-negative integer: 
! = 

Resultado da execução:

Please enter a non-negative integer: 5
5! = 120

(2) 2.2 Processo de Chamada Recursiva (n=5)

factorial(5)
= 5 × factorial(4)
= 5 × 4 × factorial(3)
= 5 × 4 × 3 × factorial(2)
= 5 × 4 × 3 × 2 × factorial(1)
= 5 × 4 × 3 × 2 × 1 × factorial(0)
= 5 × 4 × 3 × 2 × 1 × 1 ← caso base alcançado, começa a retornar
= 5 × 4 × 3 × 2 × 1
= 5 × 4 × 3 × 2
= 5 × 4 × 6
= 5 × 24
= 120

💡 Ponto-chave: Durante uma chamada recursiva, a função pausa na linha return n * factorial(n-1);, esperando que factorial(n-1) retorne seu resultado, depois calcula n * result.

3. Exemplo de Recursão: Sequência de Fibonacci

(1) 3.1 Definição da Sequência de Fibonacci

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) （n ≥ 2）

Sequência: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

▶ Exemplo 2: Calculando Números de Fibonacci com Recursão (Dificuldade ⭐⭐)

#include <iostream>

int fibonacci(int n) {
 // Caso base
 if (n == 0) {
 return 0;
 }
 if (n == 1) {
 return 1;
 }
 // Caso recursivo
 return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
 int n;
 std::cout << "Please enter a non-negative integer: ";
 std::cin >> n;
 
 std::cout << "F(" << n << ") = " << fibonacci(n) << std::endl;
 
 return 0;
}

Saída:

Please enter a non-negative integer: 
F() = 

Resultado da execução:

Please enter a non-negative integer: 10
F(10) = 55

💡 Dica: Esta implementação recursiva é muito ineficiente (recalcula muitos valores repetidamente). Mais tarde você aprenderá como otimizá-la com loops ou memoização.

4. Recursão vs Loops

(1) 4.1 Comparação

(2) 4.2 Reescrevendo Fatorial com um Loop

#include <iostream>

long long factorial(int n) {
 long long result = 1;
 for (int i = 1; i <= n; i++) {
 result *= i;
 }
 return result;
}

int main() {
 int n;
 std::cout << "Please enter a non-negative integer: ";
 std::cin >> n;
 
 std::cout << n << "! = " << factorial(n) << std::endl;
 
 return 0;
}

💡 Conselho: Se um problema pode ser facilmente resolvido com um loop, prefira loops. Recursão é adequada para problemas que são "naturalmente recursivos" (ex: travessia de árvores, quicksort).

5. A Armadilha da Recursão: Estouro de Pilha

(1) 5.1 O que é Estouro de Pilha?

Cada chamada de função ocupa espaço na pilha de chamadas. Se a recursão for muito profunda (ex: dezenas de milhares de níveis), a pilha de chamadas se esgota, causando um Stack Overflow.

#include <iostream>

void infiniteRecursion() {
 infiniteRecursion(); // ❌ Sem caso base, recursão infinita
}

int main() {
 infiniteRecursion();
 return 0;
}

Resultado da execução:

Segmentation fault (core dumped) // Linux

Ou

Process finished with exit code -1073741571 // Windows: estouro de pilha

(2) 5.2 Como Evitar Estouro de Pilha?

1. Garanta que existe um caso base, e que o caso base definitivamente pode ser alcançado
2. Controle a profundidade da recursão (ex: reescreva com um loop)
3. Use otimização de recursão de cauda (coberto mais tarde, mas nem todos os compiladores suportam)

6. Prática: Torre de Hanói

▶ Exemplo 3: Solução Recursiva da Torre de Hanói (Dificuldade ⭐⭐⭐)

Problema: Existem 3 pinos (A, B, C) e n discos. Inicialmente, todos os discos estão no pino A (menores em cima, maiores embaixo). Mova todos os discos para o pino C, movendo apenas um disco por vez, e nunca colocando um disco maior sobre um menor. Exiba os passos.

Abordagem recursiva:

1. Mova n-1 discos de A para B (usando C)
2. Mova o n-ésimo disco de A para C
3. Mova n-1 discos de B para C (usando A)

#include <iostream>

void hanoi(int n, char from, char to, char aux) {
 if (n == 1) { // Caso base：Apenas um disco
 std::cout << "Move disk 1 from " << from << " to " << to << std::endl;
 return;
 }
 // Caso recursivo
 hanoi(n - 1, from, aux, to); // Move n-1 discos da origem para auxiliar
 std::cout << "Move disk " << n << " from " << from << " to " << to << std::endl;
 hanoi(n - 1, aux, to, from); // Move n-1 discos do auxiliar para destino
}

int main() {
 int n;
 std::cout << "Please enter number of disks: ";
 std::cin >> n;
 
 std::cout << "========== Tower of Hanoi Steps ==========\n";
 hanoi(n, 'A', 'C', 'B');
 
 return 0;
}

Saída:

Move disk 1 from  to 
Move disk  from  to 
Please enter number of disks: 
========== Tower of Hanoi Steps ==========

Resultado da execução (n=3):

========== Tower of Hanoi Steps ==========
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

💡 Dica: A solução recursiva para a Torre de Hanói é muito elegante, mas se você tentar escrevê-la com loops, verá que é muito difícil. Esse é o poder da recursão.

7. Otimizando Recursão: Memoização

(1) 7.1 O Problema: Recursão Ingênua é Ineficiente

A função recursiva de Fibonacci anterior recalcula muitos valores:

fibonacci(5)
= fibonacci(4) + fibonacci(3)
= (fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))
= ...

fibonacci(2) é calculado 5 vezes! Quando n é grande, a eficiência é extremamente baixa.

(2) 7.2 Solução: Memoização

Armazene resultados previamente calculados e consulte-os diretamente na próxima vez.

#include <iostream>
#include <vector>

std::vector<long long> memo; // Array de memoização

long long fibonacci(int n) {
 if (n == 0) return 0;
 if (n == 1) return 1;
 
 if (memo[n] != -1) { // Se já calculado, retorna diretamente
 return memo[n];
 }
 
 memo[n] = fibonacci(n - 1) + fibonacci(n - 2); // Calcula e armazena
 return memo[n];
}

int main() {
 int n;
 std::cout << "Please enter a non-negative integer: ";
 std::cin >> n;
 
 memo.resize(n + 1, -1); // Inicializa array de memoização
 
 std::cout << "F(" << n << ") = " << fibonacci(n) << std::endl;
 
 return 0;
}

💡 Dica: C++11 introduziu std::unordered_map, que pode tornar a memoização ainda mais conveniente.

❓ Perguntas Frequentes

P: Recursão e loops podem ser convertidos entre si? R: Sim! Qualquer recursão pode ser reescrita como um loop (usando uma pilha para simular a pilha de chamadas), e qualquer loop pode ser reescrito como recursão.

Porém, alguns problemas são mais intuitivos com recursão (ex: árvores, grafos), enquanto outros são mais intuitivos com loops (ex: travessia de arrays).

P: Por que a recursão é ineficiente? R: Porque toda chamada de função tem overhead: > 1. Parâmetros devem ser empilhados > 2. O endereço de retorno deve ser empilhado > 3. Variáveis locais devem ter espaço alocado

Loops não têm esse overhead, então são mais rápidos.

P: O que é recursão de cauda? R: Recursão de cauda é uma forma especial de recursão — a chamada recursiva é a última operação na função.

CPP

📋 Copy

// Recursão de cauda
int factorialTail(int n, int acc = 1) {
if (n == 0) return acc;
return factorialTail(n - 1, n * acc); // chamada recursiva é a última linha
}

Recursão de cauda pode ser otimizada pelo compilador em um loop (economizando espaço na pilha), mas compiladores C++ não garantem essa otimização.

P: Todos os problemas podem ser resolvidos com recursão? R: Teoricamente sim (já que recursão e loops são equivalentes), mas alguns problemas são realmente mais complexos com recursão.

Problemas adequados para recursão:

• Travessia de árvores
• Busca em profundidade em grafos
• Algoritmos de divisão e conquista (ex: quicksort, merge sort)
• Algoritmos de backtracking (ex: problema das N-Rainhas)

Problemas não adequados para recursão:

• Travessia simples de arrays (loops são mais intuitivos)
• Problemas com recursão potencialmente muito profunda (propensos a estouro de pilha)

📖 Resumo

• Recursão é uma função chamando a si mesma
• Recursão deve ter duas condições: um caso base (saída) e um caso recursivo (continuação)
• A vantagem da recursão é código conciso; as desvantagens são baixa eficiência e potencial estouro de pilha
• Para problemas facilmente resolvidos com loops, prefira loops
• Recursão é adequada para problemas que são "naturalmente recursivos"

📝 Exercícios

1. Básico (Dificuldade ⭐): Escreva uma função recursiva int sumDigits(int n) que calcule a soma dos dígitos de um inteiro.

Input: 123
Output: 1 + 2 + 3 = 6

(Dica: caso recursivo sumDigits(n) = n % 10 + sumDigits(n / 10), caso base n == 0)

2. Intermediário (Dificuldade ⭐⭐): Escreva uma função recursiva int power(int base, int exp) que calcule base elevado a exp.

Input: power(2, 5)
Output: 32

(Dica: caso recursivo power(b, e) = b * power(b, e-1), caso base retorna 1 quando e == 0)

3. Desafio (Dificuldade ⭐⭐⭐): Use recursão para resolver o problema "subir escadas":
4. Suponha que você precise subir n escadas, e pode subir 1 ou 2 escadas por vez
5. Quantas maneiras diferentes existem de subir?
6. (Dica: Esta é outra versão da sequência de Fibonacci — f(n) = f(n-1) + f(n-2))
7. Otimize sua função recursiva com memoização

• Função recursiva: chama a si mesma, decompõe problemas depois combina resultados
• Três elementos da recursão: condição de término, chamada recursiva, combinação de resultados
• Recursão de Fibonacci é um exemplo clássico para iniciantes
• Recursão vs loops: recursão tem código conciso, loops têm melhor desempenho
• Recursão de cauda pode ser otimizada pelo compilador em um loop

8. 🚀 Próximo Passo

Agora que você aprendeu recursão, vamos avançar para Sobrecarga de Funções e Parâmetros Padrão (Aula 13) — técnicas para tornar funções mais flexíveis e fáceis de usar!

Equipe Técnica Web-Tutorial

Uma plataforma de tutoriais mantida por diversos desenvolvedores. Cada tutorial é escrito e revisado por profissionais da área correspondente. Trabalhamos para manter nosso conteúdo preciso e confiável — se encontrar algum problema, avise-nos.

Sobre Nós