Técnicas I: Recursividade

Introdução Teórica

Recursividade é a técnica de definir uma função ou algoritmo em termos de si mesmo. É fundamental para estratégias como Divisão e Conquista e Programação Dinâmica.

O Funcionamento Interno

Quando uma função recursiva é chamada: 1. Empilhamento: O estado atual (variáveis locais, ponto de retorno) é salvo na Pilha de Execução (Call Stack). 2. Nova Instância: Uma nova instância da função é executada com os novos parâmetros. 3. Caso Base: Toda recursão deve ter uma condição de parada (caso base) que retorna um valor sem fazer novas chamadas recursivas. Sem isso, ocorre o erro de Stack Overflow (estouro de pilha). 4. Desempilhamento: Quando o caso base é atingido, as chamadas retornam, desempilhando os estados e combinando os resultados.

Complexidade de Espaço

Um algoritmo recursivo consome memória proporcional à profundidade máxima da recursão (altura da árvore de chamadas), devido ao uso da pilha.

Problema Clássico

Problema: Fatorial Simples Link: Beecrowd 1153

Descrição: Calcular o fatorial de um número \(N\), dado por \(N! = N \times (N-1) \times \dots \times 1\).

Solução: A definição matemática já é recursiva: * Caso Base: \(0! = 1\) e \(1! = 1\). * Passo Recursivo: \(N! = N \times (N-1)!\).

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

Variações e Exercícios

  1. [Fibonacci Fácil]
    • Foco: Implementação direta da recorrência \(Fib(N) = Fib(N-1) + Fib(N-2)\). Note a ineficiência sem memorização em casos maiores.
    • Link: Beecrowd 1151
  2. [F91]
    • Foco: Uma função recursiva aninhada curiosa definida por John McCarthy. Um ótimo exercício para traçar a execução mentalmente ou com debugger.
    • Link: Beecrowd 1798 (Cortando Canos - DP, Verificar Link Correto) -> O correto para F91 geralmente é encontrado em outros problemas, mas exercitar recursão com Torre de Hanói é excelente:
    • Link Alternativo (Hanói): Beecrowd 2251 (Torres de Hanói)
  3. [Ida à Feira]
    • Foco: Recursão pode ser usada para iterar combinações ou caminhos, mas problemas simples de soma também ajudam a fixar o conceito de “passo indutivo”.
    • Link: Beecrowd 1281
Back to top