一. 什么是尾調(diào)用？

尾調(diào)用（Tail Call）是函數(shù)式編程的一個(gè)重要概念，本身非常簡(jiǎn)單，一句話就能說(shuō)清楚，就是指某個(gè)函數(shù)的最后一步是調(diào)用另一個(gè)函數(shù)。

function f(x) {
    return g(x);
}

上面代碼中，函數(shù)f的最后一步是調(diào)用函數(shù)g，這就叫尾調(diào)用。

以下三種情況，都不屬于尾調(diào)用。

// 情況一
function f(x){
  let y = g(x);
  return y;
}

// 情況二
function f(x){
  return g(x) + 1;
}

// 情況三
function f(x){
  g(x);
}

• 情況一是調(diào)用函數(shù)g之后，還有賦值操作，所以不屬于尾調(diào)用，即使語(yǔ)義完全一樣。
• 情況二也屬于調(diào)用后還有操作，即便是寫在一行內(nèi)。
• 情況三也屬于調(diào)用后還有操作，函數(shù)內(nèi)沒(méi)有顯示的寫 return 語(yǔ)句時(shí)，會(huì)隱式添加 return undefined 。情況三等同于以下代碼。

function f(x) {
    g(x);
  return undefined;
}

尾調(diào)用不一定出現(xiàn)在函數(shù)尾部，只要是最后一步操作即可。

function f(x) {
  if (x > 0) {
    return m(x)
  }
  return n(x);
}

上面代碼中，函數(shù)m和n都屬于尾調(diào)用，因?yàn)樗鼈兌际呛瘮?shù)f的最后一步操作。

總結(jié)：

1. 尾調(diào)用不訪問(wèn)當(dāng)前棧幀的變量(也就是說(shuō)函數(shù)不是一個(gè)閉包）
2. 在函數(shù)內(nèi)部，尾調(diào)用是最后一條語(yǔ)句
3. 尾調(diào)用的結(jié)果作為函數(shù)值返回

同時(shí)滿足以上三個(gè)條件，就是尾調(diào)用，可以被js引擎自動(dòng)優(yōu)化。

二. 尾調(diào)用優(yōu)化

尾調(diào)用之所以與其他調(diào)用不同，就在于它的特殊的調(diào)用位置。

函數(shù)調(diào)用會(huì)在內(nèi)存形成一個(gè)“調(diào)用記錄”，又稱“調(diào)用幀”（call frame），保存調(diào)用位置和內(nèi)部變量等信息。如果在函數(shù)A的內(nèi)部調(diào)用函數(shù)B，那么在A的調(diào)用幀上方，還會(huì)形成一個(gè)B的調(diào)用幀。等到B運(yùn)行結(jié)束，將結(jié)果返回到A，B的調(diào)用幀才會(huì)消失。如果函數(shù)B內(nèi)部還調(diào)用函數(shù)C，那就還有一個(gè)C的調(diào)用幀，以此類推。所有的調(diào)用幀，就形成一個(gè)“調(diào)用?！保╟all stack）。

未命名文件 (1).png

尾調(diào)用由于是函數(shù)的最后一步操作，所以不需要保留外層函數(shù)的調(diào)用幀，因?yàn)檎{(diào)用位置、內(nèi)部變量等信息都不會(huì)再用到了，只要直接用內(nèi)層函數(shù)的調(diào)用幀，取代外層函數(shù)的調(diào)用幀就可以了。

function f() {
  let m = 1;
  let n = 2;
  return g(m + n);
}
f();

// 等同于
function f() {
  return g(3);
}
f();

// 等同于
g(3);

上面代碼中，如果函數(shù)g不是尾調(diào)用，函數(shù)f就需要保存內(nèi)部變量m和n的值、g的調(diào)用位置等信息。但由于調(diào)用g之后，函數(shù)f就結(jié)束了，所以執(zhí)行到最后一步，完全可以刪除f(x)的調(diào)用幀，只保留g(3)的調(diào)用幀。

未命名文件 (3).png

這就叫做“尾調(diào)用優(yōu)化”（Tail call optimization），即只保留內(nèi)層函數(shù)的調(diào)用幀。如果所有函數(shù)都是尾調(diào)用，那么完全可以做到每次執(zhí)行時(shí)，調(diào)用幀只有一項(xiàng)，這將大大節(jié)省內(nèi)存。這就是“尾調(diào)用優(yōu)化”的意義。

注意，只有不再用到外層函數(shù)的內(nèi)部變量，內(nèi)層函數(shù)的調(diào)用幀才會(huì)取代外層函數(shù)的調(diào)用幀，否則就無(wú)法進(jìn)行“尾調(diào)用優(yōu)化”。

function addOne(a){
  var one = 1;
  function inner(b){
    return b + one;
  }
  return inner(a);
}

上面的函數(shù)不會(huì)進(jìn)行尾調(diào)用優(yōu)化，因?yàn)閮?nèi)層函數(shù)inner用到了外層函數(shù)addOne的內(nèi)部變量one。

