0

Al hacer un programa para obtener los numeros de la secuencia de fibonacci lo hice de dos formas, la primera como un algoritmo recursivo (probe esta forma ya que el libro que leo es de recursividad) y tambien lo hice de una forma iterativa. y al ejecutar cada una funciona bien, sin embargo al poner que calcule un numero de Fibonacci algo grande (1000) la funcion iterativa lo hace mas rapido que la Recursiva. A que se debe esto?, hay alguna forma de minimizar el tiempo en la recursion?

Primera forma (Recursiva)

def recu_fibonacci(fn):
  f1 = 1
  if fn<=f1:
    return fn
  else:
    fn = recu_fibonacci(fn-1) + recu_fibonacci(fn-2)
    return fn

def f(terms=3):
  if terms <=0:
    print('introduzca un termino valido')
  else:
    for i in range(terms):
      fibo = recu_fibonacci(i)
      # print(fibo)
    return fibo
f = f(terms=1000)
print(f'fibonacci = {f}')
#tarda algo de 1 hora

Segunda forma (Iterativa)

def fibonacci(post=0,actual=1,iteration=3):
  i = 0
  while i <= iteration
    nextNumber = post +actual
    
    post = actual 
    actual = nextNumber
    
    print(nextNumber)
    i +=1 
#tarda menos de 2 seg

Todo esto fue ejecutado en un cuaderno de Google Colab

2
  • La solución recursiva es como la iterativa, pero agregando una llamada a función en cada ciclo. Ese es un costo extra a pagar.
    – Candid Moe
    el 12 abr. 2021 a las 19:18
  • 1
    Posiblemente te interese leer esta es.stackoverflow.com/q/443483/7123
    – abulafia
    el 12 abr. 2021 a las 20:35

2 respuestas 2

1

para minimizar el tiempo de recursion lo mas combeniente seria almacenar los resultados previos para no volverlos a calcular

ejemplo:

# memoria: almacenara los valores previos
fibonacci_cache={}

def fibonacci(n):
    # si el valor esta almacenado en fibonacci_cache solo lo retornamos
    if(n in fibonacci_cache):
        return fibonacci_cache[n]

    if n==1:
        val=1
    elif n == 2:
        val=1
    elif n > 2:
        val = fibonacci(n-1) + fibonacci(n-2)

    # agregamos resultados a memoria fibonacci_cache
    fibonacci_cache[n] = val
    # retornamos valor
    return val


for x in range(1,1000):
    print(x, " : " ,fibonacci(x))

tiempo de ejecucion:

0.6742584705352783 segundos
0

A la respuesta de por qué pasa eso, ya te ha respondido Candid Moe en los comentarios. En cuanto a hacer más rápida la función recursiva, puedes hacerlo así:

def fibonacci(n, a=0, b=1):
    while n!=0:
        return fibonacci(n-1, b, a + b)
    return a

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.