如果使用这种递归的写法去计算第 50 个 fibonacci 数值，需要执行 40730022147 次。随着执行次数的增加，执行所需时间成指数上涨：
<code>memoization</code>的技巧在于将计算过的结果『缓存』下来，避免重复计算带来的成本，例如将计算 fibonacci 的代码改写为如下形式：
计算第 50 个 fibonacci 值只需要 99 次，执行时间为 0.06 秒，只有递归版本执行时间（546.41 秒）的万分之一，使用的内存（rss 值 20111360）只有递归版本（rss 值为 36757504）的 54%。
值得注意的是：这里闭包使用的<code>memo</code>对象有可能造成内存泄露。
如果需要处理多个参数，需要把缓存的内容变成多维数据结构，或者把多个参数结合起来作为一个索引。
例如：
上面执行了两次<code>fibonacci</code>函数，假设执行多次：
可以看到内存的增长也是有限的，并且最终控制在了<code>22097920</code>这个值。下面是另一种处理多个参数的情况（将多个参数组成一个索引）：
与上面版本相比，内存有所增加，速度有所下降：
但是需要注意的是，并不是所有函数都可以自动<code>memoization</code>，只有<code>referential transparency</code>（引用透明）的函数可以。所谓<code>referential transparency</code>的函数是指：函数的输出完全由其输入决定，且不会有副作用的函数。下面的函数就是一个反例：
对比自动<code>memoization</code>前后的两个版本：
自动<code>memoization</code>处理后的版本有所提高，但相比手动完全<code>memoization</code>的版本效率还是差了很多。
上面自动<code>memoization</code>的结果并不理想，可以参考<code>underscore</code>和<code>lodash</code>的<code>memoize</code>来做优化。
对比结果：
可以看到<code>lodash</code>的<code>memoize</code>方法减少了一半执行时间。进一步优化：
科普下：<code>function arity</code>指的是一个函数接受的参数个数，这是一个被废弃的属性，现在应使用<code>function.prototype.length</code>。 <a href="https://stackoverflow.com/questions/4848149/get-a-functions-arity" target="_blank">https://stackoverflow.com/questions/4848149/get-a-functions-arity</a>
zakas 的版本更加快，甚至比我们将<code>fibonacci</code>手动<code>memoization</code>的版本还快：
但是上面这些函数都存在问题，如果输入数目过大，会引发调用栈超过限制异常：<code>rangeerror: maximum call stack size exceeded</code>。
一种解决的方法就是将递归（<code>recursion</code>）修改为迭代（<code>iteration</code>）。例如下面这样的归并排序算法：
而上面的排序函数在经过<code>memoization</code>后虽然不会抛出<code>rangeerror: maximum call stack size exceeded</code>的异常，但是在极端情况下也会因为内存不够分配导致失败：
解决<code>rangeerror: maximum call stack size exceeded</code>异常的一种方法是将递归的代码改写为迭代的代码，例如<code>fibonacci</code>的递归式写法为：
在 javascript 中我们是通过函数的形式来是实现函数的<code>memoization</code>，在 python 中还可以用另一种被称为<code>decorator</code>的形式：
<a href="https://www.sitepoint.com/implementing-memoization-in-javascript/" target="_blank">https://www.sitepoint.com/implementing-memoization-in-javascript/</a>
<a href="https://addyosmani.com/blog/faster-javascript-memoization/" target="_blank">https://addyosmani.com/blog/faster-javascript-memoization/</a>
<a href="http://unscriptable.com/index.php/2009/05/01/a-better-javascript-memoizer/" target="_blank">http://unscriptable.com/index.php/2009/05/01/a-better-javascript-memoizer/</a>
<a href="http://www.nczonline.net/blog/2009/01/27/speed-up-your-javascript-part-3/" target="_blank">http://www.nczonline.net/blog/2009/01/27/speed-up-your-javascript-part-3/</a>
<a href="http://books.google.co.uk/books?id=pxa2bby0oq0c&pg=pa44&lpg=pa44&dq=crockford+memoization&source=bl&ots=himnm6r1ih&sig=lrdt9sk4f4yq-xq-tltx4splkuk&hl=en&ei=c-hytvaieofb8qo21nn_dq&sa=x&oi=book_result&ct=result&resnum=4&ved=0cdmq6aewaw#v=onepage&q&f=false" target="_blank">http://books.google.co.uk/books?id=pxa2bby0oq0c&pg=pa44&lpg=pa44&dq=crockford+memoization&source=bl&ots=himnm6r1ih&sig=lrdt9sk4f4yq-xq-tltx4splkuk&hl=en&ei=c-hytvaieofb8qo21nn_dq&sa=x&oi=book_result&ct=result&resnum=4&ved=0cdmq6aewaw#v=onepage&q&f=false</a>
<a href="http://my.safaribooksonline.com/book/programming/javascript/9781449399115/functions/function_propertiesma_memoization_patter#x2ludgvybmfsx0zsyxnoumvhzgvyp3htbglkptk3ode0ndkzotkxmtuvnzy=" target="_blank">http://my.safaribooksonline.com/book/programming/javascript/9781449399115/functions/function_propertiesma_memoization_patter#x2ludgvybmfsx0zsyxnoumvhzgvyp3htbglkptk3ode0ndkzotkxmtuvnzy=</a>
memoize function javascript | npm memoize | lodash memoize | underscore memoize
<a href="http://unscriptable.com/2009/05/01/a-better-javascript-memoizer/" target="_blank">http://unscriptable.com/2009/05/01/a-better-javascript-memoizer/</a>
programming optimization techniques
<a href="http://blog.stevenlevithan.com/archives/timed-memoization" target="_blank">http://blog.stevenlevithan.com/archives/timed-memoization</a>
<a href="https://github.com/addyosmani/memoize.js" target="_blank">https://github.com/addyosmani/memoize.js</a>
<a href="https://en.wikipedia.org/wiki/arity" target="_blank">function arity</a>
<a href="https://philogb.github.io/blog/2008/09/05/memoization-in-javascript/" target="_blank">https://philogb.github.io/blog/2008/09/05/memoization-in-javascript/</a>
<a href="https://stackoverflow.com/questions/6184869/what-is-difference-between-memoization-and-dynamic-programming" target="_blank">https://stackoverflow.com/questions/6184869/what-is-difference-between-memoization-and-dynamic-programming</a>
<a href="http://www.python-course.eu/python3_memoization.php" target="_blank">http://www.python-course.eu/python3_memoization.php</a>
<a href="https://en.wikipedia.org/wiki/iteration" target="_blank">https://en.wikipedia.org/wiki/iteration</a>
<a href="https://en.wikipedia.org/wiki/iterated_function" target="_blank">https://en.wikipedia.org/wiki/iterated_function</a>
<a href="https://www.ics.uci.edu/~eppstein/161/960109.html" target="_blank">https://www.ics.uci.edu/~eppstein/161/960109.html</a>
<a href="https://classes.soe.ucsc.edu/cmpe012/summer09/labs/lab8-recursion-vs-iteration/" target="_blank">https://classes.soe.ucsc.edu/cmpe012/summer09/labs/lab8-recursion-vs-iteration/</a>
google: iterative merge sort
google: maximum call stack size exceeded | avoid maximum recursive
<a href="http://www.python-course.eu/python3_decorators.php" target="_blank">http://www.python-course.eu/python3_decorators.php</a>
<a href="https://www.cs.cornell.edu/courses/cs3110/2011sp/lectures/lec22-memoization/memo.htm" target="_blank">https://www.cs.cornell.edu/courses/cs3110/2011sp/lectures/lec22-memoization/memo.htm</a>
dynamic programming
来自：http://taobaofed.org/blog/2016/07/14/performance-optimization-memoization/
作者：云翮