Recursividade
Recursividade em Algoritmos e Estrutura de Dados
Recursividade é uma técnica em que uma função chama a si mesma para resolver um problema dividindo-o em subproblemas menores. É amplamente utilizada em algoritmos como busca, ordenação e manipulação de estruturas de dados.
Conceitos Fundamentais
Definição: Uma função recursiva possui:
- Caso base: Condição de parada para evitar loops infinitos.
- Passo recursivo: Chamada da própria função com um subproblema menor.
Exemplo Clássico: Fatorial
int fatorial(int n) {
if (n == 0) // Caso base
return 1;
else
return n * fatorial(n - 1); // Passo recursivo
}
Vantagens e Desvantagens
Vantagens:
- Código mais legível e conciso para problemas com natureza recursiva.
- Facilita a resolução de problemas complexos (ex: Torres de Hanói).
Desvantagens:
- Alto consumo de memória (pilha de chamadas).
- Risco de estouro de pilha (stack overflow) se não houver caso base adequado.
Aplicações em Concursos
É comum em provas cobrarem:
- Identificação de casos base e passos recursivos.
- Cálculo de complexidade (ex: recursão linear vs. múltiplas chamadas).
- Conversão entre soluções recursivas e iterativas.
Dica para Provas
Em questões práticas, sempre verifique se a recursão possui:
- Condição de parada clara.
- Redução progressiva do problema em cada chamada.