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

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

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

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

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

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

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

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

代碼摘自阮一峰的《ECMAScript入門(mén)》這本書(shū)。

具體代碼如下

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);

這段代碼非常精妙！

分析

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

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

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

要點(diǎn)：

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

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

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

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

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

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

最新評(píng)論