### Automatic Memoization Sample

The boxes below may be used to compute values from the Fibonacci Sequence.
Because the computation uses a naïve, recursive version of Fib, it would
traditionally incur exponential runtime and appear to run forever sometime
around term 40. This page, however, rebinds the naïve function to an
automatically memoized version that provides linear runtime for uncomputed
terms, and amortized constant runtime for previously-computed terms (and any
terms that are lower than the highest computed term). It should compute large
terms nearly instantly, up to about term 1476 (after which most Javascript
engines will begin to simply return a result of "infinity"). The small cost for
this massive performance increase is space consumption linearly proportional to
the highest computed term.

The unmemoized Fibonacci source code used for this page can be found in the
file "./js/fib.js". The automatic memoization code used for this page can be
found in the file "./js/automatic_memoization.js". The actual call which
rebinds the Fibonacci function into an automatically memoized one can be seen
directly in the HTML for this page.

Back to main page.