When making a program to obtain the numbers of the fibonacci sequence I did it in two ways, the first as a recursive algorithm (I tried this way since the book I read is about recursion) and I also did it in an iterative way . and when executing each one it works fine, however when you put it to calculate a somewhat large Fibonacci number (1000) the iterative function does it faster than the Recursive one. Why is this? Is there any way to minimize the time in the recursion?
First form (Recursive)
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
Second form (Iterative)
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
All this was executed in a Google Colab notebook
To minimize the recursion time, the most convenient thing would be to store the previous results so as not to recalculate them.
example:
execution time:
To the answer of why that happens, Candid Moe has already answered in the comments. As for making the recursive function faster, you can do it like this: