JS遞回函數精講

遞回就是呼叫自身的一種程式設計技巧，在程式設計中應用廣泛。遞回函數就是函數對自身的呼叫，是迴圈運算的一種演算法模式。

JS遞回運算

遞回必須由以下兩部分組成。

• 遞回呼叫的過程。
• 遞回終止的條件。

在沒有限制的情況下，遞回運算會無終止地自身呼叫。因此，在遞回運算中要結合 if 語句進行控制，只有在某個條件成立時才允許執行遞回，否則不允許呼叫自身。

遞回運算的應用場景如下。

1) 求解遞回問題

主要解決一些數學運算，如階乘函數、冪函數和斐波那契數列。

下面範例使用遞迴運算來設計階乘函數。

var f = function (x) {
    if (x < 2) return 1;  //遞回終止條件
    else return x * f(x - 1);  //遞回呼叫過程
}
console.log(f(5));  //返回5的階乘值為120

在這個過程中，利用分支結構把遞迴結束條件和遞回運算分開。

2) 解析遞回型資料結構

很多資料結構都具有遞回特性，如 DOM 文件樹、多級目錄結構、多級導航選單、家族譜系結構等。對於這類資料結構，使用遞迴演算法進行遍歷比較合適。

下面使用遞迴運算計算指定節點內所包含的全部節點數。

function f (n) {  //統計指定節點及其所有子節點的元素個數
    var l = 0;  //初始化計數變數
    if (n.nodeType == 1) l ++;  //如果是元素節點，則計數
    var child = n.childNodes;  //獲取子節點集合
    for (var i = 0; i < child.length; i ++) {  //遍歷所有子節點
        l += f (child[i]);  //遞回運算，統計當前節點下所有子節點數
    }
    return l;  //返回節點數
}
window.onload = function () {
    console.log(f(document.body));  //返回2，即body和script兩個節點
}

3) 適合使用遞迴法解決問題

有些問題最適合採用遞迴的方法求解，如漢諾塔問題。

下面使用遞迴運算設計漢諾塔演示函數。引數說明：n 表示金片數；a、b、c 表示柱子，注意排列順序。返回說明：當指定金片數，以及柱子名稱，將輸出整個移動的過程。

function f (n,a,b,c) {
    if (n == 1) {  //當為一片時，直接移動
        document.write("移動 【盤子" + n + "】從【" + a + "柱】到【" + c + "柱】<br>");
    } else {
        f (n - 1, a, c, b);  //調整引數順序。讓引數a移給b
        document.write("移動 【盤子" + n + "】從【" + a + "柱】到【" + c + "柱】<br>");
        f(n - 1, b, a, c);  //調整順序，讓引數b移給c
    }
}
f (3, "A", "B", "C");  //呼叫漢諾塔函數

執行結果如下：

移動【盤子1】從【A柱】到【C柱】
移動【盤子2】從【A柱】到【B柱】
移動【盤子1】從【C柱】到【B柱】
移動【盤子3】從【A柱】到【C柱】
移動【盤子1】從【B柱】到【A柱】
移動【盤子2】從【B柱】到【C柱】
移動【盤子1】從【A柱】到【C柱】

JS尾遞回

尾遞回是遞迴的一種優化演算法，遞回函數執行時會形成一個呼叫函數，當子一層的函數程式碼執行完成之後，父一層的函數才會銷毀呼叫記錄，這樣就形成了呼叫棧，棧的疊加可能會產生記憶體溢位。而尾遞回函數的每子一層函數不再需要使用父一層的函數執行完畢就會銷毀棧記錄，避免了記憶體溢位，節省了記憶體空間。

範例

下面是階乘的一種普通線性遞回運算。

function f (n) {
    return (n == 1) ? 1 : n * f (n - 1);
}
console.log(f(5));  //120

使用尾遞迴演算法後，則可以使用以下方法。

function f (n, a) {
    return (n == 1) ? a : f (n - 1, a * n);
}
console.log(f(5, 1));  //120

當 n=5 時，線性遞回的遞迴過程如下。

