自幹 JavaScript 的 Tail Call Optimization

ECMAScript 6 開始，規範中出現了一項被稱為「尾呼叫優化（Tail Call Optimization, TCO）」的優化技術，這讓開發者可以在函數的執行過程中，減少 Stack Frame 的數量，進而提升效能。TCO 尤其是在遞迴這種不停呼叫自己或新函數的工作上，能得到最大的優化效益，能提升遞迴的執行效能如同迴圈一樣。

只不過很可惜的是，截至本文發稿前，大多數瀏覽器及 JavaScript 引擎尚未支援這項技術。但我們還是可以自幹並模擬一個 TCO 的行為，雖然比起語言本身、編譯器（Compiler）及虛擬機（VM）層面的實現，效果差了些，但仍然可以減少 Stack Frame 的數量避免達到 Stack Frame 的數量上限。

什麼時候會啟用尾呼叫優化機制？

如果 JavaScript 引擎有支援，通常一個函數執行到最後一行 return 時，是回傳另一個函數的執行結果，就會啟用 TCO 機制，如：

const f = () => {
    return 999;
};

const g = () => {
    // 執行並直接回傳 f 函數的執行結果：會啟用尾呼叫優化機制
    return f();
};

g();

但要注意的是，回傳的「必定為函數的直接回傳值」，所以下面這些寫法不會啟用 TCO 機制：

// 不會啟用 TCO 機制的設計
const g = () => {
    return f() + 1;
};

// 不會啟用 TCO 機制的設計
const g = () => {
    let ret = f();

    return ret;
};

創造一個跑不完的函數

首先我們先創造一個肯定跑不完的遞迴，然後改善它：

const func = (x) => {

    // 讓他跑 10000000 次
    if (x === 10000000)
        return x;

    return func(x + 1);
};

let ret = func(0);

理論上，如果你直接執行上述程式碼，會得到 stack size 超過上限的錯誤訊息：

RangeError: Maximum call stack size exceeded

簡單模擬實現自己的 TCO 效果

簡單來說，尾呼叫優化對開發者最主要的效果，就是避免每次呼叫函數時，就產生一個新的 Stack Frame，所以這是我們實現的主要訴求。而我們可以實現的作法，是讓函數的遞迴呼叫轉換成迴圈形式執行，避免不斷增加 Stack Frame，使遞迴可以無窮的跑下去。

我們可以創造一個閉包，來包裝我們的函數：

const tco = (fn) => {

    return (...args) => {

        let f = fn.bind(this, ...args);

        // 每次執行函數後，若得到的回傳值是函數物件，則繼續執行下去
        while(f instanceof Function) {
            f = f();
        }

        // 沒有需要繼續執行的函數，回傳結果
        return f;
    }
};

然後，我們用此閉包把待優化的函數包裝起來，並做點修改：

const func = (x) => {

    // 讓他跑 10000000 次
    if (x === 10000000)
        return x;

    // 不直接執行函數，改為綁定參數後產生並回傳一個函數物件
    return func.bind(this, x + 1);
};

// 包裝我們的遞迴函數
const improvedFunc = tco(func);

// 執行方法和舊函數一樣
let ret = improvedFunc(0);

執行優化後的函數，就不會再出現 stack size 的錯誤了。

自己自幹的限制

需要一提的是，在我們自己實現的版本中，我們無法做到合併所有的 Stack，也無法減少函數的來回跳轉數量，這些是屬於虛擬機和語言層面才能做到的設計。

使用遞迴時要注意事件引擎鎖死的問題

要記得，雖然 TCO 可以解決 stack size 上限的問題，但 JavaScript 仍然依賴著事件引擎，而密集運算會造成事件引擎鎖死，所以在一般的應用中，我們應該避免運用太深的遞迴，除非你確定你的應用程式沒有其他需要事件機制的地方，或是真的要拿 JavaScript 做密集運算的工作。

後記

一如程式語言的發展趨勢，所有現代化的程式語言都向 Functional Programming 靠攏。考量到為了讓函數可以無窮的遞迴執行下去，尾呼叫優化（Tail Call Optimization, TCO）就是一個重要的機制。