Algoritmos en Python

Recursive Fibonacci with Memoization in Python

Plain recursive Fibonacci repeats the same work millions of times. Add a cache and it becomes instant.

Intermedio
2 min de lectura
1 ejemplo ejecutable

Lo que aprenderás

Writing Fibonacci recursively
Why the plain version is exponential
Memoization with functools.lru_cache

Ejecutar en el compilador de Python →

fib(4) without a cache

fib(4)
- fib(3)
  - fib(2)
  - fib(1)
- fib(2)computed again

With @lru_cache the second fib(2) is read from the cache. fib(10) = 55.

Remember answers you already computed

Calcular Fibonacci con recursividad es muy corto pero lento, porque el mismo valor se recalcula muchísimas veces. La memoización (memoization) consiste en guardar el resultado de las llamadas anteriores para reutilizarlo después, en lugar de volver a calcularlo todo.

Puntos clave

fib(n) = fib(n - 1) + fib(n - 2), with fib(0) = 0 and fib(1) = 1.
Without a cache, fib(3) is recomputed many times inside fib(10).
@lru_cache stores each result, so every fib(k) runs once: O(n).

¿Cuándo se usa?

Desarrollar tu forma de pensar y entender paso a paso cómo funciona un algoritmo.
Elegir el enfoque adecuado cuando hay que procesar muchos datos o acelerar un programa.
Prepararte para exámenes, ejercicios y entrevistas de programación.

Mira cómo funciona

Pulsa Paso para seguir cada llamada. Fíjate en cómo fib calcula una y otra vez los mismos valores pequeños; por eso la versión simple es lenta.

Código de ejemplo

Ejecutar código →

main.py

from functools import cache

@cache
def fibonacci(number):
    if number < 2:
        return number
    return fibonacci(number - 1) + fibonacci(number - 2)

print(fibonacci(10))

Obtén un botón Run para este ejemplo

Resultado de la ejecución

Explicación del código

El decorador @cache guarda automáticamente el resultado de la función para cada valor de entrada. Una vez calculado fibonacci(8), las llamadas siguientes obtienen el resultado directamente. Así el tiempo de ejecución pasa de exponencial a O(n), a cambio de O(n) de memoria para guardar los resultados.

Cambia los valores y ejecuta el programa en el compilador Python online de CodeUtility sin instalar Python.

Ejercicios de práctica

Prueba a modificar el código siguiendo las ideas de abajo. Cambiar el código y ver el resultado te ayudará a entender la lección mucho mejor que solo leerla.

Prueba con una lista vacía, una lista de un solo elemento y una lista con repetidos.
Muestra el estado después de cada paso para ver el algoritmo en acción.
Mide el tiempo de ejecución con 100, 1.000 y 10.000 elementos y compáralo con otra solución.

Ejecutar en el compilador de Python →

Practica con un reto

Usa lo que cubre esta lección para resolver un problema real. Cada reto se ejecuta en el navegador, con pruebas al instante y una revisión de IA.

Todos los retos