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)

Does the following help? stackoverflow.com/questions/29570870/… — qrsngky
– qrsngky, Commented Jul 18, 2022 at 3:33
As @qrsngky mentioned, memoization is one of the most valuable tricks to reduce Fibonacci. Check that already posted question. stackoverflow.com/questions/29570870/… — Chaotic Pechan
– Chaotic Pechan, Commented Jul 19, 2022 at 2:31
Does this answer your question? Memoization fibonacci algorithm in python — Chaotic Pechan
– Chaotic Pechan, Commented Jul 19, 2022 at 2:32

kaksi · Accepted Answer · 2022-07-18 11:06:22Z

2

Note that you do not need recursion:

a,b=0,1
print(a,b,end=' ')
for i in range(9):
  a,b=b,a+b
  print(b,end=' ')

Result:
0 1 1 2 3 5 8 13 21 34 55

answered Jul 18, 2022 at 11:06

kaksi

2512 silver badges9 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

sahasrara62 · Accepted Answer · 2022-07-18 05:07:14Z

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

edited Jul 18, 2022 at 5:07

answered Jul 18, 2022 at 3:37

sahasrara62

11.4k3 gold badges35 silver badges48 bronze badges

2 Comments

umad Over a year ago

Thanks sahasrara62! it help me a lot to understand the sequence and the problem!! have a good day!

sahasrara62 Over a year ago

@umad just modifed the solution, giving more specification, to make it more simple and easy to understand

cdlane · Accepted Answer · 2024-05-14 16:11:16Z

0

You can match the lru_cache solution without lru_cache by using a better algorithm. Instead of the simple, double recursion fibonacci, you can do a single recursion implementation:

def f(n, res=0, nxt=1):
    if n == 0:
        return res

    return f(n - 1, nxt, res + nxt)

This is as fast as lru_cache wrapped around a bad algorithm and has the added advantage that it can take arguments twice as large before getting a maximum recursion depth exceeded error. In a language with tail call optimization (not Python), this might become/tie iteration.

answered May 14, 2024 at 16:11

cdlane

42.2k5 gold badges37 silver badges87 bronze badges

Collectives™ on Stack Overflow

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

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related