Fibonacci數列的實現 ~~~js function f(n){ if(n===0||n===1){ return n }else return f(n-1)+f(n-2) } ~~~ ?f(100)時瀏覽器就會卡死（棧溢出） 另外，可以通過編寫一個方法計算js函數調用棧的最深層級的大小 ~~~js function computeMaxCallStackSize() { try { return 1 + computeMaxCallStackSize(); } catch (e) { // Call stack overflow return 1; } } computeMaxCallStackSize() // 12531 ~~~ ### 改為尾調優化的寫法 思路： 使用兩個臨時變量來存儲上一個值，和上上個值 ~~~js 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 ~~~ 理論上，如果尾調優化有效，上述代碼應該能一直計算(即使輸出Infinity)，但Chrome 72中實際測試表明大概計算到 fTail(7370) 時報錯 Maxinum call stack size exceeded 尾調優化主要有兩點問題，導致它的提案仍沒有完全通過，瀏覽器的支持也不統一： * 在引擎層面進行尾調優化是一個隱式行為，如果代碼存在死循環尾遞歸調用，可能因為優化后沒有爆棧報錯提示而無法被程序員察覺 * 優化后，調用堆棧信息會丟失，造成調試困難 ### 改用循環重寫 所有遞歸都可以轉化為循環編寫 思路： 類似上一個例子，Fibonacci數列的實現使用循環還是比較簡單 ~~~js 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 ~~~ ? 可以看到改用循環重寫后，則不會引起調用棧溢出的問題 ### Trampolining（蹦床函數） 將遞歸改成循環，代碼可讀性降低，比較難以理解，還有一種方式就是使用蹦床函數將遞歸改為循環 神馬是蹦床函數呢？ ~~~js function trampoline(f) { while (f && f instanceof Function) { f = f(); } return f; } ~~~ trampoline 方法中，如果 f 是個函數就一直調用到返回不是函數為止，注意這種方式不是遞歸調用，而是循環，不會增加調用棧。 我們試著把上邊的例子改寫成使用 Trampolining ~~~js 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) } } // 結合兩個函數進行調用 trampoline(fTrampoline(10000)) // Infinity ~~~ 這種方式寫法上和尾遞歸類似，但比較好理解，只是要修改原遞歸函數，underscore庫提供了蹦床函數用于將任意滿足它寫法的尾調遞歸轉化為循環，避免爆棧問題：[http://documentcloud.github.io/underscore-contrib/#trampoline](http://documentcloud.github.io/underscore-contrib/#trampoline) ### 尾遞歸函數轉循環 還有一種方式，可以將尾遞歸形式的遞歸函數轉為為循環，并且不需要修改原尾遞歸函數，即 非侵入式 ~~~js 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 ~~~ ? 可以看到，這其實是利用 閉包 緩存標記變量和 棧存放每次遞歸的調用參數，每次發生遞歸調用就將本次調用參數push到棧內，執行后再shift 推出，直到棧為空。 ### 小結 不管是利用 Trampolining 還是 tailCallOptimize 將遞歸轉化為循環，都需要**先將遞歸函數改為尾遞歸實現**，而并不是所有遞歸都可以轉化為尾遞歸，線性遞歸是比較容易進行轉化的，而樹狀遞歸就難了，甚至可能無法轉化