27. 尾端呼叫最佳化

ECMAScript 6 提供了尾端呼叫最佳化，您可以進行一些函式呼叫，而不會增加呼叫堆疊。本章節將說明它的運作方式和它帶來的優點。

警告：儘管尾端呼叫最佳化是語言規格的一部分，許多引擎並不支援，而且這可能永遠不會改變。

27.1. 什麼是尾端呼叫最佳化？
- 27.1.1. 一般執行
- 27.1.2. 尾端呼叫最佳化
27.2. 檢查函式呼叫是否在尾端位置
- 27.2.1. 表達式中的尾端呼叫
- 27.2.2. 陳述式中的尾端呼叫
- 27.2.3. 尾端呼叫最佳化只能在嚴格模式下進行
- 27.2.4. 陷阱：單獨的函式呼叫永遠不會在尾端位置
27.3. 尾端遞迴函式
- 27.3.1. 尾端遞迴迴圈

27.1 什麼是尾端呼叫最佳化？

大致上，只要函式執行的最後一件事是呼叫另一個函式，後者就不需要返回給它的呼叫者。因此，不需要在呼叫堆疊上儲存任何資訊，而函式呼叫更像是一個 goto（一個跳躍）。這種呼叫稱為尾端呼叫；不增加堆疊稱為尾端呼叫最佳化（TCO）。

讓我們看一個例子，以更了解 TCO。我將首先說明如何在沒有 TCO 的情況下執行它，然後再說明在有 TCO 的情況下執行它。

function id(x) {
    return x; // (A)
}
function f(a) {
    const b = a + 1;
    return id(b); // (B)
}
console.log(f(2)); // (C)

27.1.1 一般執行

讓我們假設有一個 JavaScript 引擎，它透過在堆疊上儲存局部變數和回傳位址來管理函式呼叫。這樣的引擎將如何執行程式碼？

步驟 1. 最初，堆疊上只有全域變數 id 和 f。

堆疊條目區塊編碼了當前範圍的狀態（局部變數，包括參數），稱為堆疊框架。

步驟 2. 在 C 行中，呼叫 f()：首先，將返回的位置儲存在堆疊上。然後，分配 f 的參數，並跳轉到它的主體。堆疊現在如下所示。

堆疊上現在有兩個框架：一個是全域範圍（底部），一個是 f()（頂部）。f 的堆疊框架包括回傳位址，C 行。

步驟 3. 在 B 行呼叫 id()。同樣地，會建立一個堆疊架構，其中包含回傳位址和 id 參數。

步驟 4. 在 A 行，回傳結果 x。移除 id 的堆疊架構，並跳轉執行至回傳位址，即 B 行。（有數種處理回傳值的方式。兩種常見的解決方案是將結果保留在堆疊中或在暫存器中傳遞。在此忽略執行的這部分。）

堆疊現在如下所示

步驟 5. 在 B 行，由 id 回傳的值會回傳給 f 的呼叫者。同樣地，會移除最上層的堆疊架構，並跳轉執行至回傳位址，即 C 行。

步驟 6. C 行接收值 3 並記錄它。

27.1.2 尾呼叫最佳化

function id(x) {
    return x; // (A)
}
function f(a) {
    const b = a + 1;
    return id(b); // (B)
}
console.log(f(2)); // (C)

如果您查看前一節，會發現有一個步驟是不必要的，即步驟 5。在 B 行發生的所有事情就是將 id() 回傳的值傳遞到 C 行。理想情況下，id() 本身就能執行此操作，而中間步驟可以省略。

我們可以透過以不同的方式實作 B 行中的函式呼叫來實現這一點。在呼叫發生之前，堆疊如下所示。

如果我們檢查呼叫，會發現它是 f() 中的最後一個動作。一旦 id() 完成，f() 執行的唯一剩餘動作就是將 id 的結果傳遞給 f 的呼叫者。因此，不再需要 f 的變數，而且可以在呼叫之前移除其堆疊架構。提供給 id() 的回傳位址是 f 的回傳位址，即 C 行。在 id() 執行期間，堆疊如下所示

然後 id() 回傳值 3。您可以說它為 f() 回傳該值，因為它將其傳遞到 f 的呼叫者，即 C 行。

讓我們回顧一下：B 行中的函式呼叫是尾呼叫。此類呼叫可以在堆疊成長為零的情況下完成。要找出函式呼叫是否為尾呼叫，我們必須檢查它是否位於尾端位置（即函式中的最後一個動作）。下一節將說明如何執行此操作。

27.2 檢查函式呼叫是否位於尾端位置

我們剛剛學到，尾端呼叫是可以更有效率執行的函式呼叫。但什麼算是尾端呼叫？

首先，呼叫函式的途徑並不重要。如果出現在尾端位置，下列呼叫都可以最佳化

函式呼叫：func(···)
派送方法呼叫：obj.method(···)
透過 call() 直接呼叫方法：func.call(···)
透過 apply() 直接呼叫方法：func.apply(···)

27.2.1 表達式中的尾端呼叫

箭頭函式可以有表達式作為主體。因此，對於尾端呼叫最佳化，我們必須找出函式呼叫在表達式中位於尾端位置的地方。只有下列表達式可以包含尾端呼叫

