How to reduce the running time of Fibonacci sequence (recursive function)

Question

n = 1
rep = 0

def f(n):
        if n == 0:
            return 0
        if n == 1:
            return 1
        return f(n - 1) + f(n - 2)
     
while rep <= 50:
  print(f(n))
  rep += 1
  n += 1

I need to print the Fibonacci number 1~50

But errors occur because of the running time of the code.

Q. How can I fix this code to run faster?

Q. The answer code moves the previous number, F(n-2) to a temporary function and carries the current number, F(n-1) to previous number, F(n-2); which makes those two numbers go back a step when Fibonacci numbers are lined up at a list.

(ignore Q2 if there is something wrong)

Answer 1

You need to save all the processed number so that your code can access those values fast.

what your code is doing, for a number n it is processing this way.

f(n) = f(n-1) + f(n-2)
     = (f(n-2) + f(n-3)) + (f(n-3) + f(n-4))
     = ((f(n-3) + f(n-4)) + (f(n-4)+f(n-5))) + ((f(n-4) + f(n-5)) + (f(n-5)+f(n-6))

     .
     .
     . 
     so on

so you can see, for single n, code is calling a few values multiple times. and again if n changes to n+1 whole same process are followed.

so to overcome this, you need to save the result of each call so that we can get the result in O(1) time.

you can use lru_cache (inbuilt) or dict (using custom decorator/function) to save value of each fibonaci index result.

Adding code with the lru_cache below.

from functools import lru_cache
n = 1
rep = 0
@lru_cache
def f(n):
        if n == 0:
            return 0
        if n == 1:
            return 1
        return f(n - 1) + f(n - 2)
     
while rep <= 50:
  print(f(n))
  rep += 1
  n += 1