DIV CSS 佈局教程網

JavaScript 遞迴入門:從累加一路談到呼叫堆疊
編輯:關於JavaScript     

題目很經典:從 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));

遞迴的兩個必要條件

  1. 終止條件(base case):必須有一個明確的出口,否則會永遠呼叫下去。
  2. 向終止條件收斂:每次呼叫都要讓問題規模變小,例如 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 這種任務,用迴圈寫不僅更快,也更省記憶體。遞迴該出手的場合,是資料本身就是遞迴結構的時候。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved