naiveO(2ⁿ)
Repete chamadas para os mesmos valores e torna a árvore de execução visível.
tempo O(2ⁿ) · espaço O(n) voltar à Fase 4/ recursion · bancada 04
Recursive Fibonacci
Veja uma função chamar a si mesma para diminuir o problema.
LR / 04Fibonacci
Por que a mesma pergunta aparece tantas vezes?
Uma função recursiva resolve um caso menor até alcançar o caso-base, depois retorna os resultados pela pilha de chamadas.
instrumentação / estado atual
passo01 / 04Abrir a chamada
focofib(5)fib(5) ainda não é um caso-base; a função precisa quebrá-la.
complexidadeO(2ⁿ)caso médio
pilha1 chamadaobservado agora
/ visualização em execução
frame 01Abrir a chamada
fib(5)
↘ retorna pela pilha ↗
5
chamada ativa / resultado devolvido/ chamada abertaO problema foi reduzido a uma pergunta menor.
Passo 1 · fib(5) ainda não é um caso-base; a função precisa quebrá-la.
Passo 1: fib(5) ainda não é um caso-base; a função precisa quebrá-la.
Como ler esta réguaEla não mede o tempo do seu aparelho: compara como o trabalho tende a crescer quando n, a quantidade de elementos na estrutura, aumenta.
operações
O(2ⁿ) · Ramificação exponencial
Cada chamada recursiva pode gerar novas chamadas. Em Fibonacci ingênuo e Towers of Hanoi, o total de trabalho cresce muito mais rápido que n.
Adicionar uma unidade a n pode quase dobrar o trabalho; memoização em Fibonacci evita recomputações e reduz o tempo para O(n).comparação / duas técnicas
Compare o crescimento lado a lado
Escolha duas técnicas diferentes. As curvas usam a mesma escala visual para explicar como o custo tende a aumentar.
Comparações prontasaplique um par didático
Use este par para contrastar operações locais de extremidade com uma decomposição recursiva cujo número de movimentos cresce exponencialmente. Stacks & Queues tende a crescer mais devagar do que Towers of Hanoi quando aumentam quantidade de itens (n). Isso descreve tendência assintótica, não mede o tempo do seu aparelho.
duas leituras / mesmo problema
Menos chamadas, mais memória.
memoizedO(n)
Guarda cada resultado calculado e reutiliza o valor quando a mesma pergunta retorna.
tempo O(n) · espaço O(n)Naive Recursion ativa. Nenhum resultado é guardado: cada chamada abre novos subproblemas.
A faixa representa o crescimento teórico das chamadas nesta explicação, não uma medição de milissegundos do navegador. A animação usa os mesmos marcos pedagógicos; a diferença de chamadas aparece no código e no cache reutilizado.
/ raciocínio sincronizado
A mesma ideia, três leituras.
01
fib(n)02
se n ≤ 1: retorne n03
esquerda = fib(n - 1)04
direita = fib(n - 2)05
retorne esquerda + direitaO destaque acompanha o passo atual da variante naive variante; leia a linha destacada antes de avançar.
/ leitura técnica · recorrência e reuso
A fórmula é curta; a árvore pode ficar imensa.
Fibonacci mostra uma diferença essencial: uma definição recursiva pode estar correta e ainda repetir tanto trabalho que deixa de ser uma boa implementação. A pergunta é menos “há recursão?” e mais “um estado já foi resolvido?”.
011235
CONTRATO / ÍNDICE NÃO NEGATIVO
F(0) = 0, F(1) = 1.
Para n ≥ 2, a definição é F(n) = F(n - 1) + F(n - 2). Os dois casos-base precisam estar explícitos; cada chamada reduz o índice até um deles. Uma interface de produção também deve definir o que fazer com índices negativos e com valores que não cabem no tipo numérico escolhido.
fib(5)fib(4)fib(3)fib(3)fib(2)fib(3) reaparece: a árvore contém trabalho duplicado.
/ árvore de execução ≠ grafo de estados
O mesmo subproblema abre mais de uma vez.
Na versão direta, fib(5) pede fib(4) e fib(3); dentro de fib(4), fib(3) aparece outra vez. Essa sobreposição produz Θ(φⁿ) chamadas na leitura usual de custo unitário, embora a profundidade de uma trilha ativa seja somente O(n). Memoização não muda a matemática: ela converte a árvore repetida em um grafo de estados visitados uma vez.
Corretude vem por indução.
Os casos-base devolvem os valores definidos. Supondo corretos os retornos para k - 1 e k - 2, a soma devolve F(k). A prova estabelece o resultado, não a eficiência da estratégia usada.
Pilha e trabalho são recursos distintos.
O ramo mais longo guarda O(n) frames, mesmo quando o número total de chamadas explode. Medir apenas a profundidade da recursão não revela a recomputação dos ramos irmãos.
O número também cresce.
F(n) precisa de uma quantidade de bits proporcional a n. Em precisão arbitrária, somas e multiplicações não são necessariamente operações de custo constante; o tamanho da representação entra na análise real.
/ mesma recorrência, quatro escolhas
Reutilizar é mudar a estrutura do cálculo.
Recursão ingênua
Θ(φⁿ) chamadas · O(n) pilhaEscolha para ensinar árvore de chamadas e prova de corretude; evite para calcular termos moderados ou grandes.
Memoização
O(n) estados · O(n) tabela e pilhaPreserva a leitura top-down e calcula cada índice uma vez. Funciona bem quando estados são alcançados sob demanda.
Bottom-up
O(n) adições · O(1) estadoPara um termo isolado, dois valores consecutivos bastam. É a opção simples e robusta quando não é preciso guardar o histórico.
F(2k) = F(k) · [2F(k + 1) − F(k)]F(2k + 1) = F(k)² + F(k + 1)²FAST DOUBLING / REDUZIR O ÍNDICE PELA METADE
Ser recursivo não obriga a ser exponencial.
As identidades de duplicação rápida calculam o par F(k), F(k + 1) e reduzem o problema aproximadamente pela metade a cada nível. Isso dá O(log n) níveis de operações aritméticas. Para inteiros muito grandes, porém, essas operações incluem multiplicações de números com muitos bits; por isso, a complexidade precisa declarar o modelo de custo.
LIMITE PRÁTICO / EXATIDÃO
Fórmula fechada não substitui uma política numérica.
A fórmula de Binet ajuda a entender o crescimento e pode aproximar termos pequenos, mas ponto flutuante perde a garantia de devolver o inteiro exato conforme n aumenta. Para exatidão, use inteiros com limite conhecido ou BigInt/precisão arbitrária; para apenas um resto, faça as operações módulo m de forma consistente.
/ escolher pelo objetivo
Fibonacci é um laboratório, não um teste de velocidade isolado.
- Ensinar recursão
- Use a versão direta para tornar visíveis casos-base, ramificação, pilha e recomputação. O valor pedagógico está justamente no custo que ela expõe.
- Calcular um termo
- Use bottom-up para uma solução clara de custo linear e memória constante; use fast doubling quando o índice é muito grande e a aritmética de inteiros é apropriada.
- Generalizar para DP
- Use memoização para enxergar a transição de árvore para grafo de dependências. Em problemas maiores, o estado pode ter mais de um índice, mas o princípio de resolver e reutilizar permanece.