Optimización de Fibonacci

Tengan cuidado con fibonaccis muy grandes, podrían encontrarse con este pokemon legendario

Para el número 50 en recursivo mi computadora tardo: 5,394.27 segundos cerca de 1.5 horas
Resultado Recursivo: 20365011074
Tiempo Recursivo 5394.270832061768

Procesador (Intel® Core™ i7-8850H CPU @ 2.60GHz)
Memoria Ram 32gb

Para entender mejor escribí

memo[n] = resultado
        print(memo)

Y como resultado

![](

En esta pagina se muestra la solución de Fibonacci recursivo y Fibonacci Memoized con una animación.
https://www.cs.usfca.edu/~galles/visualization/DPFib.html

Con un decorador podríamos hacer un método general para memorizar

import hashlib
from time import time

data_memo = {}


def memoization(func):
    def func_wrapper(*kwargs):
        _hash = hashlib.md5((func.__name__+str(kwargs)).encode()).hexdigest()
        if _hash in data_memo:
            return data_memo[_hash]
        _result = func(*kwargs)
        data_memo[_hash] = _result
        return _result
    return func_wrapper


@memoization
def fibonacci_recursive_memo(n):
    return 1 if n == 0 or n == 1 else fibonacci_recursive_memo(n-1) + fibonacci_recursive_memo(n-2)


def fibonacci_recursive(n):
    return 1 if n == 0 or n == 1 else fibonacci_recursive(n-1) + fibonacci_recursive(n-2)


if __name__ == '__main__':
    n = int(input('chose a number: '))
    start = time()
    result = fibonacci_recursive_memo(n)
    end = time()
    print(f"result with memo {result} in {end-start}")
    start = time()
    result = fibonacci_recursive(n)
    end = time()
    print(f"result without memo {result} in {end-start}")

Dato curioso:

Si cambian por:

resultado = "{:.5e}".format(fibonacci_dinamico(n))

Tienen el resultado en notación cientifica.
El fibonacci de 1000 es 7.03 E 208
En relación,** los atomos de todo el planeta son 10 E 50**

Pdta: Antes de 2000 deja de funcionar porque el numero es muy largo, para el que se anime a averiguar como solucionarlo

Comparto una modificación que le hice al código, donde podemos ver como trabaja internamente, guardando cada número de fibonacci calculado para posteriormente consultarlo y usarlo para el calculo del numero siguiente.

def fibo_dinamico(n, memo={}):
    step = 0
    if n == 0:
        step += 1
        print(f'.........Caso base - Fibo({n}) = {0}')
        return 0
    elif n == 1:
        step += 1
        print(f'.........Caso base - Fibo({n}) = {0}')
        return 1
    try:
        print(f'..Consultando en dic_memo Fibo({n})')
        return memo[n]
    except KeyError:
        print(f'....No existe Fibo({n}) en el diccionario')
        print(f'......Calculando Fibo({n})')
        resultado = fibo_dinamico(n-1, memo) + fibo_dinamico(n-2, memo)
        memo[n] = resultado
        print(f'.........Se guardo Fibo({n})={resultado} en el diccionario')
    return resultado

if __name__ == '__main__':
    n = 5
    num_fibo_n = fibo_dinamico(n)
    print('*'*40)
    print(f'El numero Fibo({n}) = {num_fibo_n}')

https://github.com/karlbehrensg/programacion-dinamica-y-estocastica
Optimización de Fibonacci

La serie de Fibonacci se representa como Fn = Fn-1 + Fn-2 y es muy simple implementarla de forma recursiva en código. Sin embargo es muy ineficiente hacerlo simplemente recursivo, ya que repetimos varias veces el mismo computo.

Si te fijas en la imagen te darás cuenta de que repetimos varias veces el calculo para f(4), f(3), f(2), f(1) y f(0), esto significa que nuestro algoritmo crece de forma exponencial O(2^n).

Para optimizar nuestro algoritmo implementaremos en primer lugar la función recursiva para luego dar paso a la memorización, con esto las mejoras serán realmente sorprendentes.

# Importamos la librería sys para subir el limite de recursividad de Python.
import sys

# La función recursiva realiza varias veces los mismos cálculos.
def fibonacci_recursivo(n):
    if n == 0 or n == 1:
        return 1

    return fibonacci_recursivo(n - 1) + fibonacci_recursivo(n - 2)


# En cambio en la función dinámica vamos a utilizar la técnica de la
# memorización, guardando los resultados ya hechos en un diccionario.
def fibonacci_dinamico(n, memo = {}):
    if n == 0 or n == 1:
        return 1


    # Primero intentamos buscar el resultado en memoria.
    try:
        return memo[n]

    # En caso de no existir realizamos el cálculo.
    except KeyError:
        resultado = fibonacci_dinamico(n - 1, memo) + fibonacci_dinamico(n - 2, memo)
        memo[n] = resultado

        return resultado

if __name__ == '__main__':
    sys.setrecursionlimit(10002)
    n = int(input('Escoge un numero: '))
    resultado = fibonacci_dinamico(n)
    print(resultado)

Resumen para estudiar

-Con fibonacci_rescursivo hace varios calculos, independiente de si los ah calculado o no.
Ej: Si queremos el fibonacci de 6 en algun momento calcularemos 5 veces el fibonacci de 2, ahora imaginense de los demas numeros, o incluso si es un numero enorme como 500.

-Fibonacci_dinamico la gran ventaja que nos ofrece es que guarda el computo ya hecho, ejemplo, si ya ah calculado fibonacci de 2, no es necesario recalcularlo otra vez, ya que la primera vez que lo hace, lo guarda dentro de un diccionario, osea que el programa tiene memoria

-La ventaja de guardarlo dentro de diccionarios es que su complejidad es 0(1), quiere decir que no importa cuan grande sea el diccionario, se tardará lo mismo buscando un elemento, ya que en un diccionario se busca la clave correspondiente al resultado.

Para entender mejor el porque de los diccionarios, nuestro compañero @Daniel Torres lo explica mas a fondo en comentarios mas abajo

En la forma de calcular la intensidad de campo eléctrico o magnético de ciertos sistemas, deben utilizarse funciones u operaciones que dependen del resultado de una o varias iteraciones previas. Se les conoce como elementos finitos.

Acá un link para que se fijen: (https://www.researchgate.net/publication/260591308_METODO_DE_ELEMENTOS_FINITOS_EN_DOS_DIMENSIONES_PARA_ESTUDIO_DE_PROPAGACION_EN_POTENCIALES_ELECTROSTATICOS)

Generalmente se utilizan fórmulas matemáticas que ya han modelado un sistema, es decir que esas fórmulas describen el comportamiento de ese sistema de manera muy acertada.

También en matemáticas financieras, los cálculos de algunos tipos de intereses tienen fórmulas recursivas.

En esta imagen, los valores de las cajas en azul son valores que ya se han calculado, por esto sólo se consulta el valor en el diccionario y pasa de ser una función recursiva con complejidad O(2**n) a una función recursiva O(n) [sin embargo el espacio donde se almacenan los resultados tambien se convierte en O(n)]

Conclusion
Memoization es una técnica de funciones con almacenamiento (caching functions) es decir las funciones tienen memoria, y los ususarios de las funciones no necesitan saber si la función tiene memoria o no. En ocasiones este tipo de funciones no requieren hacer ningun calculo sino devolver el resultado almacenado.

En este articulo pueden encontrar la información que les compartí y más detalles.

https://medium.com/@chialunwu/wtf-is-memoization-a2979594fb2a

He encontrado este interesante articulo que fortalece lo aprendido durante esta clase http://www.cs.wm.edu/~rml/teaching/python/functions/recursion.html
Recomiendo leerlo despues de acabar la clase

Dejo el código con comentarios

'''
En este caso se usaran la memoization para optimizar el algoritmo recursivo
Esta tecnica sacrifica espacio en memoria por tiempo
'''
import sys
#Función fibonacci recursivo
def fibonacciRecursivo(numero):
    if (numero == 1 or numero == 0):
        return 1

    return fibonacciRecursivo(numero - 1) + fibonacciRecursivo(numero - 2)
#Función Fibonacci memoization
#Como parametro tiene el numero y un diccionario inicializado sin tamaño fijo y vacio
def fibonacciDinamico(numero, diccionario = {}):
    #Este es el caso base que finaliza la recursion
    if(numero ==1 or numero == 0):
        return 1
    #La función try verifica si una operación puede ser ejecutada. En este caso verifica
    #si el diccionario contiene datos para la palabra clave o key: numero
    #si exite retornara el resultado sin ejecutar la recursión, es en este punto donde 
    #mejora los tiempos de procesamiento, es más rapido buscar en un diccionario que ejecutar la recursión 
    #En pocas palabras si el fibonacci de un numero ya se calculo antes estara guardado en memoria
    try:
        return diccionario[numero]
    #La función excep se ejecuta cuando no se logra ejecutar o no se obtienen datos en el try
    except:
        #Si es un numero que no se ha calculado nunca se ejecutara la recursión normal
        resultado = fibonacciDinamico(numero -1, diccionario) + fibonacciDinamico(numero - 2, diccionario)
        #Salvo que el resultado se guardara en el diccionario usando como palabra clave el numero para el que se calcula
        #De esta manera se ira creando la base de datos de los resultados para cada numero nuevo
        diccionario[numero] = resultado
        return resultado

if __name__ ==('__main__'):
    sys.setrecursionlimit(100)
    dato = int(input('Digita un numero para calcular su Fibonacci: '))
    print(f'El fibonaci de {dato} es: {fibonacciDinamico(dato)}')
    print(f'El fibonaci de {dato} es: {fibonacciRecursivo(dato)}')

Hice la siguiente locura para el fibonacci recursivo:

Modifique la funcion para que mostrara calculando fibonacci de n

llame el programa dandole una entrada desde archivo y sacando los resultados a otro archivo, se cuentan las lineas y se sabe cuantas recursiones hizo.

fibonacci de 20:

~/cursoEstocastica $ echo 20 > numero20
 ~/cursoEstocastica $ /bin/python3 optimizacion1_fibonacci.py <numero20 >fr20.txt 

~/prueba fibonacci $ tail -n3 fr20.txt
calculando fibonacci de 1
calculando fibonacci de 0
10946

~/prueba_fibonacci $ wc -l fr20.txt
21892 

fibonacci de 20 es 10,946 iteraciones: 21,891

Ahora para n = 30

~/cursoEstocastica $ echo 30 > numero30
 ~/cursoEstocastica $ /bin/python3 optimizacion1_fibonacci.py <numero30 >fr30.txt
  
tail -n3 fr30.txt
calculando fibonacci de 1
calculando fibonacci de 0
1346269

~/prueba_fibonacci $ wc -l fr30.txt
2692538 

fibonacci de 30 es 1,346,269 iteraciones: 2,692,537

ahora para n=40

~/cursoEstocastica $ echo 40 > numero40
~/cursoEstocastica $ /bin/python3 optimizacion1_fibonacci.py <numero40 >fr40.txt 

tail -n3 fr40.txt
calculando fibonacci de 1
calculando fibonacci de 0
165580141

~/prueba_fibonacci $ wc -l fr40.txt
331160282

fibonacci de 40 es 165,580,141 iteraciones: 331,160,282

La locura es que casi acabo con mi disco duro:

~/prueba fibonacci $ ls -l
total 8480784
-rw-rw-r-- 1 julio julio     569422 jun 23 18:40 fr20.txt
-rw-rw-r-- 1 julio julio   70034644 jun 23 18:42 fr30.txt
-rw-rw-r-- 1 julio julio 8613691911 jun 23 18:49 fr40.txt
-rw-rw-r-- 1 julio julio          3 jun 23 18:40 numero20
-rw-rw-r-- 1 julio julio          3 jun 23 18:42 numero30
-rw-rw-r-- 1 julio julio          3 jun 23 18:43 numero40
-rw-rw-r-- 1 julio julio          0 jun 23 19:15 prueba.txt

la prueba con n=40 se comio 8 gigas!!!

Pueden conseguir una explicación muy buena (parte visual incluida) y otra forma de implementar esto, en el siguiente video:
https://www.youtube.com/watch?v=Qk0zUZW-U_M

Optimización de Fibonacci:

• La solución recursiva clásica es muy ineficiente, puesto que crece de manera exponencial (O(n**2), ya que llamamos a la función 2 veces más por cada incremento de n)
• Logramos optimizar esta función a una complejidad lineal (O(n)) guardando en un diccionario los resultados obtenidos previamente.

Notas:

• En python es usual el uso de la expresión try/except (pedir perdón antes que pedir permiso)
• La recursividad máxima en python por defecto es 1000, se puede modificar en el comando sys.setrecursionlimit(<nuevo_limite>)
• Puesto que intercambiamos tiempo por memoria, si excedemos las capacidades de nuestro computador puede aparecernos un error de memoria: MemoryError: Stack overflow

Creo que hacer programas que resuelvan una sumatoria matemática con Memoization puede optimizar mucho el tiempo de respuesta con números grandes.

En este algoritmo los fibonacci se van almacenando en el diccionario memo, digamos queremos obtener F(4) , lo que hace es :
f(4) = f(3) + f(2), no hay ningun valor en memo, entonces sigue la recursividad:
f(4) = f(2) + f(1) + f(1) + f(0), aca ya sabemos que f(1 o 0) = 1, estos fibonacci no los guarda, solo retorna 1
f(4) = f(2) + 1 + 1 + 1, entonces ya obtuvo f(2) = 2 y lo almacena en memo:
f(4) = 2 + 1 + 1 +1, obtuvo f(3) y lo almacena en memo
f(4) = 5, y hace lo mismo de forma progresiva
Asi lo logre entender mejor.

Wow Excelente, la verdad que me quedé sorprendido y por poco me salto este curso.

En mi maquina paso algo curioso, con el código de programación dinámica a partir del 2998 no me muestra el resultado en pantalla, tengo algunas cosas abiertas como Docker, mi teoria es que se quedo sin memoria RAM en ese punto para poder procesar más, ¿o que podría estar sucediendo?

Modifique el código para poder ver la cantidad de veces que se ejecuta el ingreso a la función tanto recursiva como dinámica, esto verifica que la función recursiva pasa de ser exponencial (O(n**n)) a la función dinámica ser lineal (O(n)).
algunos de los resultados:

La secuencia de fibonacci en la posición 5 es 8
Se ejecuto la función recursiva 15 veces
Se ejecuto la función dinámica 9 veces

Tambien para el número 15

La secuencia de fibonacci en la posición 15 es 987
Se ejecuto la función recursiva 1973 veces
Se ejecuto la función dinámica 29 veces

Y para el número 25:

La secuencia de fibonacci en la posición 25 es 121393
Se ejecuto la función recursiva 242785 veces
Se ejecuto la función dinámica 49 veces

Es increible el cambio, para números mas grandes puse comentarios al llamado a la función recursiva o no terminaria, los cambios de la dinámica son:

La secuencia de fibonacci en la posición 50 es 20365011074
Se ejecuto la función dinámica 99 veces

La secuencia de fibonacci en la posición 100 es 573147844013817084101
Se ejecuto la función dinámica 199 veces

La secuencia de fibonacci en la posición 500 es 22559151616193633087251269503607207204601132491375819058863886641847
4627738686883405015987052796968498626
Se ejecuto la función dinámica 999 veces

Escoge un número: 5000
La secuencia de fibonacci en la posición 5000 es 7088069496231111407908953313902398529655056082228.....(son demasiados números)
Se ejecuto la función dinámica 9999 veces

Como se ve la cantidad de veces que se ingreso a la función se vuelve lineal, dejare el código respondiendo una pregunta para no hacer este post mas largo.

Detuve el cronometro de fibonacci_recursivo en 13 min. y aun no llegaba al resultado. Con fibonacci_dinamico fue super rápido

Excelente tema y explicación. A tener en cuenta en el algoritmo del profesor: Fibonacci de 0 es 0 y de 1 es 1

import time
import sys

def fibonacci_recursivo(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci_recursivo(n - 1) + fibonacci_recursivo(n -2)

def fibonacci_dinamico(n, memo = {}):
    if n == 0:
        return 0
    elif n == 1:
        return 1

    try:
        return memo[n]        
    except KeyError:
        resultado = fibonacci_dinamico(n - 1, memo) + fibonacci_dinamico(n - 2, memo)
        memo[n] = resultado
        return resultado

def main():
    sys.setrecursionlimit(10002)
    n = int(input('Escoge un número: '))

    tiempo_ini = time.time()
    # resultado = fibonacci_recursivo(n)
    resultado = fibonacci_dinamico(n)
    tiempo_fin =  time.time()
    print(f'El resultado es {resultado} y el tiempo para calcularso fue de {tiempo_fin - tiempo_ini}')

if __name__ == "__main__":
    main()

Yo hice una busqueda en Stack Overflow de algún código de fibonacci y encontré uno que me sirvió de base para crear esta solución que me parece mas intuitiva y no consume tanta memoria.
Igual no se si es una solución valida, así que acepto sugerencias.

import time


def fibonacci(n):
    fibonacci_numbers = [0, 1]
    for i in range(n-1):
        fibonacci_numbers.append(fibonacci_numbers[0]+fibonacci_numbers[1])
 
        del fibonacci_numbers[0]

    return fibonacci_numbers[1]


if __name__ == '__main__':
    n = int(input('Elige un numero: '))
    #n = 4000000

    start = time.time()
    print(fibonacci(n))
    end = time.time()


    number = end-start

    print(f'Fibonacci de {n}')
    print(f'Tiempo de ejecucion: {number}')
    print(f'Tiempo en minutos: {number/60}')
    print('---'*50)

Fibonacci de 4 000 000
Tiempo de ejecucion: 598.9549551010132
Tiempo en minutos: 9.982582585016887

No pongo el resultado por que es muy muy grande

sys.setrecursionlimit(100002)
sys.set_int_max_str_digits(1000000)

aumentando límites xd el número más grande que probé fue 50000

al reto de fibonacci recursivo de 50.
a mi se me demoro 31min appx en calcular el resultado. Con ese tiempo, no quiero probar los 500.

Cuando introdujeron Fibonacci dentro de este learning path busque videos para ayudarme a comprender más el tema de recursividad, de todos ellos este fue el más util que encontré:
Me sorprendió ver como de diferentes maneras podemos resolver un problema, incluso si implementamos las mismas ideas (no se si me explico xD)

Tal vez estoy mal pero en todos los sitios donde investigo, el Fibonacci de 5 da 5. Con el codigo que creamos en esta clase da 8. ¿Cuál es el real?

Dejé 10min computando el fibonacci de 50 con la función recursiva, y ni así lo terminó de calcular.

Duró un instante con memorización. Aquí les dejo el número:
20,365,011,074

A manera de recomendación en estos ejercicios que son tan abstractos, deberían apoyarse en recursos visuales para que el que tome el curso comprenda de manera la implementación de estos algoritmos, saludos

Una técnica de optimización combinatorica permite encontrar una formula no recursiva para Fibonacci y otras funciones recursivas como los números de Catalan. Esta técnica se llama funciones generatrices, en este pdf se explica en detalle como usar esta técnica. Las secciones 1, 2 y 3 son introductorias, en la sección 4 se explica la técnica, en la sección 5 hay otro ejemplo de esta técnica, en el apéndice de la sección 9 se explica como se hacen los calculos mas complicados. (https://www.miguelmath.com/Combinatorics-spring-2018.pdf)

Una forma de escribir rapido el:
if __name__=='__main__':
Es escribiendo main en VS y presionando enter, a mi me ahorra 2 o 3 segundos de vida 😁

Consejo antes de ver este vídeo: averiguen qué es la sucesión de Fibonacci ¿Para qué? Para saber qué es lo qué van a hacer y para qué sirve.
Para dejarlo más claro pongo un vídeo aquí de la sucesión de Fibonacci: https://www.youtube.com/watch?v=yDyMSliKsxI

La serie Fibonacci
Si tienen dudas sobre la serie de números de Fibonacci, se construye de la siguiente manera:

• Si ustedes hacen la serie les da:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34…

• El subíndice en realidad es muy importante, pues representa la posición del número que quieres hallar.

• Por ejemplo para el subíndice n = 50, el número de Fibonacci F50 es un número muy grande porque es una serie que crece muy rápido. Entonces, si la serie comienza con:
  n = 0, F0 = 0, F50 = 12586269025. Que es como está implementado en la función de la imagen.

• Si la serie comienza con n = 0, F0 = 1, saltándose el 0, entonces:
  F50 = 20365011074, como le da a al profe David.

La memorización convierte el algoritmo de fibonacci de exponencial O(2**n) a lineal O(n). Es bellísimo, les dejo una gráfica que hice con bokeh y el código. https://github.com/Angrub/dinamic_fibonacci/blob/main/README.md
x = número de fibonacci
y = número de pasos

woooooow hace un tiempo implemente esta misma optimizacion para trabjar con un datasets, de 20s en hacer un cambio pase a 0.6s

Muy interesante el ejemplo

Yo al principio no entendia como funcionaba memo, literal parecia magia pura, pero dibuje los frames en un papel y FUA, entendi todo a la perfeccion jajajaj

#Si hay un numero en la posicion n, devolvemos ese valor y corta la recursividad, esto nos ahorra muchisimo tiempo, porque cuando entra al segundo fibonacci, literalmente solo toma memo[n] y listo
#El que penso en esto es un crack

Hola otro forma de usar la programación dinámica es para optimizar la forma de encontrar números primos.
Los invito a ver el tutorial que creé si quieren saber mas al respecto -> https://platzi.com/tutoriales/1835-programacion-estocastica/5328-usar-programacion-dinamica-para-buscar-numeros-primos/
saludos!

Cuando empezaba a estudiar python, uno de los ejercicios era generar la secuencia de Fibonacci. No me di cuenta que hicimos un algoritmo eficiente usando sólo bucles.

print('Secuencia de Fibonacci \n\n')
limite = int(input('Escribe el elemento de la serie: '))
Fib = [1,1]
if limite > 1:
	for i in range(2, limite+1, 1):
		Fib.append(Fib[i-2] + Fib[i-1])
print(Fib[limite])

funciona igual de rápido 😄

La diferencia entre ttiempos es brutal!!!

Esto me funciono rebien, no pude desifrar un error que me dio en el codigo de profe Aroesti.

Super, lo de la memoization es muy heavy 🤯

entonces creo que entendi bien… lo que hacemos en este caso es guardar los numeros en un diccionario(‘memo’) para que cuando los ocupemos el calculo sea mas rapido? :0

Desarrollé este código de fibonacci hace tiempo y es más eficiente ahora que lo comparo con el código del profe, pero, por qué?

def run():
    contador = int(input("cuantos números fibonacci quieres?: "))
    i = 0
    a , b = 0, 1
    while i < contador:
        a = a + b
        b = a - b
        i += 1
        print(f'({i})', a)

if __name__=='__main__':
    run()

prueben con cualquier número, 5k, 10k, 100k, no tarda nada(claro, tarda solo el print)

rats…

Este enlace muestra un simulacion de como funciona la pila stack en los algoritmos de Fibonacci Recursivo, Memoizado y de tabla que al parecer es mas optimo que los demas

https://www.cs.usfca.edu/~galles/visualization/DPFib.html

si hay muchos numeros casi imposible de leer pueden usar notacion cientifica

from decimal import Decimal 
'%.2E' % Decimal(resultado) ```
ejemplo 
Fib de 900 
8.88e+187

#crear diccionario    
memo={}
#definir funcion fibo
def fibo_dina_1(n):
    #si n ingresado esta en el diccionario, devuelve el valor grabado, 
    #caso contrario calculalo
    if n in memo:
        #aqui encuentra el valor grabado
        return memo[n]
    if n==0 or n==1:
        value=1
    else:
        #aqui lo calcula
        value=fibo_dina_1(n-1)+fibo_dina_1(n-2)
    #grabar el valor calculado en el diccionario con indice n
    memo[n]=value 
    #la funcion retorna el valor grababo en el diccionario con indice n
    return memo[n]

Super clase 💪

Yo utilizaría programación dinámica para filtrar búsquedas en el front end. Así solo tendría que hacer una llamada al back-end para filtrar y en caso de que el usuario repita una búsqueda, se muestra de inmediato.

Les comparto el mismo método pero con factorial. Es un código muy sencillo y evita que explote tu computadora al intentar calcular números grandes.

import sys

def factorial(n, memo = {}):
    """Calcula el factorial de n.
    n int > 0

    returns n!
    """

    if n == 1:
        return 1
    try:
        return memo[n]
    except KeyError: 
        resultado = n * factorial(n - 1, memo)    
    return resultado

if __name__ == '__main__':

    sys.setrecursionlimit(10002)

    n = int(input("escribe un entero:  "))

    resultado = factorial(n)

    print(f'Su resultado es: {resultado}')

Hay un error fibonacci de 0 es 0 no 1 creo que hubo una confusión con factorial 0! = 1
El programa da los números de fibonacci pero recorridos un lugar

Corrijanme se me equivoco …
La sucesión de Fibonacci inicia con 0, es decir …
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

A mi me crasheo Python con F(5000) y f(10000) D:

me sucede algo extraño…
al ampliar el límite de recursividad, solo me deja calcular hasta 2286, de ahí en adelante no muestra el resultado, termina la función sin imprimir ningún valor.
Alguna idea por qué?

Hola amigos, encontré una tercera forma de hacerlo. En realidad es igual que con el método dinámico que nos enseñó el profesor, pero en lugar de crear un diccionario, usamos el decorador de python @lru_cache de la librería functools. Les dejo mi código con las 3 implementaciones:

"""
Fibonacci sequence:
1,1,2,3,5,8,13,21,34,...

n : 1 --> 1
n : 2 --> 1
n : 3 --> 2
n : 4 --> 3
n : 5 --> 5
n : 6 --> 8
...

- El siquiente numero de la secuencia de fibonacci es la suma de los dos terminos anteriores.
- A veces se suele incluir el 0. Eso depende de una decision personal la mayoria de los casos.
"""
from functools import lru_cache

# Funcion recursiva que obtiene el n-esimo termino de la secuencia Fibonacci
# Muy ineficiente
def fibonacci_recursivo(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fibonacci_dinamico(n-1) + fibonacci_dinamico(n-2)

# Funcion de Fibonacci dinámica que obtiene el n-ésimo termino de la secuencia
def fibonacci_dinamico(n, memo = {}):
    if n==1 or n==2:
        return 1
    else:
        try:
            return memo[n]
        except KeyError:
            resultado = fibonacci_dinamico(n-1, memo) + fibonacci_dinamico(n-2, memo)
            memo[n] = resultado

            return resultado

# Una alternativa a la función fibonacci_dinamico. Obtiene el n-ésimo termino de la secuencia
# En esta función nos auxiliamos de la libreria de python. El resultado se obtiene de manera tan eficiente que con fibonacci_dinamico.
# Mas información: https://docs.python.org/3/library/functools.html
@lru_cache(maxsize = 1000)
def fibonacci_dinamico2(n, memo={}):
    if n == 1 or n == 2:
        return 1
    return fibonacci_dinamico(n-1) + fibonacci_dinamico(n-2)

# Funcion principal
def main():
    n = int(input("Escoge un numero: "))
    resultado = fibonacci_dinamico2(n)
    print(resultado)

if __name__ == "__main__":
    main()

Como ven, la función fibonacci_dinamico2 es igual a la función fibonacci_recursivo solo que antes le agregamos el decorador lru_cache.

Esta forma es con un loop pero sin guardar en memoria

def fibonacci_iterativo(n):
    resultado_anterior, resultado_actual= 0, 1

    for i in range(n):
        resultado_anterior, resultado_actual = resultado_actual, resultado_actual + resultado_anterior

    return resultado_actual

Un poco más comprendido al tema del trade of: tiempo vs espacio

antes de iniciar la clase hice este pequeño codigo para calcular la secuencia que desee ver el usuario:

def Fibonacci(i_objetivo):
lista=[1,1]
for i in range(i_objetivo+1):
if i <=2:
Resultado=1
else:
Resultado=lista[0]+lista[1]
lista[0]=lista[1]
lista[1]=Resultado
#print(lista)
print(Resultado)
if name == ‘main’:
i_objetivo = int(input('cual item desearia saber: '))

Fibonacci(i_objetivo)

Corregidme si me equivoco, pero creo que hay un error en el algoritmo de David:

if  n==0  or  n==1:
    return 1

es errónea. Fibonacci de 0 es 0, pero según el código de arriba devuelve 1. Debería ser:

if  n==0:
	return 0
if  n==1:
	return 1

Me pareció más fácil como lo explica aquí, incluso hasta como ordena el código:

https://www.youtube.com/watch?v=Qk0zUZW-U_M

Programación dinámica
Poco tiene que ver con su nombre, es solo una técnica para optimizar ciertos tipos de problemas. Especificamente los problemas que tienen:

1. Subestructura óptima: cuando una solución óptima global se puede encontrar al combinar soluciones óptimas de subproblemas locales. Es decir, encontrar las soluciones óptimas de problemas más pequeños.
Ejemplos: Fibonacci, Problema del morral, Merge sort.

2. Problemas empalmados: Soluciones óptimas que involucra resolver el mismo problema varias veces (recursividad).
Ejemplo: Fibonacci, Problema del morral.

Aclaración: en Merge sort, cada vez que se divide la lista, se tiene un nuevo problema. Por lo tanto, no aplica la PG en este caso.

**La forma de optimizar: Memoization **
Evita cómputos adicionales guardando el resultado de cálculos previos dentro de un diccionario (o estructura de datos), que tienen complejidad O(1). Al guardar los resultados en memoria, se ahorra tiempo de cómputo. Así, se intercambia tiempo por espacio.

😃

Una ilustración grafica de la optimización dinámica de fibonacci.

Un pequeño error, aunque no afecta el tema a tratar, es que en la serie de Fibonacci si el numero es igual a 0 se retorna 0 no 1, y si es 1 si se retorna 1.

miren amigos, yo lo hice con javascript y aqui lo dejo por si les sirve

function fibonacci_dinamic(n, memo = {}) {
  if (n == 0 || n == 1) {
    return 1;
  }
  if (memo[n]) {
    return memo[n];
  }
  var resultado =
    fibonacci_dinamic(n - 1, memo) + fibonacci_dinamic(n - 2, memo);
  memo[n] = resultado;
  console.log(memo);
  return resultado;
}

const resultado = fibonacci_dinamic(50);
console.log(resultado);

que locura… 😃

Hola a todos 👋🏾!
Utilizando python tutor, hice la prueba de hallar el número de Fibonacci tres veces en una misma ejecución para ver cómo funcionaba el diccionario en cada llamada de la función y el resultado fue el siguiente (🤯):

.
La primera entrada fue 10:
.

.
La segunda entrada fue 15:
.

.
La tercera entrada fue 5:
.

.
Si quieres probarlo por ti mismo 👉🏾aquí lo puedes hacer 👈🏾

en principio lo hice sin el if name …
y por alguna rázon que no me explico es mas lento asi.
aunque funciona
una vez lo pongo con ese iniciador, funciona de inmediato

😃 Intenté encontrar el fibonacci de 40 con el metodo recursivo y demoro 69 segundo

a mí me siguió respondiendo hasta el 999

Como consejo, en general nunca deberían utilizar recursión en la programación.
Una forma de implementar lo mismo sin el problema del límite de recursión (y algo así como 100 veces más rápido) sería un simple for loop

def fib(n):

    a, b = 1, 1

    for i in range(n):
        a, b = b, a+b
    
    return a

El Fibonacci de 50 es 20365011074

En mi pc el límite es 2131 de la serie de Fibonacci. No se puede ir más allá alargando el SYS porque literalmente parece que el micro no llega.
No sé si es problema de python o de mi compu pero siguiendo estos pasos de la clase me topé con este límite.
Tengo que añadir que a partir de números muy grandes Python ya no me devuelve ningún error, sólo pasa y ya.

Si estás leyendo esto seguro que puedes explicar el comportamiento de mi compu.
Responde este comentario y me cuentas porque estoy perdidísima

¿Qué es el entry point en python?

“En conclusión, nuestro entry point le ayuda al interprete de python internamente a identificar de que manera se debe ejecutar el o los módulos y/o scripts de python que le estamos pasando.”

https://n9.cl/knz4w9

Este algoritmo funciona bien y no da problemas de recursividad.

def fibonacci_dinamico_2(number):
    memo_dict = {0: 0, 1: 1}
    for i in range(number + 1):
        if i >= 2:
            resp = memo_dict[i - 1] + memo_dict[i - 2]
            memo_dict[i] = resp

    return memo_dict[number]

es un poco mas facil de entender si se imprimer el diccionario.

Para parar la ejecución de un programa desde la consola basta con poner ‘Ctrl+c’

😄

Para entender mejor el tema, fibonacci y memorización, tuve que leer este medium: https://medium.com/@porzingod/fibonacci-and-memoization-e99f765b97f6

Me costo un poco entenderlo, pero me ayudo verlo asi:

1. Crear un diccionario
2. return 1 para los primeros dos elementos de la secuencia
3. Revisar si ya tenemos guardado el numero n de la secuencia en el diccionario
4. Si esta, return el valor. Si no esta evaluar el número de la secuencia

.
Siempre revisamos si ya tenemos el valor n de la secuencia guardado en el diccionario.
Si no está, lo evaluamos.

y este comentario me salvo la vida

Hola creo que hay una forma mas eficiente. Llego a 400mil de fibonacci en menos de 2 segundos.
Con el fibonacci_dinamico(n) del curso se rompe todo mucho antes.

def fibonacci_faster(n):
    if n == 1 or n == 0:
        return 1
    primero = 0
    segundo = 1
    
    for i in range(n):
        resultado = primero + segundo
        primero = segundo
        segundo = resultado

    return resultado

Me puse rebelde y no quise usar la recursividad, 😅 y que creen,
logre llegar a la complejidad **O(n) ** A mi parecer lo hice bien… pero me gustaría leer tu recomendación.

def fibonacii_by_loop(n):
    #[{fibonacii:_2},{fibonacii:_1}, {fibonacii : _1 + _2 }]
    _1 = 1
    _2 = 0
    fibonacii = _1 + _2
    for i in range(1, n):
        _2 = _1
        _1 = fibonacii
        fibonacii = _1 + _2
    return fibonacii


def run():
    n = int(input('Escribe un número: '))
    print(fibonacii_by_loop(n))


if __name__ == '__main__':
    run()

pdsta: Si llegaste hasta aquí es por que eres grandioso o un curioso grandioso, jaja pero de todos modos eres grandioso!

Se puede profundizar este contenido a nivel de programacion con esta genial clase:
https://platzi.com/clases/2397-python-profesional/39532-la-sucesion-de-fibonacci/

En ingeniería de software analizar la complejidad algorítmica es primordial, por tanto, es importante entender un poco más que tipo de complejidad tiene nuestro algoritmo, les dejo este video, que explica a grandes rasgos como medirla: https://www.youtube.com/watch?v=IZgOEC0NIbw

Fuente Imagen: https://rootear.com/desarrollo/complejidades-algoritmos

<import sys

def fibonacci_recursivo(n):
    if n == 0 or n == 1:
        return 1
    return fibonacci_recursivo(n - 1) + fibonacci_recursivo(n - 2)

def fibonacci_dinamico(n, memo = {}):
    if n == 0 or n == 1:
        return 1
    try:
        return memo[n]
    except KeyError:
        resultado = fibonacci_dinamico( n - 1, memo) + fibonacci_dinamico(n - 2 , memo)
        memo[n] = resultado
        return resultado


if __name__ == '__main__':
    #cambiar limite de recursividad mediante la libreria sys
    sys.setrecursionlimit(10002)
    n = int(input('Escoge un número: '))
    resultado = fibonacci_dinamico(n)
    print(resultado)> 

import sys, sys.setrecursionlimit(10000) para aumentar el nivel de recursividad.

Para hacer memoization, solo necesitamos especificar cuándo se guarda el resultado, para luego acceder a él.

Fibonacci de 35 para arriba, empieza a ser lento.

memoization, es la forma en cómo aplicamos la programación dinámica.

Los números Fibonacci, pueden tomar muchos caminos.

Fibonancci, de por si solo, es bastante ineficiente.

Este vídeo es muy bueno para complementar!
https://www.youtube.com/watch?v=M3LkQiWVBoc

Es divertido utilizar recursividad para aprender, solo hay que tener cuidado de no usarlo en el trabajo, no es bien visto por la complejidad algoritmica que implica

Debe corregir el caso base de los números de Fibonacci.

Tomado de: https://es.wikipedia.org/wiki/Sucesión_de_Fibonacci