Memoization is a computer science concept to optimize programs by avoiding computations that have already been done and to reuse it. This is achieved by storing the computaions in a lookup table and retrieving them if a need for it arrives in a future computation step.

Now, lets try to walk this concept using a Fibonacci series where each number in the series is sum of the previous two numbers. In the subsequent code, we are trying to find the value of the N’th term in the series.

Fibonacci Series -> 0, 1, 1, 2, 3, 5, 8, ....


def fib(n):
    if n == 0:
        return 0 
    if n == 1:
        return 1
    return fib(n-1)+fib(n-2)    

{% endhighlight %}

So, F(7) = F(6) + F(5) = [F(5) + F(4)] + [F(4) + F(3)] = [[F(4) + F(3)] + [F(3) + F(2)]] + [[F(3)+ F(2)] + [F(2)+F(1)]]
= [[[F(3)+F(2)] + [F(2)+F(1)]] + [[F(2)+F(1)] + [F(1)+F(0)]]] + [[F(3)+ F(2)] + [F(2)+F(1)]] = … = 8



If you notice, we are computing the `fib()` for all the positions less than 'N' from scratch to compute the `fib(N)`. And we could have easily stopped this process earlier if we had some of the values computed beforehand.

So, lets try our hand at coding a memoized version of `fibonacci` below.

{% highlight python %}

fib_list = [0,1]
def fib_mem(n):
    if len(fib_list) > n:
        return fib_list[n] 
    fib_val = fib_mem(n-1) + fib_mem(n-2)
    fib_list.append(fib_val) 
    return fib_val

In this new approach, we look for the value of f(n) in the list. If it exists we simply return it, else we compute it and store it in the list, so we can speed up future computations.

I was amazed to see the improvement in the speed of the computation. Infact computing using the pure recursive method for values > 39 was so slow, that I decided to not compute for N > 39. And, the meomized version is blazingly fast.

=====Non Mem=====
fibonacci(35) ->  9227465
T = 11.2710268497
fibonacci(32) ->  2178309
T = 2.53484201431
fibonacci(34) ->  5702887
T = 7.05076313019
fibonacci(39) ->  63245986
T = 77.6575329304

===== Mem=====
fibonacci_mem(35) ->  9227465
T = 6.98566436768e-05
fibonacci_mem(32) ->  2178309
T = 1.19209289551e-05
fibonacci_mem(34) ->  5702887
T = 1.21593475342e-05
fibonacci_mem(45) ->  1134903170
T = 2.50339508057e-05
fibonacci_mem(55) ->  139583862445
T = 2.88486480713e-05
fibonacci_mem(155) ->  110560307156090817237632754212345
T = 0.000208854675293