遞歸是拖慢腳本運(yùn)行速度的大敵之一。太多的遞歸會(huì)讓瀏覽器變得越來越慢直到死掉或者莫名其妙的突然自動(dòng)退出。
我們可以使用memoization技術(shù)來替代函數(shù)中太多的遞歸調(diào)用，通過封裝一個(gè)Memoization函數(shù)去緩存之前運(yùn)算結(jié)果，從而能避免無謂的運(yùn)算避免重復(fù)工作，將執(zhí)行過的運(yùn)算或操作，緩存起來，如果后續(xù)有相同的操作可直接從緩存中查找，沒有則進(jìn)行遞歸，可大大減少遞歸的工作量，提高性能。
一、簡(jiǎn)單實(shí)現(xiàn)
通過 Memoization 的定義和原理，我們就可以初步實(shí)現(xiàn) Memoization
function memoizer(fundamental, cache){
cache = cache || {}
var shell = function(arg){
if (! (arg in cache)){
cache[arg] = fundamental(shell, arg)
}
return cache[arg];
};
return shell;
}
函數(shù)緩存其實(shí)就是利用閉包，將函數(shù)參數(shù)作為存儲(chǔ)對(duì)象的鍵（key），函數(shù)結(jié)果作為存儲(chǔ)對(duì)象的 value 值。原有函數(shù)被設(shè)置為第一個(gè)參數(shù)，第二個(gè)參數(shù)是緩存對(duì)象，為可選參數(shù)，因?yàn)椴⒉皇撬械倪f歸函數(shù)都包含初始信息。在函數(shù)內(nèi)部，使用一個(gè)對(duì)象來緩存函數(shù)值，在shell函數(shù)里，我使用了in操作符來判斷參數(shù)是否已經(jīng)包含在緩存里。這種寫法比測(cè)試類型不是undefined更加安全，因?yàn)閡ndefined是一個(gè)有效的返回值。
二、使用場(chǎng)景 計(jì)算斐波那契數(shù)列
斐波那契數(shù)列的特點(diǎn)是后一個(gè)數(shù)等于前面兩個(gè)數(shù)的和
指的是這樣一個(gè)數(shù)列：1、1、2、3、5、8、13、21、34、……在數(shù)學(xué)上，斐波那契數(shù)列以如下被以遞推的方法定義：F(0)=0，F(xiàn)(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）
var count = 0;
var fibonacci = function(n) {
count++;
return n < 2 ? n : fibonacci(n - 2) + fibonacci(n - 1);
}
fibonacci(40)
// 102334155
console.log(count);
//331,160,280 !!! 由于每有緩存結(jié)果，每次都需要進(jìn)行函數(shù)調(diào)用
這里可以看到 在使用遞歸函數(shù)計(jì)算的時(shí)候，沒有做結(jié)果緩存，每次計(jì)算都要重新調(diào)用函數(shù)計(jì)算。那我們就犧牲一小部分內(nèi)存，用來緩存每次計(jì)算的值，就可以減少函數(shù)的調(diào)用
var count = 0
fibonacci =
memoizer(function (recur, n) {
count++
return recur(n - 1) + recur(n - 2);
}, {"0":0, "1":1});
fibonacci(40)
console.log(count);
// 39 可以看到最后通過 memoize 函數(shù)記憶，使得函數(shù)執(zhí)行次數(shù)只需要39次，大大優(yōu)化了函數(shù)執(zhí)行計(jì)算的性能消耗，
三、總結(jié)
函數(shù)記憶（memoization）將函數(shù)的參數(shù)和結(jié)果值，保存在對(duì)象當(dāng)中，用一部分的內(nèi)存開銷來提高程序計(jì)算的性能，常用在遞歸和重復(fù)運(yùn)算較多的場(chǎng)景中，對(duì)于那些有著嚴(yán)格定義的結(jié)果集的遞歸算法來說，提升運(yùn)行效果比較顯著。
參考文獻(xiàn)
https://humanwhocodes.com/blog/2009/01/20/speed-up-your-javascript-part-2/
https://humanwhocodes.com/blog/2009/01/20/speed-up-your-javascript-part-3/
