Memoization

Memoization is a technique that is associated with Dynamic Programming. The concept is to cache the result of a function given its parameter so that the calculation will not be repeated; it is simply retrieved, or memo-ed. Most of the time a simple array is used for the cache table, but a hash table or map could also be employed.

Example

Consider a naive function that recursively calculates the Fibonacci Sequence:

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

The above function runs in exponential time. Since $fib(n)$ will never change, and the function produces no side-effects (such as printing to a file), we can memoize the results, giving linear time.

declare fib_table as array; all values initialized to 0

function fib_memo(n)
   if (n = 0)
      return 0
   if (n = 1)
      return 1

   if (fib_table[n] == 0)
     fib_table[n] = fib_memo(n-1) + fib_memo(n-2)

   return fib_table[n]

Be careful when choosing a default value for the memoization table. Zero is fine for this example, because the only time zero appears is for $F_{0}$, which is accounted for explicitly. If your function's range is all integers, you may have to use an auxiliary table to keep track of whether a specific value has been computed.