Hay más de una manera de hacer las cosas. Siempre hay diferentes puntos de vista y estilos de lanzamiento.~Tim Hudson

En este artículo, utilizaremos tres técnicas diferentes en Python para codificar un programa básico de Fibonacci que dará como resultado la suma de la secuencia. En este caso la secuencia de Fibonacci es 0,1,1,2,3,5,8...

Como habrás notado, sumamos el primer y el segundo número 0 y 1, para obtener el tercer número de la secuencia (1) -> 0+1=1. Luego sumamos el segundo y el tercer número, 1+1=2, para obtener el cuarto número de la secuencia, así sucesivamente.

Puedes implementar este código en Jupyter, Colab o cualquier IDE o editor de texto con el que te sientas cómodo.

Cómo codificar la secuencia de Fibonacci utilizando un bucle for en Python

Aquí, he escrito un programa básico de Fibonacci usando un bucle for en Python. La lógica detrás de esto es simple y ya lo discutimos anteriormente.

La complejidad temporal es O(N) y la espacial es O(1) o constante. Pero, en realidad, es más complicado de lo que implica esta complejidad.

"Si, tu número es menor que N < 94, y utilizas un entero de 64 bits, entonces el algoritmo se comporta como una complejidad lineal. Sin embargo, para N > 94 empieza a comportarse como un algoritmo de complejidad cuadrática." ~ Michael Veksler
Imprimiendo resultado de un Fibonacci mediante un bucle For

Voy a ejecutar esto con el módulo %timeit de Python. Esto evita una serie de trampas comunes para medir los tiempos de ejecución. Puedes ver más usos aquí.

Se necesitaron 675 nanoSeg por bucle para 10

Cómo codificar la secuencia de Fibonacci con recursión en Python

En este caso, implementaremos la secuencia usando la recursividad. Las funciones recursivas tienden a llamarse a sí mismas para repetir hasta llegar al caso base. Así, la recursión crea una estructura de árbol ramificado.

Si, tomamos la serie de Fibonacci de 5, este es el árbol que se creará por recursión.

Diagrama de la recursividad de Fibonacci 5

La complejidad espacial es O(N) y la complejidad temporal es O(2^N), porque el nodo raíz tiene 2 hijos y 4 nietos. Y como puedes ver, cada nodo tiene 2 hijos.

Ahora la profundidad es N, lo que significa que tenemos que hacer esto N veces. Además, habrás notado que el subárbol de la derecha es más pequeño que el de la izquierda, por lo que el tiempo de ejecución real es aproximadamente O(1,6^N).

El caso base: Fibonacci(2) = Fib(1) + Fib(0) = 1 + 0 = 1

Imprimiendo del resultado de Fibonacci mediante recursión

El ejemplo de Fibonacci recursivo es definitivamente más rápido que el bucle for.

Medición de tiempo bucle for

Cómo codificar la secuencia de Fibonacci utilizando la memoiazación en Python

La memoización es una técnica que puede mejorar significativamente el rendimiento de una función recursiva al reducir la carga computacional.

Almacena los resultados de las llamadas de funciones costosas en un arreglo o diccionario y devuelve los resultados almacenados en caché cuando se llama a la misma entrada.

Puedes ver el árbol de arriba como referencia y cómo ciertas entradas siguen siendo recalculadas en cada llamada a ellas.

Impresión del resultado de Fibonacci mediante memoización

La complejidad temporal es O(nlogn).

Impresión del tiempo consumido

¿Qué es mejor, la recursión, los bucles for o la memoización?

Ahora bien, no se supone que estas técnicas sean mejores unas que otras. Simplemente hay que saber cuándo hay que utilizar una u otra. Lo cual, por supuesto, depende de sus necesidades.

La iteración será más rápida que la recursión porque la recursión tiene que lidiar con el marco de la pila de llamadas recursivas(stack frame). Pero, si la recursión se escribe en un lenguaje que optimiza la llamada de cola(tail), entonces elimina la sobrecarga y está casi a la par con los bucles for.

Por último, la memoización es mejor cuando el espacio de estados es disperso, es decir, no hay que resolver todos los subproblemas pequeños, sino sólo unos pocos.

¡Gracias por leer! Si te ha gustado este artículo, puedes leer mis otros artículos aquí. Puedes mostrar tu aprecio por este artículo compartiéndolo. También puedes conectar conmigo en LinkedIn.

Traducido del artículo de Diva Dugar - Memoisation, Recursion, and For Loops in Python Explained