本文實例講述了JS尾遞歸的實現(xiàn)方法及代碼優(yōu)化技巧。分享給大家供大家參考，具體如下：

在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的時候，我們都知道所有的遞歸都是可以優(yōu)化成棧+循環(huán)的。

對于特定的遞歸函數(shù)，一般我們都是手動對它們進行優(yōu)化的。

在學(xué)習(xí)scala的時候，接觸到尾遞歸的概念。我們只要將遞歸寫成尾遞歸方式，編譯器會自動幫助我們優(yōu)化。

ps:并不是所有的遞歸都可以改寫成尾遞歸

在js中，尾遞歸通常會被解釋器優(yōu)化。然而，并不是所有的js解釋器都支持尾遞歸優(yōu)化。

對于不支持尾遞歸優(yōu)化的環(huán)境，我們需要手動將遞歸優(yōu)化成棧+循環(huán)。

這里實現(xiàn)了一個通用的方法，將尾遞歸優(yōu)化成棧+循環(huán)。

代碼摘自阮一峰的《ECMAScript入門》這本書。

具體代碼如下

function tco(f) {
  var value;
  var active = false;
  var accumulated = [];
  return function accumulator() {
    accumulated.push(arguments);
    if(!active) {
      active = true;
      while(accumulated.length) {
        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);
  } else {
    return x;
  }
});
let res = sum(1, 5)
console.info(res);

這段代碼非常精妙！

分析

已知，任何遞歸可以寫成循環(huán)+棧。

實現(xiàn)將任何尾遞歸轉(zhuǎn)換成循環(huán)+棧執(zhí)行而不需要針對每個尾遞歸函數(shù)寫一個實現(xiàn)版本的思路。

困難在于，任何尾遞歸，通用實現(xiàn)。而不是針對某一個遞歸函數(shù)。

要點：

棧中保存的數(shù)據(jù)，正是遞歸函數(shù)的參數(shù)。

通用實現(xiàn)，那就必須依賴原來的遞歸函數(shù)，循環(huán)的終止條件，正是遞歸的結(jié)束條件。

要將遞歸函數(shù)的參數(shù)入棧，而不修改原來的遞歸函數(shù)，就必須用一個函數(shù)代替遞歸函數(shù)被調(diào)用，從而取得函數(shù)入?yún)ⅰ?/p>

遞歸函數(shù)的終止條件，每一個遞歸函數(shù)都不一樣，但是如果遞歸函數(shù)沒有被再次調(diào)用，說明已達到終止條件。即終止條件和遞歸函數(shù)的調(diào)用有關(guān)聯(lián)。而遞歸函數(shù)每次調(diào)用，都會將參數(shù)入棧。所以可以根據(jù)棧中是否有元素，推斷是否達到終止條件。

更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)學(xué)運算用法總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯誤與調(diào)試技巧總結(jié)》

希望本文所述對大家JavaScript程序設(shè)計有所幫助。

最新評論