# Memoization fibonacci algorithm in python

## Memoization fibonacci algorithm in python

You should return `memo[n]` always, not only on unseccesful look up (last line of `fastFib()`):

``````def fastFib(n, memo):
global numCalls
numCalls += 1
print fib1 called with, n
if not n in memo:
memo[n] = fastFib(n-1, memo) + fastFib(n-2, memo)
#this should be outside of the if clause:
return memo[n] #<<<<<< THIS
``````

The number of calls is reduced this way, because for each value of `n` you actually compute and recurse from at most once, limitting the number of recursive calls to `O(n)` (upper bound of `2n` invokations), instead of recomputing the same values over and over again, effectively making exponential number of recursive calls.

A small example for fib(5), where each line is a recursive invokation:

Naive approach:

``````f(5) =
f(4) + f(3) =
f(3) + f(2) + f(3) =
f(2) + f(1) + f(2) + f(3) =
f(1) + f(0) + f(1) + f(2) + f(3) = (base clauses) =
1 + f(0) + f(1) + f(2) + f(3) =
2 + f(1) + f(2) + f(3) =
3 + f(2) + f(3) =
3 + f(1) + f(0) + f(3) =
3 + 1 + f(0) + f(3) =
5 + f(3) =
5 + f(2) + f(1)  =
5 + f(1) + f(0) + f(1) =
5 + 1 + f(0) + f(1) =
5 + 2 + f(1) =
8
``````

Now, if you use memoization, you dont need to recalculate a lot of things (like `f(2)`, which was calculated 3 times) and you get:

``````f(5) =
f(4) + f(3) =
f(3) + f(2) + f(3) =
f(2) + f(1) + f(2) + f(3) =
f(1) + f(0) + f(1) + f(2) + f(3) = (base clauses) =
1 + f(0) + f(1) + f(2) + f(3) =
2 + f(1) + f(2) + f(3) =
3 + f(2) + f(3) =  {f(2) is already known}
3 + 2 + f(3) = {f(3) is already known}
5 + 3  =
8
``````

As you can see, the second is shorter than the first, and the bigger the number (`n`) becomes, the more significant this difference is.

It can be done with functools library in Python 3.2+

``````import functools

@functools.lru_cache(maxsize=None) #128 by default
def fib(num):
if num < 2:
return num
else:
return fib(num-1) + fib(num-2)
``````

#### Memoization fibonacci algorithm in python

The following method uses a minimal cache size (2 entries) while also providing O(n) asymptotics:

``````from itertools import islice
def fibs():
a, b = 0, 1
while True:
yield a
a, b = b, a + b

def fib(n):
return next(islice(fibs(), n-1, None))
``````

This implementation comes from the classic corecursive definition of fibonacci (a la Haskells https://wiki.haskell.org/The_Fibonacci_sequence#Canonical_zipWith_implementation).

For a more direct (corecursive) translation see https://gist.github.com/3noch/7969f416d403ba3a54a788b113c204ce.