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
    Commented el 12 abr. 2021 a las 19:18
  • 1
    Posiblemente te interese leer esta es.stackoverflow.com/q/443483/7123
    – abulafia
    Commented el 12 abr. 2021 a las 20:35

4 respuestas 4

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
0

Una solucion para la secuencia de fibonacci con recursividad. Saludos

f = []
def fibo(c = 0, n = 0, limit = 10):
    if c <= limit:
        if len(f) < 2:
            f.append(n)
            n += 1
            c += 1
            fibo(c, n)
        else:
            f.append(f[c-2] + f[c-1])
            c += 1
            fibo(c)

fibo(limit=10)
print(f)
Nuevo colaborador
Roberto Bravo es un usuario nuevo en el sitio. Tenlo en cuenta cuando preguntes por aclaraciones, comentes o respondas. Revisa nuestro Código de conducta.
1
  • 1
    Saludos, recuerda que siempre agregar una explicación de código para que tu respuesta sea mejor recibida por la comunidad. ;)
    – Israel-ICM
    Commented el 9 dic. a las 12:30
0

Una solucion para la secuencia de Fibonacci con iteraciones

# FIBONACCI CON ITERACIONES
def fibo(limit = 10):
    f = []
    for i in range(limit+1):
        if len(f) < 2:
            f.append(i)
        else:
            f.append(f[i-1] + f[i-2])
    print(f)

fibo()
Nuevo colaborador
Roberto Bravo es un usuario nuevo en el sitio. Tenlo en cuenta cuando preguntes por aclaraciones, comentes o respondas. Revisa nuestro Código de conducta.
1
  • 1
    Saludos, intenta siempre agregar el cómo funciona tu código para que tu respuesta sea mejor recibida por la comunidad. ;)
    – Israel-ICM
    Commented el 9 dic. a las 12:26

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.