Introduction To Memoization

Posted on Updated on

From a previous post on recursion we see that sometimes the sub problems of a recursive solution are related or overlapping in certain ways, the Fibonacci number sequence has sub-problems which overlap. From the recursion tree we notice that most calculations repeat, which causes inefficiency in the algorithm.

Recursion Tree:
recursion tree

The solution for Fibonacci 4, 3, 2, 1 and 0 is repeated on the left and right of the recursion tree, which makes the algorithm very inefficiently. What if there was a way we could store values for previously calculated Fibonacci numbers so that in the event that we need those solutions we could find them O(1) without doing any calculations.

In computingmemoization 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. Memoization has also been used in other contexts (and for purposes other than speed gains), such as in simple mutually recursive descent parsing[1] in a general top-down parsingalgorithm[2][3] that accommodates ambiguity and left recursion in polynomial time and space. Although related to caching, memoization refers to a specific case of this optimization, distinguishing it from forms of caching such as buffering or page replacement. In the context of some logic programming languages, memoization is also known as tabling;[4] see also lookup table more…

Original Algorithm:

def fib(num):
    if num < 2:return num     if num > 0 :return fib(num-1) + fib(num-2)

Memoized Version:

cache = {}
def fib(num):
    if num in cache:
        return cache[num]
        cache[num] = num if num < 2 else fib(num-1) + fib(num-2)
        return cache[num]

Pruned Recursion Tree:
The red lines on the above diagram shows the pruning on the recursion tree caused by the memoization of the algorithm. The algorithm is now much more efficient because it no longer needs to traverse the recursion tree for a value which has already been calculated. Until next time have fun :-)


4 thoughts on “Introduction To Memoization

    Orville Patterson said:
    December 11, 2012 at 8:24 am

    Awesome Algorithm

    gpandey said:
    January 25, 2013 at 9:57 am

    Made my day :)

    Security Dude said:
    April 28, 2013 at 1:54 pm

    The red lines on the above diagram shows the ***proning*** on the recursion tree … maybe you meant “pruning”

    Romaine Carter responded:
    April 29, 2013 at 6:45 am

    Thank for the correction Security Dude.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s