An optimized python program to find the n th fibonacci number

We are familiar with the Fibonacci series and algorithm to find the n th Fibonacci number  using recursion. which may be as follows.

def fibonacci(n):factorial

    if n<2 : return n

    else: return fibonacci(n-1) + fibonacci(n-2)

Which seems to be a simple solution. But in actual practice using recursion is a tedious task for the computer. The complexity of calculation increases incredibly with an increase in single number. with this algorithm to compute fibonacci(30), it will take few seconds to calculate the result( result is 832040 ). Further increase in number may not produce any result due to stack overflow.  Recursion uses stacks to remember function calls and every computer has a stack size limit.If stack cannot hold these recursive function calls it will not produce any result or sometimes take long time to print result.So Even though recursion makes the solution is simple, it is always advisable to stay out from it.

But using python dictionary we can reduce the complexity of recursive function call by remembering the results of each function call and thus reusing the value straight away with out function call. It will dramatically reduce the recursive function call complexity. we can even compute fibonacci(220) ( I have done it in less than 1sec) easily. Here is the program.

def fib(n):
    if n<2 : return n
    elif not n in fib_dict :
            fib_dict[n]= fib(n-1) + fib(n-2)
    return fib_dict[n]

#dictionary which store Fibonacci values
fib_dict = {}
result = fib(220)
print result

# result :4244200115309993198876969489421897548446236915
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s