遞歸是拖慢腳本運(yùn)行速度的大敵之一。太多的遞歸會(huì)讓瀏覽器變得越來(lái)越慢直到死掉或者莫名其妙的突然自動(dòng)退出睛廊。
我們可以使用memoization技術(shù)來(lái)替代函數(shù)中太多的遞歸調(diào)用，通過(guò)封裝一個(gè)Memoization函數(shù)去緩存之前運(yùn)算結(jié)果祟滴，從而能避免無(wú)謂的運(yùn)算避免重復(fù)工作刊懈，將執(zhí)行過(guò)的運(yùn)算或操作，緩存起來(lái)捷凄，如果后續(xù)有相同的操作可直接從緩存中查找忱详，沒(méi)有則進(jìn)行遞歸，可大大減少遞歸的工作量跺涤，提高性能匈睁。
一、簡(jiǎn)單實(shí)現(xiàn)
通過(guò) 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ì)象來(lái)緩存函數(shù)值阅虫，在shell函數(shù)里演闭，我使用了in操作符來(lái)判斷參數(shù)是否已經(jīng)包含在緩存里。這種寫(xiě)法比測(cè)試類(lèi)型不是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í)候陨闹，沒(méi)有做結(jié)果緩存楞捂，每次計(jì)算都要重新調(diào)用函數(shù)計(jì)算。那我們就犧牲一小部分內(nèi)存趋厉，用來(lá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 可以看到最后通過(guò) memoize 函數(shù)記憶，使得函數(shù)執(zhí)行次數(shù)只需要39次觅廓，大大優(yōu)化了函數(shù)執(zhí)行計(jì)算的性能消耗鼻忠，
三、總結(jié)
函數(shù)記憶（memoization）將函數(shù)的參數(shù)和結(jié)果值杈绸，保存在對(duì)象當(dāng)中帖蔓，用一部分的內(nèi)存開(kāi)銷(xiāo)來(lái)提高程序計(jì)算的性能，常用在遞歸和重復(fù)運(yùn)算較多的場(chǎng)景中瞳脓，對(duì)于那些有著嚴(yán)格定義的結(jié)果集的遞歸算法來(lái)說(shuō)塑娇，提升運(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/
