什么是尾調(diào)用

• 尾調(diào)用（Tail Call）是函數(shù)式編程的一個(gè)重要概念，就是指某個(gè)函數(shù)的最后一步是調(diào)用另一個(gè)函數(shù)。

// 尾調(diào)用
function f(x){
  return g(x);
}
// 不屬于尾調(diào)用， 調(diào)用函數(shù)g之后，還有賦值操作
function f(x){
  let y = g(x);
  return y;
}

// 不屬于尾調(diào)用， 調(diào)用后還有操作，即使寫在一行內(nèi)
function f(x){
  return g(x) + 1;
}

// 不屬于尾調(diào)用，下面的兩個(gè)函數(shù)等同
function f(x){
  g(x);
}
function f(x){
  g(x);
  return undefined;
}

// 尾調(diào)用, 雖然尾調(diào)用沒出現(xiàn)在函數(shù)尾部，但是只要是最后一步操作即可
function f(x) {
  if (x > 0) {
    return m(x)
  }
  return n(x);
}

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

• 函數(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)用棧”（call stack）。
• 尾調(diào)用由于是函數(shù)的最后一步操作，所以不需要保留外層函數(shù)的調(diào)用幀，因?yàn)檎{(diào)用位置、內(nèi)部變量等信息都不會(huì)再用到了，只要直接用內(nèi)層函數(shù)的調(diào)用幀，取代外層函數(shù)的調(diào)用幀就可以了。
• 只有不再用到外層函數(shù)的內(nèi)部變量，內(nèi)層函數(shù)的調(diào)用幀才會(huì)取代外層函數(shù)的調(diào)用幀，否則就無法進(jìn)行“尾調(diào)用優(yōu)化”。

// 不會(huì)進(jìn)行尾調(diào)用優(yōu)化，因?yàn)閮?nèi)層函數(shù)inner用到了外層函數(shù)addOne的內(nèi)部變量one。
function addOne(a){
  var one = 1;
  function inner(b){
    return b + one;
  }
  return inner(a);
}

尾遞歸

• 函數(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ò)誤。

// 正常遞歸，復(fù)雜度 O(n)
function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}

// 尾遞歸，復(fù)雜度 O(1)
function factorial(n, total = 1) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

來源： http://es6.ruanyifeng.com/#docs/function#尾調(diào)用優(yōu)化