fig computing fib( as you can see from fig it takes lot of calls to the fib function to compute fib( now imagine how many calls it would take to compute fib( to compute fib( we first have to compute fib( and then compute fib( it took calls to fib to compute fib( and from the figure we can see that it takes calls to compute fib( including the call to fib( it will take calls to fib to compute fib( computing fib( will take calls or calls computing fib(nthis way more than doubles the number of calls to compute fib( - this is called exponential growth the complexity of the fib function is ( function with exponential complexity is worthless except for very small values of all is not lost there are better ways of computing the fibonacci sequence the way to improve the efficiency is to avoid all that unnecessary work once fib( has been computedwe shouldn' compute it again we already did that work there are at least couple of ways of improving the efficiency one method involves removing the recursion and computing fib(nwith loopwhich is probably the best option howeverthe recursive function is closer to the original definition we can improve the recursive version of the function with memoization in sect the memo dictionary serves as our mapping from values of to their fib(nresult memoized fibonacci function memo { def fib( )if in memoreturn memo[ if = memo[ this copy belongs to 'acha