JavaScript中關於防止遞歸棧溢位錯誤的解析

真是大神級的人物, 必須膜拜. 虛心學習

尾遞歸

函數呼叫自身，稱為遞歸。如果尾調用自身，就稱為尾遞歸。

遞歸非常耗費內存，因為需要同時保存成千上萬個呼叫幀，很容易發生「堆疊溢出」錯誤（stack overflow）。但對於尾遞歸來說，由於只存在一個呼叫幀，所以永遠不會發生「棧溢位」錯誤。

範例1

function factorial(n) {
  if (n === 1) return 1;  return n * factorial(n - 1);
}

factorial(5) // 120

上面程式碼是一個階乘函數，計算n的階乘，最多需要保存n個呼叫記錄，複雜度 O(n) 。

如果改寫成尾遞歸，只保留一個呼叫記錄，複雜度O(1)

function factorial(n, total) {
  if (n === 1) return total;  return factorial(n - 1, n * total);
}

factorial(5, 1) // 120

例子2

還有一個比較有名的例子，就是計算Fibonacci數列，也能充分說明尾遞歸最佳化的重要性。

非尾遞歸的 Fibonacci 數列實作如下。

function Fibonacci (n) {
  if ( n <= 1 ) {return 1};  return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Fibonacci(10) // 89Fibonacci(100) // 堆栈溢出, 亲测页面直接卡死, cpu: i7-4720Fibonacci(500) // 堆栈溢出

優化後

function Fibonacci2 (n , ac1 = 1 , ac2 = 1) {
  if( n <= 1 ) {return ac2};  return Fibonacci2 (n - 1, ac2, ac1 + ac2);
}

Fibonacci2(100) // 573147844013817200000Fibonacci2(1000) // 7.0330367711422765e+208 非一般的速度Fibonacci2(10000) // Infinity

尾遞歸優化

尾遞歸優化只在嚴格模式下生效，那麼正常模式下，或者那些不支援該功能的環境中，有沒有辦法也使用尾遞歸優化呢？回答是可以的，就是自己實現尾遞歸優化。

它的原理非常簡單。尾遞歸之所以需要最佳化，原因是呼叫棧太多，造成溢出，那麼只要減少呼叫棧，就不會溢出。怎麼做可以減少呼叫棧呢？就是採用「循環」換掉「遞迴」。

下面是一個正常的遞歸函數。

function sum(x, y) {
  if (y > 0) {    return sum(x + 1, y - 1);
  } else {    return x;
  }
}sum(1, 100000)// Uncaught RangeError: Maximum call stack size exceeded(…)

上面程式碼中，sum是一個遞迴函數，參數x是需要累加的值，參數y控制遞迴次數。一旦指定sum遞歸100000次，就會報錯，提示超出呼叫堆疊的最大次數。

彈翻床函數（trampoline）可以將遞迴執行轉為循環執行。

function trampoline(f) {
  while (f && f instanceof Function) {
    f = f();
  }  return f;
}

上面就是彈跳床函數的一個實現，它接受一個函數f作為參數。只要f執行後回傳一個函數，就繼續執行。請注意，這裡是傳回一個函數，然後執行函數，而不是函數裡面呼叫函數，這樣就避免了遞歸執行，從而消除了呼叫堆疊過大的問題。

然後，要做的就是將原來的遞歸函數，改寫為每一步返回另一個函數。

function sum(x, y) {
  if (y > 0) {    return sum.bind(null, x + 1, y - 1);
  } else {    return x;
  }
}

上面程式碼中，sum函數的每次執行，都會傳回自身的另一個版本。

現在，使用彈翻床函數執行sum，就不會發生呼叫堆疊溢位。

trampoline(sum(1, 100000))// 100001

彈翻床函數並不是真正的尾遞歸最佳化，下面的實作才是。

重點來了, 老鐵們

function tco(f) {
  var value;  var active = false;  var accumulated = [];  return function accumulator() {
    accumulated.push(arguments);//每次将参数传入. 例如, 1 100000
    if (!active) {
      active = true;      
      while (accumulated.length) {//出循环条件, 当最后一次返回一个数字而不是一个函数时, accmulated已经被shift(), 所以出循环
        value = f.apply(this, accumulated.shift());//调用累加函数, 传入每次更改后的参数, 并执行
      }
      active = false;      
      return value;
    }
  };
}var sum = tco(function(x, y) {
  if (y > 0) {    
  return sum(x + 1, y - 1)//重点在这里, 每次递归返回真正函数其实还是accumulator函数
  }  
  else {    
  return x
  }
});

sum(1, 100000);//实际上现在sum函数就是accumulator函数// 100001

上面程式碼中，tco函數是尾遞歸最佳化的實現，它的奧妙就在於狀態變數active。預設情況下，這個變數是不啟動的。一旦進入尾遞歸優化的過程，這個變數就啟動了。然後，每一輪遞歸sum回傳的都是undefined，所以就避免了遞歸執行；而accumulated數組存放每一輪sum執行的參數，總是有值的，這就保證了accumulator函數內部的while循環總是會執行。這樣就很巧妙地將“遞歸”改成了“循環”，而後一輪的參數會取代前一輪的參數，保證了調用棧只有一層。

以上是JavaScript中關於防止遞歸棧溢位錯誤的解析的詳細內容。更多資訊請關注PHP中文網其他相關文章！