Tail Call Optimization

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

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

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

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.

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(···)

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

  Copy Code

  1const a = x => x ? f() : g();
  2// Both f() and g() are in tail position.

• The logical Or operator (||)
  js

  Copy Code

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

• The logical And operator (&&)
  js

  Copy Code

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

• The comma operator (,)
  js

  Copy Code

  1const a = () => (f() , g());
  2// f() is not in a tail position, but g() is in a tail position.
  3// To see why, take a look at the following code,
  4// which is equivalent to the previous code:
  5
  6const a = () => {
  7    f();
  8    return g();
  9}

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.

1return «expr»;

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.

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:

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

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

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

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

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

• forEach()

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

• findIndex()

1function findIndex(arr, predicate, start = 0) {
2    if (0 <= start && start < arr.length) {
3        if (predicate(arr[start])) {
4            return start;
5        }
6        return findIndex(arr, predicate, start+1); // tail call
7    }
8}
9findIndex(['a', 'b'], x => x === 'b'); // 1