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[edit]
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 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 , 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.