Recursion and Memoization - A Fibonacci Example

In this post, I will try to describe why memoization can be a great optmization technique in the recursive function implementations with an example of fibonacci sequence.

Straight from Wikipedia, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously processed inputs.

Basically, we maintain a lookup table and store the computer values for particular cases which lets us query and use the corresponding value for particular case present in the lookup tables. This reduces function call overheads. Now in order to understand why this is a great optimization technique in recursion, lets first draw a recursion tree for finding n^th term in fibonacci sequence.

                           fib(5)                          
                             /\                              
                            /  \
                           /    \
                          /      \                      
                     fib(4)       fib(3)                                 
                      /\               /\                          
                     /  \             /  \
                    /    \           /    \
                   /      \         /      \                         
               fib(3)    fib(2)     fib(2) fib(1) -> 1                                    
                  /\         /\          /\                          
                 /  \       /  \        /  \                         
                /    \     /    \      /    \
               /      \   /      \    /      \                        
          fib(2) fib(1) fib(1) fib(0) fib(1) fib(0) -> 0                                        
          /\        |     |      |        |    |               
         /  \       1     1      0        1    0               
    fib(1) fib(0)                                                       
       |      |                                               
       1      0 

We can clearly see the calls to fib() with same arguments several times. For example, fib(1) is called 5 times and fib(2) 3 times. Thus, we are repeating same calculations multiple times and imagine how this would look like for large value of n. If we would have maintained the value of fib(n) in the lookup table when computed the value for the first time.

The python code without memoization looks like below and notice the runtime:

#!/usr/bin/python

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

print fib(50)

And, now with the memoization, you will notice significant improvement in runtime.

#!/usr/bin/python

known = {0:0, 1:1}

def fib(n):
        if n in known:
                return known[n]
        known[n] = fib(n-1) + fib(n-2)
        return known[n]

print fib(50)

If you run and compare above two codes, you will find that the addition of memoization significantly improves the performance of recursive functions. Recursion are generally known to be terribly slow however memoization can make the difference insignificant. Some languages now provide memoization as the language feature natively or via third party APIs such as groovy memoize.


Read more...