尾調(diào)用（Tail Call）是函數(shù)式編程的一個重要概念父阻，本身非常簡單愈涩，一句話就能說清楚望抽，就是指某個函數(shù)的最后一步是調(diào)用另一個函數(shù)。

遞歸函數(shù)

假設(shè)我們需要計算階乘 factorial「n! = 1 * 2 * 3 * ... * n」履婉，用函數(shù)表示

image.png

fact(n) 用遞歸方式寫：

def fact(n: int) -> int:
    if n == 1:
        return 1
    return n * fact(n - 1)

計算 fact(5)煤篙，過程如下：

> fact(5)
> 5 * fact(4)
> 5 * (4 * fact(3))
> 5 * (4 * (3 * fact(2)))
> 5 * (4 * (3 * (2 * fact(1))))
> 5 * (4 * (3 * (2 * 1)))
> 5 * (4 * (3 * 2))
> 5 * (4 * 6)
> 5 * 24
> 120

在每次遞歸調(diào)用的時候，都會產(chǎn)生一個臨時變量毁腿，導(dǎo)致進(jìn)程內(nèi)存占用量變大辑奈。這樣執(zhí)行遞歸層數(shù)比較深的代碼時，除了無謂的內(nèi)存浪費(fèi)已烤，還可能導(dǎo)致著名的堆棧溢出錯誤鸠窗。

在計算機(jī)中，函數(shù)調(diào)用是通過棧 Stack 這種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的胯究，每當(dāng)進(jìn)入一個函數(shù)調(diào)用稍计，棧就會加一層棧幀，當(dāng)數(shù)據(jù)返回值時唐片，棧就會減一層棧幀丙猬。由于棧的大小不是無限的，所以遞歸調(diào)用的次數(shù)過多费韭，會導(dǎo)致棧溢出茧球。

>>> fact(1000)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in fact
  ...
  File "<stdin>", line 4, in fact
RuntimeError: maximum recursion depth exceeded in comparison

理論上，所有的遞歸函數(shù)都可以寫成循環(huán)的方式星持，避免對棧溢出抢埋，但循環(huán)的邏輯不如遞歸清晰。改成循環(huán)就是手動維護(hù)一些數(shù)據(jù)結(jié)構(gòu)來緩存數(shù)據(jù)督暂，而不是用系統(tǒng)的調(diào)用棧揪垄。

遞歸函數(shù)不斷調(diào)用自身，這種機(jī)械的重復(fù)行為很適合機(jī)器來執(zhí)行逻翁，但是由于調(diào)用棧大小的限制饥努，我們需要對遞歸做優(yōu)化 - 尾遞歸。

什么是尾調(diào)用(Tail Call)八回？

尾調(diào)用（Tail Call）是函數(shù)式編程的一個重要概念酷愧，本身非常簡單，一句話就能說清楚缠诅，就是指某個函數(shù)的最后一步是調(diào)用另一個函數(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)用戏自，即使語義完全一樣邦投。情況二也屬于調(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的最后一步操作弯淘。

嚴(yán)格模式才有效

ES6 的尾調(diào)用優(yōu)化只在嚴(yán)格模式下開啟，正常模式是無效的吉懊。
這是因?yàn)樵谡ＤＪ较侣龋瘮?shù)內(nèi)部有兩個變量，可以跟蹤函數(shù)的調(diào)用棧借嗽。

• func.arguments：返回調(diào)用時函數(shù)的參數(shù)态鳖。
• func.caller：返回調(diào)用當(dāng)前函數(shù)的那個函數(shù)。
  尾調(diào)用優(yōu)化發(fā)生時恶导，函數(shù)的調(diào)用棧會改寫浆竭，因此上面兩個變量就會失真。嚴(yán)格模式禁用這兩個變量惨寿，所以尾調(diào)用模式僅在嚴(yán)格模式下生效邦泄。

function restricted() {
  'use strict';
  restricted.caller;    // 報錯
  restricted.arguments; // 報錯
}
restricted();

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

在開始進(jìn)一步了解尾調(diào)用優(yōu)化前，我們首先要熟悉兩個概念裂垦，分別是調(diào)用棧（call stack）和調(diào)用幀（call frame）顺囊。

調(diào)用棧（call stack）

• 調(diào)用棧是一種棧結(jié)構(gòu)的數(shù)據(jù)，它是由調(diào)用偵組成的蕉拢。
• 調(diào)用棧記錄了函數(shù)的執(zhí)行順序和函數(shù)內(nèi)部變量等信息特碳。
• 程序運(yùn)行到一個函數(shù)，它就會將其添加到“調(diào)用椘罅浚”中测萎，當(dāng)從這個函數(shù)返回的時候，就會將這個函數(shù)從調(diào)用棧中刪掉届巩。

調(diào)用幀（call frame）
每個進(jìn)入到調(diào)用棧中的函數(shù)硅瞧，都會分配到一個單獨(dú)的棧空間恕汇，稱為“調(diào)用偵”腕唧。

