調(diào)用棧（Call Stack）
調(diào)用棧（Call Stack）是一個基本的計算機概念约郁，這里引入一個概念：棧幀。
棧幀是指為一個函數(shù)調(diào)用單獨分配的那部分椀剑空間鬓梅。
當(dāng)運行的程序從當(dāng)前函數(shù)調(diào)用另外一個函數(shù)時，就會為下一個函數(shù)建立一個新的棧幀谨湘，并且進入這個棧幀绽快，這個棧幀稱為當(dāng)前幀。而原來的函數(shù)也有一個對應(yīng)的棧幀紧阔，被稱為調(diào)用幀坊罢。每一個棧幀里面都會存入當(dāng)前函數(shù)的局部變量。
當(dāng)函數(shù)被調(diào)用時寓辱，就會被加入到調(diào)用棧頂部，執(zhí)行結(jié)束之后赤拒，就會從調(diào)用棧頂部移除該函數(shù)秫筏。并將程序運行權(quán)利（幀指針）交給此時棧頂?shù)臈＿@種后進后出的結(jié)構(gòu)也就是函數(shù)的調(diào)用棧挎挖。
而在JavaScript里这敬，可以很方便的通過console.trace()這個方法查看當(dāng)前函數(shù)的調(diào)用幀
尾調(diào)用
說尾遞歸之前必須先了解一下什么是尾調(diào)用。簡單的說蕉朵，就是一個函數(shù)執(zhí)行的最后一步是將另外一個函數(shù)調(diào)用并返回崔涂。
以下是正確示范：
// 尾調(diào)用正確示范1.0
function f(x){
return g(x);
}
// 尾調(diào)用正確示范2.0
function f(x) {
if (x > 0) {
return m(x)
}
return n(x);
}
1.0程序的最后一步即是執(zhí)行函數(shù)g，同時將其返回值返回始衅。2.0中冷蚂，尾調(diào)用并不是非得寫在最后一行中，只要執(zhí)行時汛闸，是最后一步操作就可以了蝙茶。
以下是錯誤示范：
// 尾調(diào)用錯誤示范1.0
function f(x){
let y = g(x);
return y;
}
// 尾調(diào)用錯誤示范2.0
function f(x){
return g(x) + 1;
}
// 尾調(diào)用錯誤示范3.0
function f(x) {
g(x); // 這一步相當(dāng)于g(x) return undefined
}
1.0最后一步為賦值操作，2.0最后一步為加法運算操作诸老，3.0隱式的有一句return undefined
尾調(diào)用優(yōu)化
在調(diào)用棧的部分我們知道隆夯，當(dāng)一個函數(shù)A調(diào)用另外一個函數(shù)B時，就會形成棧幀别伏，在調(diào)用棧內(nèi)同時存在調(diào)用幀A和當(dāng)前幀B蹄衷，這是因為當(dāng)函數(shù)B執(zhí)行完成后，還需要將執(zhí)行權(quán)返回A厘肮，那么函數(shù)A內(nèi)部的變量愧口，調(diào)用函數(shù)B的位置等信息都必須保存在調(diào)用幀A中。不然类茂，當(dāng)函數(shù)B執(zhí)行完繼續(xù)執(zhí)行函數(shù)A時调卑，就會亂套抡砂。
那么現(xiàn)在，我們將函數(shù)B放到了函數(shù)A的最后一步調(diào)用（即尾調(diào)用）恬涧，那還有必要保留函數(shù)A的棧幀么注益？當(dāng)然不用，因為之后并不會再用到其調(diào)用位置溯捆、內(nèi)部變量丑搔。因此直接用函數(shù)B的棧幀取代A的棧幀即可。當(dāng)然提揍，如果內(nèi)層函數(shù)使用了外層函數(shù)的變量啤月，那么就仍然需要保留函數(shù)A的棧幀，典型例子即是閉包劳跃。
在網(wǎng)上有很多關(guān)于講解尾調(diào)用的博客文章谎仲，其中流傳廣泛的一篇中有這樣一段。我不是很認(rèn)同刨仑。
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() 的調(diào)用記錄，只保留 g(3) 的調(diào)用記錄祈搜。
但我認(rèn)為第一種中较店，也是先執(zhí)行m+n這步操作，再調(diào)用函數(shù)g同時返回容燕。這應(yīng)當(dāng)是一次尾調(diào)用泽西。同時m+n的值也通過參數(shù)傳入函數(shù)g內(nèi)部，并沒有直接引用缰趋，因此也不能說需要保存f內(nèi)部的變量的值捧杉。
總得來說，如果所有函數(shù)的調(diào)用都是尾調(diào)用秘血，那么調(diào)用棧的長度就會小很多味抖，這樣需要占用的內(nèi)存也會大大減少。這就是尾調(diào)用優(yōu)化的含義灰粮。
尾遞歸
遞歸仔涩，是指在函數(shù)的定義中使用函數(shù)自身的一種方法。函數(shù)調(diào)用自身即稱為遞歸粘舟，那么函數(shù)在尾調(diào)用自身熔脂，即稱為尾遞歸佩研。
最常見的遞歸，斐波拉契數(shù)列霞揉，普通遞歸的寫法：
function f(n) {
if (n === 0 || n === 1) return n
else return f(n - 1) + f(n - 2)
}
這種寫法旬薯，簡單粗暴，但是有個很嚴(yán)重的問題适秩。調(diào)用棧隨著n的增加而線性增加绊序，當(dāng)n為一個大數(shù)（我測了一下，當(dāng)n為100的時候秽荞，瀏覽器窗口就會卡死骤公。。）時扬跋，就會爆棧了（棧溢出阶捆，stack overflow）。這是因為這種遞歸操作中钦听，同時保存了大量的棧幀洒试，調(diào)用棧非常長，消耗了巨大的內(nèi)存彪见。
接下來儡司，將普通遞歸升級為尾遞歸看看娱挨。
function fTail(n, a = 0, b = 1) {
if (n === 0) return a
return fTail(n - 1, b, a + b)
}
很明顯余指，其調(diào)用棧為
fTail(5) => fTail(4, 1, 1) => fTail(3, 1, 2) => fTail(2, 2, 3) => fTail(1, 3, 5) => fTail(0, 5, 8) => return 5
被尾遞歸改寫之后的調(diào)用棧永遠都是更新當(dāng)前的棧幀而已，這樣就完全避免了爆棧的危險跷坝。
但是酵镜，想法是好的，從尾調(diào)用優(yōu)化到尾遞歸優(yōu)化的出發(fā)點也沒錯柴钻，然并卵：）淮韭，讓我們看看V8引擎官方團隊的解釋
Proper tail calls have been implemented but not yet shipped given that a change to the feature is currently under discussion at TC39.
意思就是人家已經(jīng)做好了，但是就是還不能不給你用：）嗨呀贴届，好氣喔靠粪。
當(dāng)然，人家肯定是有他的正當(dāng)理由的：
- 在引擎層面消除尾遞歸是一個隱式的行為毫蚓，程序員寫代碼時可能意識不到自己寫了死循環(huán)的尾遞歸占键，而出現(xiàn)死循環(huán)后又不會報出
stack overflow的錯誤，難以辨別元潘。 - 堆棧信息會在優(yōu)化的過程中丟失畔乙，開發(fā)者調(diào)試非常困難。
道理我都懂翩概，但是不信邪的我拿nodeJs（v6.9.5）手動測試了一下：
好的牲距，我服了
手動優(yōu)化
雖然我們暫時用不上ES6的尾遞歸高端優(yōu)化返咱，但遞歸優(yōu)化的本質(zhì)還是為了減少調(diào)用棧，避免內(nèi)存占用過多牍鞠，爆棧的危險咖摹。而俗話說的好，一切能用遞歸寫的函數(shù)皮服，都能用循環(huán)寫——尼克拉斯·夏楞艾，如果將遞歸改成循環(huán)的話，不就解決了這種調(diào)用棧的問題么龄广。
方案一：直接改函數(shù)內(nèi)部硫眯，循環(huán)執(zhí)行
function fLoop(n, a = 0, b = 1) {
while (n--) {
[a, b] = [b, a + b]
}
return a
}
這種方案簡單粗暴，缺點就是沒有遞歸的那種寫法比較容易理解择同。
方案二：Trampolining（蹦床函數(shù)）
function trampoline(f) {
while (f && f instanceof Function) {
f = f()
}
return f
}
function f(n, a = 0, b = 1) {
if (n > 0) {
[a, b] = [b, a + b]
return f.bind(null, n - 1, a, b)
} else {
return a
}
}
trampoline(f(5)) // return 5
這種寫法算是容易理解一些了两入，就是蹦床函數(shù)的作用需要仔細(xì)看看。缺點還有就是需要修改原函數(shù)內(nèi)部的寫法敲才。
方案三：尾遞歸函數(shù)轉(zhuǎn)循環(huán)方法
function tailCallOptimize(f) {
let value
let active = false
const accumulated = []
return function accumulator() {
accumulated.push(arguments)
if (!active) {
active = true
while (accumulated.length) {
value = f.apply(this, accumulated.shift())
}
active = false
return value
}
}
}
const f = tailCallOptimize(function(n, a = 0, b = 1) {
if (n === 0) return a
return f(n - 1, b, a + b)
})
f(5) // return 5
經(jīng)過 tailCallOptimize 包裝后返回的是一個新函數(shù) accumulator裹纳，執(zhí)行 f時實際執(zhí)行的是這個函數(shù)。這種方法可以不用修改原遞歸函數(shù)紧武，當(dāng)調(diào)用遞歸時只用使用該方法轉(zhuǎn)置一下便可解決遞歸調(diào)用的問題剃氧。
總結(jié)
尾遞歸優(yōu)化是個好東西，但既然暫時用不上阻星，那我們就該在平時編碼的過程中朋鞍，對使用到了遞歸的地方特別敏感，時刻避免出現(xiàn)死循環(huán)妥箕，爆棧等危險滥酥。畢竟，好的工具不如好的習(xí)慣畦幢。
筆者水平有限坎吻，如有錯誤，歡迎指出宇葱。
參考資料：
