Tail Call Optimization

目前只有 Safari 浏览器支持尾调用优化,Chrome 和 Firefox 都不支持。

Node.js 也不支持,因为 V8 不支持

Relate to https://exploringjs.com/es6/ch_tail-calls.html

What is tail call optimization?

Roughly, whenever the last thing a function does is to call another function then the latter does not need to return to its caller. As a consequence, no information needs to be stored on the call stack and the function call is more of a goto (a jump). This kind of call is named tail call; not growing the stack is named tail call optimization (TCO).

Let’s look at an example to better understand TCO. I’ll first explain how it is executed without TCO and then with TCO.

Checking whether a function call is in a tail position

First, the way in which you call a function does not matter. The following calls can all be optimized if they appear in a tail position:

  • Function call: func(···)
  • Dispatched method call: obj.method(···)
  • Direct method call via call(): func.call(···)
  • Direct method call via apply(): func.apply(···)

Tail calls in expressions

Arrow functions can have expressions as bodies. For tail call optimization, we therefore have to figure out where function calls are in tail positions in expressions. Only the following expressions can contain tail calls:

  • The conditional operator (? :)
    js
    1
    2
    const a = x => x ? f() : g();
    // Both f() and g() are in tail position.
  • The logical Or operator (||)
    js
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    const a = () => f() || g();
    // f() is not in a tail position, but g() is in a tail position.
    // To see why, take a look at the following code,
    // which is equivalent to the previous code:
    
    const a = () => {
        const fResult = f(); // not a tail call
        if (fResult) {
            return fResult;
        } else {
            return g(); // tail call
        }
    };
    // The result of the logical Or operator depends on the result of f(),
    // which is why that function call is not in a tail position (the caller does something with it other than returning it).
    // However, g() is in a tail position.
  • The logical And operator (&&)
    js
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    const a = () => f() && g();
    // f() is not in a tail position, but g() is in a tail position. 
    // To see why, take a look at the following code,
    // which is equivalent to the previous code:
    
    const a = () => {
        const fResult = f(); // not a tail call
        if (!fResult) {
            return fResult;
        } else {
            return g(); // tail call
        }
    };
    // The result of the logical And operator depends on the result of f(),
    // which is why that function call is not in a tail position (the caller does something with it other than returning it). 
    // However, g() is in a tail position.
  • The comma operator (,)
    js
    1
    2
    3
    4
    5
    6
    7
    8
    9
    const a = () => (f() , g());
    // f() is not in a tail position, but g() is in a tail position.
    // To see why, take a look at the following code,
    // which is equivalent to the previous code:
    
    const a = () => {
        f();
        return g();
    }

Tail calls in statements

For statements, the following rules apply.

Only these compound statements can contain tail calls:

  • Blocks (as delimited by {}, with or without a label)
  • if: in either the “then” clause or the “else” clause.
  • do-while, while, for: in their bodies.
  • switch: in its body.
  • try-catch: only in the catch clause. The try clause has the catch clause as a context that can’t be optimized away.
  • try-finally, try-catch-finally: only in the finally clause, which is a context of the other clauses that can’t be optimized away.

Of all the atomic (non-compound) statements, only return can contain a tail call. All other statements have context that can’t be optimized away. The following statement contains a tail call if expr contains a tail call.

js
1
return «expr»;

Tail call optimization can only be made in strict mode

In non-strict mode, most engines have the following two properties that allow you to examine the call stack:

  • func.arguments: contains the arguments of the most recent invocation of func.
  • func.caller: refers to the function that most recently called func.

With tail call optimization, these properties don’t work, because the information that they rely on may have been removed. Therefore, strict mode forbids these properties (as described in the language specification) and tail call optimization only works in strict mode.

Tail-recursive functions

A function is tail-recursive if the main recursive calls it makes are in tail positions.

For example, the following function is not tail recursive, because the main recursive call in line A is not in a tail position:

js
1
2
3
4
5
6
7
function factorial(x) {
    if (x <= 0) {
        return 1;
    } else {
        return x * factorial(x-1); // (A)
    }
}

factorial() can be implemented via a tail-recursive helper function facRec(). The main recursive call in line A is in a tail position.

js
1
2
3
4
5
6
7
8
9
10
function factorial(n) {
    return facRec(n, 1);
}
function facRec(x, acc) {
    if (x <= 1) {
        return acc;
    } else {
        return facRec(x-1, x*acc); // (A)
    }
}

That is, some non-tail-recursive functions can be transformed into tail-recursive functions.

Tail-recursive loops

Tail call optimization makes it possible to implement loops via recursion without growing the stack. The following are two examples.

  • forEach()
js
1
2
3
4
5
6
7
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}`));
  • findIndex()
js
1
2
3
4
5
6
7
8
9
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