遞迴優雅,但代價是重複計算。經典的 Fibonacci 就是最容易被數字規模壓垮的例子。
var fibonacci = function (n) {
return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
};
這段程式看起來乾淨俐落,但只要 n 大一點,瀏覽器就會卡死。原因是它在計算過程中會大量重複拜訪同一個節點——fibonacci(30) 內部其實把 fibonacci(28) 算了兩次、fibonacci(27) 算了三次,越往下指數級膨脹。
JavaScript 強大的陣列與函式閉包,讓「記憶已計算的結果」變得非常容易。下面這個小小的通用記憶器,任何遞迴函式都能套用:
var memoizer = function (memo, fundamental) {
var shell = function (n) {
var result = memo[n];
if (typeof result !== 'number') {
result = fundamental(shell, n);
memo[n] = result;
}
return result;
};
return shell;
};
兩個參數分工明確:memo 是初始的記憶表(已知答案),fundamental 是真正負責計算的基礎函式。而 shell 是包在外面的守門人:先查 memo,命中就直接回傳;沒命中才呼叫 fundamental 計算,算完立刻寫回 memo。
最妙的是它把 shell 自己當參數傳給 fundamental,於是基礎函式內部的遞迴呼叫也會經過同一道守門關卡——記憶因此能一路貫穿整棵遞迴樹。
// 傳入初始已知項 [F(0), F(1)] = [0, 1]
var fibonacci = memoizer([0, 1], function (shell, n) {
return shell(n - 1) + shell(n - 2);
});
// 同理,階乘的初始項是 [0!, 1!] = [1, 1]
var factorial = memoizer([1, 1], function (shell, n) {
return n * shell(n - 1);
});
呼叫方式與原本的遞迴幾乎相同,但速度從指數級降為線性級——原本算不完的 n,現在瞬間完成。
它把「怎麼算」與「算過的別再算」這兩件關注點徹底分離。基礎函式只專心寫遞迴關係式,效能優化完全交給外層的 memoizer 處理,兩邊都不必為對方妥協。這正是高階函式的典型價值。
有兩個實作上的限制值得注意:其一,typeof result !== 'number' 這個判斷意味著它只適用於回傳數值的函式,若結果可能是物件或 NaN 就會誤判;其二,記憶表會無限成長,長時間運行的應用可能需要加上容量上限或改用 WeakMap 之類的機制。
ES6 之後也可以直接用 Map 實作同樣的效果,語意比陣列更清楚,也不受索引必須為整數的限制。