三. 尾遞歸

函數(shù)調(diào)用自身，稱為遞歸。如果尾調(diào)用自身，就稱為尾遞歸。

遞歸是非常耗費(fèi)內(nèi)存的，因?yàn)樾枰瑫r(shí)保存成千上百個(gè)調(diào)用幀，很容易發(fā)生“棧溢出”錯(cuò)誤（stack overflow）。

但對(duì)于尾遞歸來(lái)說(shuō)，由于只存在一個(gè)調(diào)用幀，所以永遠(yuǎn)不會(huì)發(fā)生“棧溢出”錯(cuò)誤。

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

factorial(5) // 120

上面代碼是一個(gè)階乘函數(shù)，計(jì)算n的階乘，最多需要保存n個(gè)調(diào)用記錄，復(fù)雜度 O(n) 。上面代碼的調(diào)用幀如下所示

未命名文件 (4).png

如果改寫成尾遞歸，只保留一個(gè)調(diào)用記錄，復(fù)雜度 O(1) 。

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

factorial(5, 1) // 120

還有一個(gè)比較著名的例子，就是計(jì)算斐波那契數(shù)列，也能充分說(shuō)明尾遞歸優(yōu)化的重要性。

非尾遞歸的斐波那契數(shù)列實(shí)現(xiàn)如下。

function fibonacci (n) {
  if (n <= 1) return 1;

  return fibonacci(n - 1) + fibonacci(n - 2);
}

fibonacci(10) // 89
fibonacci(100) // 超時(shí)
fibonacci(500) // 超時(shí)

尾遞歸優(yōu)化過(guò)的斐波那契數(shù)列實(shí)現(xiàn)如下。

function fibonacci2 (n , ac1 = 1 , ac2 = 1) {
  if(n <= 1) return ac2;

  return fibonacci2 (n - 1, ac2, ac1 + ac2);
}

fibonacci2(100) // 573147844013817200000
fibonacci2(1000) // 7.0330367711422765e+208
fibonacci2(10000) // Infinity

由此可見(jiàn)，“尾調(diào)用優(yōu)化”對(duì)遞歸操作意義重大，只要使用尾遞歸，就不會(huì)發(fā)生棧溢出（或者層層遞歸造成的超時(shí)），相對(duì)節(jié)省內(nèi)存。

四. 遞歸函數(shù)的改寫

尾遞歸的實(shí)現(xiàn)，往往需要改寫遞歸函數(shù)，確保最后一步只調(diào)用自身。做到這一點(diǎn)的方法，就是把所有用到的內(nèi)部變量改寫成函數(shù)的參數(shù)。

比如上面的例子，階乘函數(shù) factorial 需要用到一個(gè)中間變量total，那就把這個(gè)中間變量改寫成函數(shù)的參數(shù)。這樣做的缺點(diǎn)就是不太直觀，第一眼很難看出來(lái)，為什么計(jì)算5的階乘，需要傳入兩個(gè)參數(shù)5和1？

兩個(gè)方法可以解決這個(gè)問(wèn)題。方法一是在尾遞歸函數(shù)之外，再提供一個(gè)正常形式的函數(shù)。

// 尾遞歸階乘函數(shù)
function tailFactorial(n, total) {
  if (n === 1) return total;
  return tailFactorial(n - 1, n * total);
}

// 階乘函數(shù)
function factorial(n) {
  return tailFactorial(n, 1);
}

factorial(5) // 120

上面代碼通過(guò)一個(gè)正常形式的階乘函數(shù)factorial，調(diào)用尾遞歸函數(shù)tailFactorial，看起來(lái)就正常多了。

