Editing Memoization (section)

==Overview==

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 eliminating the primary cost of a call with given [[parameter (computer programming)|parameters]] from all but the first call made to the function with those parameters. The set of remembered associations may be a fixed-size set controlled by a replacement algorithm or a fixed set, depending on the nature of the function and its use.  A function can only be memoized if it is [[Referential transparency|referentially transparent]]; that is, only if calling the function has exactly the same effect as replacing that function call with its return value. (Special case exceptions to this restriction exist, however.) While related to [[lookup table]]s, since memoization often uses such tables in its implementation, memoization populates its cache of results transparently on the fly, as needed, rather than in advance.

Memoized functions are optimized for ''speed'' in exchange for a higher use of [[computer memory]] ''space''. The time/space "cost" of [[algorithm]]s has a specific name in computing: ''[[Computational complexity theory|computational complexity]]''. All functions have a computational complexity in ''time'' (i.e. they take time to execute) and in ''space''.

Although a [[space–time tradeoff]] occurs (i.e., space used is speed gained), this differs from some other optimizations that involve time-space trade-off, such as [[strength reduction]], in that memoization is a [[Run time (program lifecycle phase)|run-time]] rather than [[compile-time]] optimization. Moreover, strength reduction potentially replaces a costly operation such as multiplication with a less costly operation such as addition, and the results in savings can be highly [[machine-dependent]] (non-portable across machines), whereas memoization is a more machine-independent, [[cross-platform]] strategy.

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 <code><var>n</var> ≥ 0</code>, the final result of the function <code>factorial</code> is [[Invariant (computer science)|invariant]]; if invoked as <code>''x'' = factorial(3)</code>, the result is such that ''x'' will ''always'' be assigned the value 6. The non-memoized implementation above, given the nature of the [[recursion|recursive]] algorithm involved, would require ''n + 1'' invocations of <code>factorial</code> 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 <code>factorial</code> by ''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 <code>factorial</code> includes the cumulative cost of steps 2 through 6 proportional to the initial value of ''n''.

A memoized version of the <code>factorial</code> function follows:

 function factorial (''n'' is a non-negative integer)
     if ''n'' is 0 then
         return 1 [''by the convention that'' '''0! = 1''']
     else if ''n'' is in ''lookup-table'' then
         return ''lookup-table-value-for-n''
     else
         let x = factorial(n – 1) times ''n'' [''recursively invoke factorial''
                                          ''with the parameter 1 less than n'']
         store ''x'' in ''lookup-table'' in the ''n''<sup>th</sup> slot [''remember the result of n! for later'']
         return x
     end if
 end function

In this particular example, if <code>factorial</code> 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 <code>factorial</code> 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.