Fibonacci recursivo

Veja uma função chamar a si mesma para diminuir o problema.

LR / 04Fibonacci

pergunta de entrada

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

Abrir a chamada

frame 01

fib(5)

↘ retorna pela pilha ↗

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.

duas leituras / mesmo problema

Menos chamadas, mais memória.

ingênuaO(2ⁿ)

Repete chamadas para os mesmos valores e torna a árvore de execução visível.

tempo O(2ⁿ) · espaço O(n)

memoizadaO(n)

Guarda cada resultado calculado e reutiliza o valor quando a mesma pergunta retorna.

tempo O(n) · espaço O(n)

Recursão ingênua 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.

01fib(n)

02se n ≤ 1: retorne n

03esquerda = fib(n - 1)

04direita = fib(n - 2)

05retorne esquerda + direita

O destaque acompanha o passo atual da variante ingênua; leia a linha destacada antes de avançar.