Overview
La versión recursiva de Fibonacci llama directamente a la definición matemática: fib(n) = fib(n-1) + fib(n-2) con casos base.
Analogy
Como preguntar a dos personas el resultado y combinarlos. Pero cada persona también pregunta a otras dos — el árbol crece exponencialmente.
Step-by-step
- Caso base: fib(0)=0, fib(1)=1
- Caso recursivo: fib(n) = fib(n-1) + fib(n-2)
- El árbol de recursión tiene 2^n nodos sin memo
- Con @lru_cache: cada estado se calcula solo una vez → O(n)
Visual
fib(4): fib(3)+fib(2)
= fib(2)+fib(1)+fib(1)+fib(0)
= fib(1)+fib(0)+1+1+0 = 3
Common mistakes
- Olvidar el caso base → recursión infinita
- No añadir memoización para inputs grandes
Practice questions
- Agrega @lru_cache y compara tiempos de ejecución
- Dibuja el árbol de recursión para fib(5) a mano
Time
O(2^n) sin memo, O(n) con memoización
Space
O(n) — profundidad de pila