函數(shù)式編程有一個(gè)概念，叫做柯里化（currying），意思是將多參數(shù)的函數(shù)轉(zhuǎn)換成單參數(shù)的形式。這里也可以使用柯里化。

function currying(fn, n) {
  return function (m) {
    return fn.call(this, m, n);
  };
}

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

const factorial = currying(tailFactorial, 1);

factorial(5) // 120

上面代碼通過(guò)柯里化，將尾遞歸函數(shù)tailFactorial變?yōu)橹唤邮芤粋€(gè)參數(shù)的factorial。

另外也可以使用ES6的函數(shù)默認(rèn)值

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

factorial(5) // 120

上面代碼中，參數(shù)total有默認(rèn)值1，所以調(diào)用時(shí)不用提供這個(gè)值。

總結(jié)一下，遞歸本質(zhì)上是一種循環(huán)操作。純粹的函數(shù)式編程語(yǔ)言沒(méi)有循環(huán)操作命令，所有的循環(huán)都用遞歸實(shí)現(xiàn)，這就是為什么尾遞歸對(duì)這些語(yǔ)言極其重要。

對(duì)于其他支持“尾調(diào)用優(yōu)化”的語(yǔ)言（比如 Lua，ES6），只需要知道循環(huán)可以用遞歸代替，而一旦使用遞歸，就最好使用尾遞歸。

五. 尾遞歸優(yōu)化的實(shí)現(xiàn)

尾遞歸之所以需要優(yōu)化，原因是調(diào)用棧太多，造成溢出，那么只要減少調(diào)用棧，就不會(huì)溢出。怎么做可以減少調(diào)用棧呢？就是采用“循環(huán)”換掉“遞歸”。

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是一個(gè)遞歸函數(shù)，參數(shù)x是需要累加的值，參數(shù)y控制遞歸次數(shù)。一旦指定sum遞歸 100000 次，就會(huì)報(bào)錯(cuò)，提示超出調(diào)用棧的最大次數(shù)。

蹦床函數(shù)（trampoline）可以將遞歸執(zhí)行轉(zhuǎn)為循環(huán)執(zhí)行。

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

上面就是蹦床函數(shù)的一個(gè)實(shí)現(xiàn)，它接受一個(gè)函數(shù)f作為參數(shù)。只要f執(zhí)行后返回一個(gè)函數(shù)，就繼續(xù)執(zhí)行。

注意，這里是返回一個(gè)函數(shù)，然后執(zhí)行該函數(shù)，而不是函數(shù)里面調(diào)用函數(shù)，這樣就避免了遞歸執(zhí)行，從而就消除了調(diào)用棧過(guò)大的問(wèn)題。

然后，要做的就是將原來(lái)的遞歸函數(shù)，改寫為每一步返回另一個(gè)函數(shù)。

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

上面代碼中，sum函數(shù)只要 y > 0，就會(huì)返回自身的另一個(gè)版本。

現(xiàn)在，使用蹦床函數(shù)執(zhí)行sum，就不會(huì)發(fā)生調(diào)用棧溢出。

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

事實(shí)上蹦床函數(shù)并不是真正的尾遞歸優(yōu)化，下面的實(shí)現(xiàn)才是。

// 尾遞歸優(yōu)化的實(shí)現(xiàn)
function tco(f) {
  var value; // 最終返回的結(jié)果
  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
  }
});

sum(1, 100000)
// 100001

上面代碼中，tco函數(shù)是尾遞歸優(yōu)化的實(shí)現(xiàn)，它的奧妙就在于狀態(tài)變量active。默認(rèn)情況下，這個(gè)變量是不激活的。一旦進(jìn)入尾遞歸優(yōu)化的過(guò)程( accumulator 被調(diào)用時(shí) )，這個(gè)變量就激活了。然后，每一輪遞歸sum返回的都是undefined，所以就避免了遞歸執(zhí)行；而accumulated數(shù)組存放每一輪sum執(zhí)行的參數(shù)，總是有值的，這就保證了accumulator函數(shù)內(nèi)部的while循環(huán)總是會(huì)執(zhí)行。這樣就很巧妙地將“遞歸”改成了“循環(huán)”，而后一輪的參數(shù)會(huì)取代前一輪的參數(shù)，保證了調(diào)用棧只有一層。