[译] ES6中的尾调用优化
原文：http://exploringjs.com/es6/ch_tail-calls.html
ECMAScript 6 提供了尾调用优化(tail call optimization)功能，以使得对某些函数的调用不会造成调用栈(call stack)的增长。本文解释了这项功能，以及其带来的好处。
1. 什么是尾调用优化?
粗略的来说，如果当一个函数所做的最后一件事是调用了另一个函数，而后者不需要向调用者返回任何东西时；以及由此可知，在这种情况下没有调用者的额外信息需要被储存在调用栈(call stack)上，函数间的调用更像一种goto跳转的时候 -- 这种调用就被称为尾调用(tail call)，此时使得内存栈不再增长的行为就成为尾调用优化(TCO - tail call optimization)。
举个例子来更好的理解下TCO。首先说明一下是否用TCO的区别：
function id(x) {
return x; // (A)
}
function f(a) {
const b = a + 1;
return id(b); // (B)
}
console.log(f(2)); // (C)1.1 正常的执行
假设有一个JS引擎通过 存储本地变量并返回栈上的地址 来管理方法调用。该引擎会如何执行上述代码呢？
Step 1. 最初，栈上只有全局变量id和f。
栈会对当前作用域的状态(包括本地变量、参数等)进行编码，形成被称为“调用帧”(frame)的一块。
Step 2. 在代码中的C行，f()被调用：首先，将要return到的位置被记录在栈中；然后f的参数a被分配并执行。
栈现在看起来是这样的：共有两个调用帧，一个是位于底部的全局作用域，另一个是其上方 的f()。
Step 3. id() 在B行中被调用。再次形成了一个调用帧，包含了id将要返回到的地址及其参数x被分配和调用的值。
Step 4. 在行A，结果x被返回。id的调用栈被移除，执行过程跳转到其调用帧中存储的要return的位置，也就是行B。(处理返回值有多种途径，最常见的两种是将结果留在栈中和在寄存器中处理之，此处按下不表)
栈现在是这副模样的了：
Step 5. 在行B中，从id中返回的值将继续返回给f的调用者。照旧，最上面的调用帧被移除，执行过程跳转到要return的位置 -- 行C。
Step 6. 行C接收到返回值3并完成打印工作。
1.2 尾调用优化
function id(x) {
return x; // (A)
}
function f(a) {
const b = a + 1;
return id(b); // (B)
}
console.log(f(2)); // (C)回顾上个章节的过程，其实 step 5 是多余的。行B中发生的全部事情其实只不过是把id()中返回的值传递给行C罢了。理想情况是，id()可以自行完成这一步，而跳过二传手 step 5。
可以通过对行B的函数调用采取不一样的实现方式来达成以上目的。栈在调用发生前是这样的：
检查这次调用就会发现，它是f()的最后一个行为。一旦id()完成，f()剩余执行的唯一行为就是把前者的结果返回给自身的调用者。因此，f中的变量就不需要了，其调用帧也就可以在这次调用之前被移除了。赋给id()的将要return地址直接可以是f的return地址，也就是行C了。在id()执行期间，栈看起来就是这样的：
id()返回了数值3，或者可以说它为f()返回了这个值；因为通过行C，该值被传递给了f的调用者。
不难发现，行B的函数调用就是一个尾调用。这样的调用可以在栈0增长的情况下完成。要判断函数调用是否是尾调用，必须检查其是否处于尾部(比如最后一个行为)。下一章节将讲述如何做到。
2. 检查函数调用是否在尾部发生
我们已经了解到尾调用可以被更有效率的执行，那么如何认定一个尾调用呢？
首先，调用函数的方式是无所谓的。下列调用如果出现在尾部，就都可以被优化：
- 函数调用:
func(···) - 方法调用:
obj.method(···) - 通过
call():func.call(···) - 通过
apply():func.apply(···)
2.1 表达式中的尾调用
箭头函数可以用表达式作为方法体。对于尾调用优化，因此必须找出表达式中函数调用的尾部。只有下列表达式会包含尾调用：
- 条件操作符 (
? :) - 逻辑或 (
||) - 逻辑与 (
&&) - 逗号 (
,)
分别来举例看一下：
2.1.1 条件操作符 (? :)
const a = x => x ? f() : g();f() 和 g() 都在尾部。
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()，而非f()的方法调用(调用者在其返回后又做了些什么)处于尾部。
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
}
};理由和逻辑或相同。
2.1.4 逗号 (,)
const a = () => (f() , g());依然是，f() 不在尾部，g() 在尾部：
const a = () => {
f();
return g();
}2.2 声明语句中的尾调用
对于声明语句，下列规则适用，只有这些混合声明语句会包含尾调用：
- 块 (用
{}界定，有时会有一个label) if: 包括逻辑上的 “then” 和 “else” 子句do-while,while,for: 在其循环体中switch: 在其判断体中try-catch: 只在catch子句中，try子句将catch子句作为上下文，导致无法被优化try-finally,try-catch-finally: 只在finally子句中，它会成为其他子句的上下文
对于所有原子(非混合)声明语句，只有return会包含尾调用。其他此类声明语句都有无法被优化的上下文。如下所示，当expr部分包含尾调用时，下列声明语句就包含尾调用。
return «expr»;2.3 尾调用优化只在严格模式下有效
在非严格模式下，大多数引擎会包含下面两个属性，以便开发者检查调用栈：
func.arguments: 表示对func最近一次调用所包含的参数func.caller: 引用对func最近一次调用的那个函数
在尾调用优化中，这些属性不再有用，因为相关的信息可能以及被移除了。因此，严格模式(strict mode)禁止这些属性，并且尾调用优化只在严格模式下有效。
2.4 单独的函数调用不算在尾部
下面的代码中，对bar() 的函数调用不算在尾部：
function foo() {
bar(); // this is not a tail call in JS
}原因在于foo()的最后一个动作不是对bar() 的函数调用，而是隐式的返回了undefined。换句话说，foo()的行为如下：
function foo() {
bar(); return undefined;
}调用者可以依赖一个总是返回undefined的foo()；但如果对bar()做了尾调用优化，那么其返回值就有可能改变了foo的行为。
因此，如果想要bar()成为一个尾调用，就得改成这样：
function foo() {
return bar(); // tail call
}3. 尾递归函数
如果一个函数的主递归调用发生在尾部，那这个函数就是尾递归。
譬如，下面的阶乘函数不是尾递归，因为行A中的主递归调用不在尾部：
function factorial(x) {
if (x <= 0) {
return 1;
} else {
return x * factorial(x-1); // (A)
}
}可以用一个辅助方法facRec()来使factorial()成为尾递归。行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)
}
}这样，一些非尾递归的函数就可以转化成尾递归了。
3.1 尾递归循环
尾调用优化使得在递归循环中不增长调用栈成为可能。下面举两个例子。
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. b3.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(end)