A memoized function "remembers" the results corresponding to some set of specific inputs. Subsequent calls with remembered inputs return the remembered result rather than recalculating it, thus moving the primary cost of a call with given parameters to the first call made to the function with those parameters. Memoization is a means of lowering a function's time cost in exchange for space cost.
Consider the following pseudocode function to calculate the factorial of n:
function factorial (n is a non-negative integer)
if n is 0 then
return 1 [by the convention that 0! = 1]
else
return factorial(n - 1) times n [recursively invoke factorial
with the parameter 1 less than n]
end if
end function
For every integer n such that n≥0, the final result of the function factorial is invariant; if invoked as x = factorial(3), the result is such that x will always be assigned the value 6. A non-memoized version of the above, given the nature of the recursive algorithm involved, would require n + 1 invocations of factorial to arrive at a result, and each of these invocations, in turn, has an associated cost in the time it takes the function to return the value computed. Depending on the machine, this cost might be the sum of:
- The cost to set up the functional call stack frame.
- The cost to compare n to 0.
- The cost to subtract 1 from n.
- The cost to set up the recursive call stack frame. (As above.)
- The cost to multiply the result of the recursive call to
factorialby n. - The cost to store the return result so that it may be used by the calling context.
In a non-memoized implementation, every top-level call to factorial includes the cumulative cost of steps 2 through 6 proportional to the initial value of n.
A memoized version of the factorial function follows:
function factorial (n is a non-negative integer)
allocate temporary integer variable x
if n is in lookup-table then
return lookup-table-value-for-n;
else if n is 0 then
return 1 [by the convention that 0! = 1]
else
x = factorial(n - 1) times n [recursively invoke factorial with the parameter 1 less than n]
store x in lookup-table in the nth slot [remember the result of n! for later]
return x
end if
In this particular example, if factorial is first invoked with 5, and then invoked later with any value less than or equal to five, those return values will also have been memoized, since factorial will have been called recursively with the values 5, 4, 3, 2, 1, and 0, and the return values for each of those will have been stored. If it is then called with a number greater than 5, such as 7, only 2 recursive calls will be made (7 and 6), and the value for 5! will have been stored from the previous call. In this way, memoization allows a function to become more time-efficient the more often it is called, thus resulting in eventual overall speed up.