在調(diào)用棧中每個“調(diào)用偵”都對應(yīng)一個函數(shù)或辖，最上方的調(diào)用幀稱為“當(dāng)前幀”，調(diào)用棧是由所有的調(diào)用偵形成的枣接。

image.png

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

如果在函數(shù)A的內(nèi)部調(diào)用函數(shù)B但惶，那么在A的調(diào)用幀上方耳鸯，還會形成一個B的調(diào)用幀。等到B運(yùn)行結(jié)束膀曾，將結(jié)果返回到A县爬，B的調(diào)用幀才會消失。如果函數(shù)B內(nèi)部還調(diào)用函數(shù)C添谊，那就還有一個C的調(diào)用幀财喳，以此類推。所有的調(diào)用幀斩狱，就形成一個“調(diào)用棧（call stack）”耳高。

話不多說，舉個例子

function foo () { console.log(111); }
function bar () { foo(); }
function baz () { bar(); }

baz();

調(diào)用棧情況參考下圖：

image.png

造成這種結(jié)果是因?yàn)槊總€函數(shù)在調(diào)用另一個函數(shù)的時候所踊，并沒有 return 該調(diào)用三妈，所以JS引擎會認(rèn)為你還沒有執(zhí)行完柑司，會保留你的調(diào)用幀。

baz() 里面調(diào)用了 bar() 函數(shù)，并沒有 return 該調(diào)用表锻，所以在調(diào)用棧中保持自己的調(diào)用幀坦康，同時 bar() 函數(shù)的調(diào)用幀在調(diào)用棧中生成浑度，同理字支，bar() 函數(shù)又調(diào)用了 foo() 函數(shù)，最后執(zhí)行到 foo() 函數(shù)的時候惋增，沒有再調(diào)用其他函數(shù)叠殷，這里沒有顯示聲明 return，所以這里默認(rèn) return undefined诈皿。

foo() 執(zhí)行完了林束，銷毀調(diào)用棧中自己的記錄，依次銷毀 bar() 和 baz() 的調(diào)用幀稽亏，最后完成整個流程壶冒。

如果對上面的例子做如下修改：

function foo () { console.log(111); }
function bar () { return foo(); }
function baz () { return bar(); }

baz();

如果尾調(diào)用優(yōu)化生效，流程圖就會變成這樣：

image.png

我們可以很清楚的看到截歉，尾調(diào)用由于是函數(shù)的最后一步操作胖腾，所以不需要保留外層函數(shù)的調(diào)用記錄，只要直接用內(nèi)層函數(shù)的調(diào)用記錄取代外層函數(shù)的調(diào)用記錄就可以了，調(diào)用棧中始終只保持了一條調(diào)用幀咸作。

這就叫做尾調(diào)用優(yōu)化（Tail call optimization）锨阿，即只保留內(nèi)層函數(shù)的調(diào)用幀。如果所有的函數(shù)都是尾調(diào)用的話记罚，調(diào)用位置墅诡、內(nèi)部變量等信息都不會再用到了，那么在調(diào)用棧中的調(diào)用幀始終只有一條桐智，這樣會節(jié)省很大一部分的內(nèi)存末早，這也是尾調(diào)用優(yōu)化的意義。

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)用幀悦穿。

注意攻礼，只有不再用到外層函數(shù)的內(nèi)部變量，內(nèi)層函數(shù)的調(diào)用幀才會取代外層函數(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ù)不會進(jìn)行尾調(diào)用優(yōu)化，因?yàn)閮?nèi)層函數(shù)inner用到了外層函數(shù)addOne的內(nèi)部變量one瞬沦。

尾調(diào)用的應(yīng)用——尾遞歸Tail Recursion

函數(shù)調(diào)用自身太伊，稱為遞歸。如果尾調(diào)用自身逛钻，就稱為尾遞歸僚焦。
遞歸非常耗費(fèi)內(nèi)存，因?yàn)樾枰瑫r保存成千上百個調(diào)用幀曙痘，很容易發(fā)生“棧溢出”錯誤（stack overflow）芳悲。但對于尾遞歸來說，由于只存在一個調(diào)用幀边坤，所以永遠(yuǎn)不會發(fā)生“棧溢出”錯誤名扛。

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

factorial(5) // 120

上面代碼是一個階乘函數(shù)，計算n的階乘茧痒，最多需要保存n個調(diào)用記錄肮韧，空間復(fù)雜度 O(n) 。

如果改寫成尾遞歸，只保留一個調(diào)用記錄惹苗，空間復(fù)雜度 O(1) 殿较。

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

factorial(5, 1) // 120

還有一個比較著名的例子，就是計算 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)化”對遞歸操作意義重大，所以一些函數(shù)式編程語言將其寫入了語言規(guī)格业汰。ES6 亦是如此伙窃，第一次明確規(guī)定，所有 ECMAScript 的實(shí)現(xiàn)样漆，都必須部署“尾調(diào)用優(yōu)化”为障。這就是說，ES6 中只要使用尾遞歸放祟，就不會發(fā)生棧溢出（或者層層遞歸造成的超時）鳍怨，相對節(jié)省內(nèi)存。

