11.1 遞歸

遞歸是一種解決問題的方法，它解決問題的各個小部分，直到解決最初的大問題。遞歸通常涉及函數調用自身。

遞歸函數是像下面這樣能夠直接調用自身的方法或函數：

function recursiveFunction(someParam){
  recursiveFunction(someParam);
};

  

能夠像下面這樣間接調用自身的函數，也是遞歸函數：

function recursiveFunction1(someParam){
  recursiveFunction2(someParam);
};

function recursiveFunction2(someParam){
  recursiveFunction1(someParam);
};

  

假設現在必須要執行recursiveFunction，結果是什麼？單單就上述情況而言，它會一直執行下去。因此，每個遞歸函數都必須要有邊界條件，即一個不再遞歸調用的條件（停止點），以防止無限遞歸。

11.1.1　JavaScript調用棧大小的限制

如果忘記加上用以停止函數遞歸調用的邊界條件，會發生什麼呢？遞歸並不會無限地執行下去；瀏覽器會拋出錯誤，也就是所謂的棧溢出錯誤（stack overflow error）。

每個瀏覽器都有自己的上限，可用以下代碼測試：

var i = 0;

function recursiveFn  {
  i++;
  recursiveFn;
}

try {
  recursiveFn;
} catch (ex) {
  alert('i = ' + i + ' error: ' + ex);
}

  

在Chrome v37中，這個函數執行了20 955次，而後瀏覽器拋出錯誤RangeError: Maximum call stack size exceeded（超限錯誤：超過最大調用棧大小）。在Firefox v27中，函數執行了343 429次，然後瀏覽器拋出錯誤 InternalError: too much recursion（內部錯誤：遞歸次數過多）。

　根據操作系統和瀏覽器的不同，具體數值會所有不同，但區別不大。

ECMAScript 6有尾調用優化（tail call optimization）。如果函數內最後一個操作是調用函數（就像示例中加粗的那行），會通過「跳轉指令」（jump） 而不是「子程序調用」（subroutine call）來控制。也就是說，在ECMAScript 6中，這裡的代碼可以一直執行下去。所以，具有停止遞歸的邊界條件非常重要。

　有關尾調用優化的更多相關信息，請訪問http://goo.gl/ZdTZzg。

11.1.2　斐波那契數列

回到第10章提到的斐波那契問題。斐波那契數列的定義如下：

• 1和2的斐波那契數是 1；

• n（n>2）的斐波那契數是(n-1)的斐波那契數加上(n-2)的斐波那契數。

那麼，讓我們開始實現斐波那契函數：

function fibonacci(num){
  if (num === 1 || num === 2){ //{1}
    return 1;
  }
}

  

邊界條件是已知的，1和2的斐波那契數（行{1}）是1。現在，讓我們完成斐波那契函數的實現：

function fibonacci(num){
  if (num === 1 || num === 2){
    return 1;
  }
  return fibonacci(num - 1) + fibonacci(num - 2);
}

  

我們已經知道，當n大於2時，Fibonacci(n)等於Fibonacci(n-1)+Fibonacci(n-2)。

現在，斐波那契函數實現完畢。讓我們試著找出6的斐波那契數，其會產生如下函數調用：

我們也可以用非遞歸的方式實現斐波那契函數：

function fib(num){
  var n1 = 1,
    n2 = 1,
    n = 1;
  for (var i = 3; i<=num; i++){
    n = n1 + n2;
    n1 = n2;
    n2 = n;
  }
  return n;
}

  

為何用遞歸呢？更快嗎？遞歸並不比普通版本更快，反倒更慢。但要知道，遞歸更容易理解，並且它所需的代碼量更少。

　在ECMAScript 6中，因為尾調用優化的緣故，遞歸並不會更慢。但是在其他語言中，遞歸通常更慢。

所以，我們用遞歸，通常是因為它更容易解決問題。