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

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

尾調(diào)用（Tail Call）是函數(shù)式編程的一個(gè)重要概念，本身非常簡(jiǎn)單，一句話就能說清楚，就是指某個(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)。情況三等同于下面的代碼。

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的最后一步操作。
尾調(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)用?！保?code>call stack）。

尾調(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)用幀。

這就叫做“尾調(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)用幀，否則就無法進(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ì)于尾遞歸來說，由于只存在一個(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)。

如果改寫成尾遞歸，只保留一個(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ì)算 Fibonacci 數(shù)列，也能充分說明尾遞歸優(yōu)化的重要性。

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

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

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

Fibonacci(10) // 89
Fibonacci(100) // 堆棧溢出
Fibonacci(500) // 堆棧溢出

尾遞歸優(yōu)化過的 Fibonacci 數(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

由此可見，“尾調(diào)用優(yōu)化”對(duì)遞歸操作意義重大，所以一些函數(shù)式編程語(yǔ)言將其寫入了語(yǔ)言規(guī)格。ES6 是如此，第一次明確規(guī)定，所有 ECMAScript 的實(shí)現(xiàn)，都必須部署“尾調(diào)用優(yōu)化”。這就是說，ES6 中只要使用尾遞歸，就不會(huì)發(fā)生棧溢出，相對(duì)節(jié)省內(nèi)存。