In computing, memoization is an optimisation technique used primarily to speed up

computer programs by caching the function results so that, later we can use that result,

when we call the function with the same arguments.

To explore memoization, lets consider the code segment for finding out the term of a

Fibonacci series:

*def fib(n):*

* if n<2:return n*

* else:*

* n=fib(n-1)+fib(n-2)*

* return n *

*Run the following command to find out the time taken for finding the nth term of the series *

**$ time python file_name.py**

So we would find out then that the time complexity of our program is O(exp(n)) .

Try and find out the 40th term of the Fibonacci series . This code segment will make you

wait for a considerable amount of time before you view your result in the terminal.

Is it possible to find out higher terms of the series much faster???

oh,yes!!

Here is the role of memoization.It caches the results that have been calculated earlier and

stores them in a lookup table so that these don’t have to be calculated again. We make use

of an associative array as a lookup table here.

The following code segment shows the memoized version:

*table={0:0,1:1}*

*def fib1(n):*

* if not n in table:*

* table[n]=fib1(n-1)+fib1(n-2)*

* return table[n] *

Run

**$ time python file_name.py **

Using this memoized function we would find out the higher terms of the series much faster.

But don’t forget everything has a reasonable limit