CODEWITHSUNDEEP
pythonrecursiontimefibonacci
umad
umad

Reputation: 15

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

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)

Upvotes: 1

Views: 127

Answers (4)

cdlane
cdlane

Reputation: 41872

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.

Upvotes: 0

Abdellah karani
Abdellah karani

Reputation: 1

long long int fib(int F[], int N[], int n, long long int *calls) {
if (N[n] == n) return F[n];
else if (n == 0 || n == 1) {
    F[n] = n; N[n] = n;
    return F[n];
}
else {
    N[n] = n; F[n] = fib(F, N, n - 2, calls) + fib(F, N, n - 1, calls);

}
return F[n]; }

You can try this solution based on two lists. F[n] to store the result of fib(n) and N[n] to store the n.

Upvotes: 0

kaksi
kaksi

Reputation: 196

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

Upvotes: 2

sahasrara62
sahasrara62

Reputation: 11228

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

Upvotes: 1

Related Questions