條件運算子 (? :)
邏輯或運算子 (||)
邏輯與運算子 (&&)
逗號運算子 (,)

讓我們來看每個運算子的範例。

27.2.1.1 條件運算子 (`? :`)

const a = x => x ? f() : g();

f() 和 g() 都在尾端位置。

27.2.1.2 邏輯或運算子 (`||`)

const a = () => f() || g();

f() 不在尾端位置，但 g() 在尾端位置。要了解原因，請看以下程式碼，它等同於前一個程式碼

const a = () => {
    const fResult = f(); // not a tail call
    if (fResult) {
        return fResult;
    } else {
        return g(); // tail call
    }
};

邏輯或運算子的結果取決於 f() 的結果，這就是為什麼該函式呼叫不在尾端位置（呼叫者對它執行的動作不只是傳回它）。不過，g() 在尾端位置。

27.2.1.3 邏輯與運算子

const a = () => f() && g();

f() 不在尾端位置，但 g() 在尾端位置。要了解原因，請看以下程式碼，它等同於前一個程式碼

const a = () => {
    const fResult = f(); // not a tail call
    if (!fResult) {
        return fResult;
    } else {
        return g(); // tail call
    }
};

邏輯與運算子的結果取決於 f() 的結果，這就是為什麼該函式呼叫不在尾端位置（呼叫者對它執行的動作不只是傳回它）。不過，g() 在尾端位置。

27.2.1.4 逗號運算子 (`,`)

const a = () => (f() , g());

f() 不在尾端位置，但 g() 在尾端位置。要了解原因，請看以下程式碼，它等同於前一個程式碼

const a = () => {
    f();
    return g();
}

27.2.2 陳述式中的尾端呼叫

對於陳述式，適用下列規則。

只有下列複合陳述式可以包含尾端呼叫

區塊（以 {} 分隔，有或沒有標籤）
if：在「then」子句或「else」子句中。
do-while、while、for：在它們的主體中。
switch：在主體中。
try-catch：僅在 catch 子句中。try 子句具有 catch 子句作為無法最佳化的內容。
try-finally、try-catch-finally：僅在 finally 子句中，這是無法最佳化的其他子句的內容。

在所有原子（非複合）陳述中，只有 return 可以包含尾呼叫。所有其他陳述都有無法最佳化的內容。如果 expr 包含尾呼叫，則下列陳述包含尾呼叫。

return «expr»;

27.2.3 尾呼叫最佳化只能在嚴格模式中進行

在非嚴格模式中，大多數引擎具有以下兩個屬性，允許您檢查呼叫堆疊

func.arguments：包含 func 最近一次呼叫的自變數。
func.caller：指最近呼叫 func 的函式。

使用尾呼叫最佳化時，這些屬性無法運作，因為它們依賴的資訊可能已移除。因此，嚴格模式禁止這些屬性（如語言規範中所述），而尾呼叫最佳化僅在嚴格模式中運作。

27.2.4 陷阱：單獨函式呼叫從不在尾部位置

下列程式碼中的函式呼叫 bar() 不在尾部位置

function foo() {
    bar(); // this is not a tail call in JS
}

原因是 foo() 的最後動作不是函式呼叫 bar()，而是（隱式）傳回 undefined。換句話說，foo() 的行為如下

function foo() {
    bar();
    return undefined;
}

呼叫者可以依賴 foo() 始終傳回 undefined。如果 bar() 要傳回 foo() 的結果，由於尾呼叫最佳化，這將會改變 foo 的行為。

因此，如果我們希望 bar() 成為尾呼叫，我們必須變更 foo() 如下。

function foo() {
    return bar(); // tail call
}

27.3 尾遞迴函式

如果函式的主要遞迴呼叫位於尾部位置，則此函式為尾遞迴。

例如，下列函式並非尾遞迴，因為 A 行中的主要遞迴呼叫並非位於尾部位置

function factorial(x) {
    if (x <= 0) {
        return 1;
    } else {
        return x * factorial(x-1); // (A)
    }
}

factorial() 可透過尾遞迴輔助函式 facRec() 來實作。A 行中的主要遞迴呼叫位於尾部位置。

function factorial(n) {
    return facRec(n, 1);
}
function facRec(x, acc) {
    if (x <= 1) {
        return acc;
    } else {
        return facRec(x-1, x*acc); // (A)
    }
}

也就是說，有些非尾遞迴函式可以轉換為尾遞迴函式。

27.3.1 尾遞迴迴圈

尾呼叫最佳化讓你可以透過遞迴來實作迴圈，而不會增加堆疊。以下有兩個範例。

27.3.1.1 `forEach()`

function forEach(arr, callback, start = 0) {
    if (0 <= start && start < arr.length) {
        callback(arr[start], start, arr);
        return forEach(arr, callback, start+1); // tail call
    }
}
forEach(['a', 'b'], (elem, i) => console.log(`${i}. ${elem}`));

// Output:
// 0. a
// 1. b

27.3.1.2 `findIndex()`

function findIndex(arr, predicate, start = 0) {
    if (0 <= start && start < arr.length) {
        if (predicate(arr[start])) {
            return start;
        }
        return findIndex(arr, predicate, start+1); // tail call
    }
}
findIndex(['a', 'b'], x => x === 'b'); // 1

下一篇：28. 使用代理進行元程式設計