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

### Like this:

Like Loading...

*Related*