f (5) = {5 * f(4)}
      = {5 * {4 * f(3) }}
      = {5 * {4 * {3 * f(2)}}}
      = {5 * {4 * {3 * {2 * f(1)}}}}
      = {5 * {4 * {3 * {2 *1}}}}
      = {5 * {4 * {3 *2}}}
      = {5 * {4 * 6}
      = {5 * 24}
      = 120

而尾遞回的遞迴過程如下。

f (5) = f (5, 1)
      = f (4, 5)
      = f (3, 20)
      = f (2, 60)
      = f (1, 120)
      = 120

很容易看出，普通遞回比尾遞回更加消耗資源，每次重複的過程呼叫都使得呼叫鏈條不斷加長，系統不得不使用棧進行資料儲存和恢復，而尾遞回就不存在這樣的問題，因為它的狀態完全由變數 n 和 a 儲存。

從理論上分析，尾遞回也是遞迴的一種型別，不過其演算法具有疊代演算法的特徵。上面的階乘尾遞回可以改寫為下面的疊代迴圈。

var n = 5;
var w = 1;
for (var i = 1; i <= 5; i ++) {
    w = w * i;
}
console.log(w);

尾遞回由於直接返回值，不需要儲存臨時變數，所以效能不會產生線性增加，同時 JavaScript 引擎會將尾遞迴形式優化成非遞迴形式。

JS遞回與疊代的區別

遞回與疊代都是迴圈的一種，簡單比較如下：

• 在程式結構上，遞回是重複呼叫函數自身實現迴圈，疊代是通過迴圈結構實現。
• 在結束方式上，遞回當滿足終止條件時會逐層返回再結束，疊代直接使用計數器結束回圈。
• 在執行效率上，疊代的效率明顯高於遞回。因為遞回需要佔用大量系統資源，如果遞迴深度很大，系統資源可能會不夠用。
• 在程式設計實現上，遞回可以很方便的把數學公式轉換為程式，易理解，易程式設計。疊代雖然效率高，不需要系統開銷，但不容易理解，編寫複雜問題時比較麻煩。

在實際應用中，能不用遞迴就不用遞迴，遞迴都可以用疊代來代替。

範例

下面以斐波那契數列為例說明。

斐波那契數列就是一組數位，從第 3 項開始，每一項都等於前兩項之和。例如：
1、1、2、3、5、8、13、21、34、55、89、144、233、377、610、987、1597、2584、4181。

使用遞回函數計算斐波那契數列，其中最前面的兩個數位是 0 和 1。

var fibonacci = function (n) {
    return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
};
console.log(fibonacci(19));  //4181

嘗試傳入更大的數位，會發現遞回運算的次數加倍遞增，速度加倍遞減，返回值加倍放大。如果嘗試計算 100 的斐波那契數列，則瀏覽器基本癱瘓。

下面使用疊代演算法來設計斐波那契數列，程式碼如下（測試瞬間完成，基本沒有任何延遲）：

var fibonacci = function (n) {
    var a = [0, 1];  //記錄數列的陣列，第1、2個元素值確定
    for (var i = 2; i <= n; i ++) {  //從第 3 個數位開始迴圈
        a.push(a[i - 2] + a[i - 1]);  //計算新數位，並推入陣列
    }
    return a[n];  //返回指定位數的數列結果
};
console.log(fibonacci(19));  //4181

下面使用 JavaScript 高階函數進行設計，把斐波那契數列函數封裝在一個閉包體內，然後返回斐波那契數列函數。在閉包內使用 memo 陣列持久記錄每級斐波那契數列函數的求值結果。在下一次求值之前，先在陣列中檢索是否存在同級（數列的個數，陣列的下標位置）計算結果，如果存在，則直接返回，避免重複行計算；如果沒有找到結果，則呼叫斐波那契數列函數進行求和。實現程式碼如下：

var finbonacci = (function () {
    var memo = [0, 1];
    var fib = function (n) {
        var result = memo[n];
        if (typeof result !== 'number') {
            result = fib(n - 1) + fib(n - 2);
            memo[n] = result;
        }
        return result;
    };
    return fib;
}());
console.log(finbonacci(100));  //354224848179262000000

在瀏覽器中測試，可以看到，求 100 的斐波那契數列基本上不會延遲。