遞歸函數(shù)的改寫

尾遞歸的實(shí)現(xiàn)跪妥，往往需要改寫遞歸函數(shù)鞋喇，確保最后一步只調(diào)用自身。做到這一點(diǎn)的方法眉撵，就是把所有用到的內(nèi)部變量改寫成函數(shù)的參數(shù)侦香。比如上面的例子，階乘函數(shù) factorial 需要用到一個中間變量total纽疟，那就把這個中間變量改寫成函數(shù)的參數(shù)罐韩。這樣做的缺點(diǎn)就是不太直觀，第一眼很難看出來仰挣，為什么計算5的階乘伴逸，需要傳入兩個參數(shù)5和1？

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

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

function factorial(n) {
  return tailFactorial(n, 1);
}

factorial(5) // 120

上面代碼通過一個正常形式的階乘函數(shù)factorial颓芭，調(diào)用尾遞歸函數(shù)tailFactorial顷锰，看起來就正常多了。

函數(shù)式編程有一個概念亡问，叫做柯里化（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

上面代碼通過柯里化束世，將尾遞歸函數(shù)tailFactorial變?yōu)橹唤邮芤粋€參數(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)用時不用提供這個值贫堰。

總結(jié)一下穆壕，遞歸本質(zhì)上是一種循環(huán)操作。純粹的函數(shù)式編程語言沒有循環(huán)操作命令其屏，所有的循環(huán)都用遞歸實(shí)現(xiàn)喇勋，這就是為什么尾遞歸對這些語言極其重要。對于其他支持“尾調(diào)用優(yōu)化”的語言（比如 Lua偎行，ES6）川背，只需要知道循環(huán)可以用遞歸代替，而一旦使用遞歸蛤袒，就最好使用尾遞歸渗常。

尾遞歸優(yōu)化(Tail Call Optimization)

尾遞歸優(yōu)化只在嚴(yán)格模式下生效，那么正常模式下汗盘，或者那些不支持該功能的環(huán)境中，有沒有辦法也使用尾遞歸優(yōu)化呢询一？回答是可以的隐孽，就是自己實(shí)現(xiàn)尾遞歸優(yōu)化。

它的原理非常簡單健蕊。尾遞歸之所以需要優(yōu)化菱阵，原因是調(diào)用棧太多，造成溢出缩功，那么只要減少調(diào)用棧晴及，就不會溢出。怎么做可以減少調(diào)用棧呢嫡锌？就是采用“循環(huán)”換掉“遞歸”虑稼。

下面是一個正常的遞歸函數(shù)。

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是一個遞歸函數(shù)蛛倦，參數(shù)x是需要累加的值，參數(shù)y控制遞歸次數(shù)啦桌。一旦指定sum遞歸 100000 次溯壶，就會報錯，提示超出調(diào)用棧的最大次數(shù)。
蹦床函數(shù)（trampoline）可以將遞歸執(zhí)行轉(zhuǎn)為循環(huán)執(zhí)行且改。

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

上面就是蹦床函數(shù)的一個實(shí)現(xiàn)验烧，它接受一個函數(shù)f作為參數(shù)。只要f執(zhí)行后返回一個函數(shù)又跛，就繼續(xù)執(zhí)行碍拆。注意，這里是返回一個函數(shù)效扫，然后執(zhí)行該函數(shù)倔监，而不是函數(shù)里面調(diào)用函數(shù)，這樣就避免了遞歸執(zhí)行菌仁，從而就消除了調(diào)用棧過大的問題浩习。

然后，要做的就是將原來的遞歸函數(shù)济丘，改寫為每一步返回另一個函數(shù)谱秽。

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

上面代碼中，sum函數(shù)的每次執(zhí)行摹迷，都會返回自身的另一個版本疟赊。
現(xiàn)在，使用蹦床函數(shù)執(zhí)行sum峡碉，就不會發(fā)生調(diào)用棧溢出近哟。

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

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

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

sum(1, 100000)
// 100001

上面代碼中吉执，tco函數(shù)是尾遞歸優(yōu)化的實(shí)現(xiàn)，它的奧妙就在于狀態(tài)變量active地来。默認(rèn)情況下戳玫，這個變量是不激活的。一旦進(jìn)入尾遞歸優(yōu)化的過程未斑，這個變量就激活了咕宿。然后，每一輪遞歸sum返回的都是undefined蜡秽，所以就避免了遞歸執(zhí)行府阀；而accumulated數(shù)組存放每一輪sum執(zhí)行的參數(shù)，總是有值的载城，這就保證了accumulator函數(shù)內(nèi)部的while循環(huán)總是會執(zhí)行肌似。

這樣就很巧妙地將“遞歸”改成了“循環(huán)”，而后一輪的參數(shù)會取代前一輪的參數(shù)诉瓦，保證了調(diào)用棧只有一層川队。

參考：
wikipedia.org
尾調(diào)用優(yōu)化 - 阮一峰
JS 調(diào)用棧機(jī)制與 ES6 尾調(diào)用優(yōu)化介紹
https://segmentfault.com/a/1190000020694801