# 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.