目錄

• 目錄
  • 什麼是tail recursion
  • 各語言對於尾遞迴的優化
  • 參考資料

什麼是tail recursion

在尾遞迴(tail recursion)，會先計算，再呼叫自身(遞迴)

遞迴時，會將目前的計算結果傳給下一個遞迴，所以說function中的最後一個statement必是呼叫自身的遞迴(跟tailresum一樣)，

結果就是，只要準備好進入下一個遞迴階段，目前的stack frame就可以被拋棄掉了，

stack frame會為function提供執行環境，可以將其視為function scope，裡面會存些只存在於function scope的變數、參數...等，

因此進入下個遞迴階段前棄用目前的stack frame，有助於一些編譯器進行優化、減少記憶體用量，

記憶體用量過高和stack overflow有關，當call stack裝不下新的stack frame時，就會出現stack overflow，

而尾遞迴總是不斷拋棄stack frame，所以才說它降低stack overflow的機率

// 尾遞迴
function tailrecsum(x, running_total = 0) {
    if (x === 0) {
        return running_total;
    } else {
        return tailrecsum(x - 1, running_total + x);
    }
}

tailrecsum(5);

// stack frame的增長
// tailrecsum(5, 0)
// tailrecsum(4, 5)
// tailrecsum(3, 9)
// tailrecsum(2, 12)
// tailrecsum(1, 14)
// tailrecsum(0, 15)
// 15

// 一般遞迴
function recsum(x) {
    if (x === 0) {
        return 0;
    } else {
        return x + recsum(x - 1);
    }
}

recsum(5);

// stack frame的增長
// recsum(5)
// 5 + recsum(4)
// 5 + (4 + recsum(3))
// 5 + (4 + (3 + recsum(2)))
// 5 + (4 + (3 + (2 + recsum(1))))
// 5 + (4 + (3 + (2 + (1 + recsum(0)))))
// 5 + (4 + (3 + (2 + (1 + 0))))
// 5 + (4 + (3 + (2 + 1)))
// 5 + (4 + (3 + 3))
// 5 + (4 + 6)
// 5 + 10
// 15

來試用看看這兩個function

各語言對於尾遞迴的優化

在上一段發現了尾遞迴並不是無敵的

原來是因為有些編譯器沒有實作優化尾遞迴，或者優化得不夠好，所以還是會stack overflow、使用尾遞迴沒有比較好

像是Node.js針對尾遞迴的優化就比V8引擎好

所以即便V8引擎允許的stack frame上限(從1MB換算，約1萬個)遠多於Node.js則預設的1000個stack frame，從以下影片仍然可以發現在Chrome、Node.js上執行同個尾遞迴function的情況不太相同

再試試Rust，會發現它對尾遞迴的優化又海放前兩者

參考資料

What is tail recursion?
讓遞迴的Stack永遠不會爆炸的「尾遞迴」真的有那麼神奇嗎
Tail-Recursion Elimination on Conditional Types
A visualization of JavaScript runtime, callback queue and event loop and Web APIs.
Javascript 的事件循環 (Event Loop)、事件佇列 (Event Queue)、事件堆疊 (Call Stack)：排隊
What is the difference between callback queue and event queue?
了解Javascript 在網頁瀏覽器的運作原理