題目很經典:從 1 累加到 100 是多少?用遞迴寫一次,就能把觀念釐清。
function run() {
var sum = 0;
for (var i = 1; i <= 100; i++) {
sum = sum + i;
}
console.log(sum);
}
var testCase = {
sum: 0,
run: function (n) {
if (n >= 100) {
return 100;
} else {
sum = n + testCase.run(n + 1);
return sum;
}
}
};
console.log(testCase.run(1));
網路上這類範例一搜就有一大堆,下面這個寫法與它等價,但更適合拿來理解遞迴的本質:
console.log((function (n) {
var sum = 0;
if (n <= 1) {
return 1;
} else {
sum = arguments.callee(n - 1) + n;
return sum;
}
})(100));
這裡的 arguments.callee 指的是「目前這個匿名函式本身」,讓我們不必先幫函式取名字就能自我呼叫。不過要注意,arguments.callee 在 ES5 的 strict mode 下已被禁用,實務上應該改為具名函式表示式:
var fn = function fact(n) {
return n <= 1 ? 1 : fact(n - 1) + n;
};
console.log(fn(100));
n 往 n - 1 走。少了任何一個,就會撞上行疊上限,瀏覽器拋出 Maximum call stack size exceeded。
值得指出的是,上面那個 testCase 的版本把 sum 放在物件上當共享狀態,每次遞迴都改寫它,同時又回傳值往上疊加,等於把同一件事計算了兩遍。改成純函式會乾淨很多:
function sumTo(n) {
if (n <= 1) return 1;
return n + sumTo(n - 1);
}
console.log(sumTo(100)); // 5050
沒有外部狀態、沒有副作用,讀起來就是數學定義本身。這正是遞迴的價值所在:有些問題(樹狀走訪、巢狀結構展開、分治法)用遞迴表達的清晰度,遠非迴圈可比。
以上都屬於線性遞迴,作為入門夠用,但就效率而言並不理想:每一層呼叫都要佔用一個堆疊框,且 JavaScript 目前主流引擎尚未普遍實作尾端呼叫最佳化。累加 1 到 100 這種任務,用迴圈寫不僅更快,也更省記憶體。遞迴該出手的場合,是資料本身就是遞迴結構的時候。