Técnicas I: Recursividade

Metáfora e Motivação

Imagine subir uma escada de \(N\) degraus. Você sabe como subir 1 degrau e sabe que, se conseguir subir até o degrau \(N-1\), então consegue chegar ao \(N\) apenas dando mais um passo. Essa ideia de “resolver o problema menor e então dar um passo” é a essência da recursão.

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.

Implementações em Código

C++ (Fatorial Recursivo)

long long fatorial(int n) {
    if (n <= 1) return 1; // caso base
    return n * fatorial(n - 1); // passo recursivo
}

Java (Fatorial Recursivo)

public static long fatorial(int n) {
    if (n <= 1) {
        return 1; // caso base
    }
    return n * fatorial(n - 1); // passo recursivo
}

Python (Fatorial Recursivo)

def fatorial(n: int) -> int:
    if n <= 1:
        return 1  # caso base
    return n * fatorial(n - 1)  # passo recursivo

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)!\).

Exercício Prático Guiado

Use o fatorial como exercício central:

  1. Implemente o fatorial iterativo e o recursivo em sua linguagem favorita.
  2. Desenhe (ou imprima) a árvore de chamadas da versão recursiva para um \(n\) pequeno (por exemplo, 4 ou 5).
  3. Conte quantas chamadas são feitas e compare com a solução iterativa.
  4. Discuta a complexidade de tempo e de espaço (altura da pilha) nas duas abordagens.

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