文中栗子來源 http://es6.ruanyifeng.com/#docs/function#%E5%B0%BE%E9%80%92%E5%BD%92
來源
函數(shù) caller 運行時，調用其他函數(shù) called ，js引起會在調用棧中新開一個調用幀存儲作用域和上下文信息挎塌，而caller的調用幀信息仍需要保存苦掘。而內存中調用棧存儲信息有限，遞歸情況下，如果遞歸層次過深會導致調用棧耗光而引起stack overflow —— 爆棧。
注：文中例子執(zhí)行環(huán)境均為 Chrome 72
比如這個Fibonacci數(shù)列的實現(xiàn)
function f(n){
if(n===0||n===1){
return n
}else
return f(n-1)+f(n-2)
}
?f(100)時瀏覽器就會卡死（棧溢出）
另外，可以通過編寫一個方法計算js函數(shù)調用棧的最深層級的大小
function computeMaxCallStackSize() {
try {
return 1 + computeMaxCallStackSize();
} catch (e) {
// Call stack overflow
return 1;
}
}
computeMaxCallStackSize()
// 12531
改為尾調優(yōu)化的寫法
思路： 使用兩個臨時變量來存儲上一個值娘扩，和上上個值
function fTail(n, ac1=0, ac2=1){
if(n===0){
return ac1
}else
return fTail(n-1, ac2, ac1+ac2)
}
fTail(100)
// 354224848179262000000
fTail(1000)
// 4.346655768693743e+208
fTail(2000)
// Infinity
理論上，如果尾調優(yōu)化有效壮锻，上述代碼應該能一直計算(即使輸出Infinity)琐旁，但Chrome 72中實際測試表明大概計算到 fTail(7370) 時報錯 Maxinum call stack size exceeded
尾調優(yōu)化主要有兩點問題，導致它的提案仍沒有完全通過躯保，瀏覽器的支持也不統(tǒng)一：
- 在引擎層面進行尾調優(yōu)化是一個隱式行為旋膳，如果代碼存在死循環(huán)尾遞歸調用，可能因為優(yōu)化后沒有爆棧報錯提示而無法被程序員察覺
- 優(yōu)化后途事，調用堆棧信息會丟失验懊，造成調試困難
尾調優(yōu)化的瀏覽器支持可以參考http://kangax.github.io/compat-table/es6/#test-proper_tail_calls_(tail_call_optimisation)
改用循環(huán)重寫
所有遞歸都可以轉化為循環(huán)編寫
思路： 類似上一個例子擅羞，F(xiàn)ibonacci數(shù)列的實現(xiàn)使用循環(huán)還是比較簡單
function fLoop(n, ac1 = 0, ac2 = 1) {
while (n--) {
[ac1, ac2] = [ac2, ac1 + ac2]
}
return ac1
}
// 運行看看
fLoop(1000)
// 4.346655768693743e+208
fLoop(10000)
// Infinity
fLoop(100000)
// Infinity
?
可以看到改用循環(huán)重寫后，則不會引起調用棧溢出的問題
Trampolining（蹦床函數(shù)）
將遞歸改成循環(huán)义图，代碼可讀性降低减俏，比較難以理解，還有一種方式就是使用蹦床函數(shù)將遞歸改為循環(huán)
神馬是蹦床函數(shù)呢碱工？
function trampoline(f) {
while (f && f instanceof Function) {
f = f();
}
return f;
}
trampoline 方法中娃承，如果 f 是個函數(shù)就一直調用到返回不是函數(shù)為止，注意這種方式不是遞歸調用怕篷，而是循環(huán)历筝，不會增加調用棧。
我們試著把上邊的例子改寫成使用 Trampolining
function trampoline(f) {
while (f && f instanceof Function) {
f = f();
}
return f;
}
function fTrampoline (n, ac1=0, ac2=1){
if(n===0){
return ac1
}else{
return fTrampoline.bind(null, n-1, ac2, ac1+ac2)
}
}
// 結合兩個函數(shù)進行調用
trampoline(fTrampoline(10000))
// Infinity
這種方式寫法上和尾遞歸類似廊谓，但比較好理解梳猪，只是要修改原遞歸函數(shù)，underscore庫提供了蹦床函數(shù)用于將任意滿足它寫法的尾調遞歸轉化為循環(huán)蒸痹，避免爆棧問題：http://documentcloud.github.io/underscore-contrib/#trampoline
尾遞歸函數(shù)轉循環(huán)
還有一種方式春弥，可以將尾遞歸形式的遞歸函數(shù)轉為為循環(huán)，并且不需要修改原尾遞歸函數(shù)叠荠，即 非侵入式
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, ac1 = 0, ac2 = 1) {
if (n === 0) return ac1
return f(n - 1, ac2, ac1 + ac2)
})
f(10000)
// Infinity
?
可以看到匿沛，這其實是利用 閉包 緩存標記變量和 棧 存放每次遞歸的調用參數(shù)，每次發(fā)生遞歸調用就將本次調用參數(shù)push到棧內榛鼎，執(zhí)行后再shift 推出逃呼，直到棧為空。
小結
不管是利用 Trampolining 還是 tailCallOptimize 將遞歸轉化為循環(huán)借帘，都需要先將遞歸函數(shù)改為尾遞歸實現(xiàn)蜘渣，而并不是所有遞歸都可以轉化為尾遞歸，線性遞歸是比較容易進行轉化的肺然，而樹狀遞歸就難了，甚至可能無法轉化腿准。
查詢資料時就在思考际起，是否有一種方式可以嘗試將遞歸轉化為尾遞歸呢？然后找到了這篇：
基于CPS變換的尾調遞歸轉化算法
https://www.cnblogs.com/cheukyin/p/6444860.html
由于本人算法渣渣吐葱，就不搬運文章內容了街望，有興趣的可以點開進一步了解
在實際應用中，如果可以明確遞歸的層次不會太深的情況（比如線性遞歸不會超過1000層）弟跑，仍可以使用原始遞歸寫法灾前，或者某些情況下通過約束參數(shù)而避免爆棧的情況；
如果遞歸層次比較深孟辑，則需要優(yōu)化遞歸寫法為尾調遞歸哎甲，并利用類似 Trampolining 的方式轉化為循環(huán)調用蔫敲。
