原文:http://exploringjs.com/es6/ch_tail-calls.html
ECMAScript 6 提供了尾调用优化(tail call optimization)功能,以使得对某些函数的调用不会造成调用栈(call stack)的增长。本文解释了这项功能,以及其带来的好处。
粗略的来说,如果当一个函数所做的最后一件事是调用了另一个函数,而后者不需要向调用者返回任何东西时;以及由此可知,在这种情况下没有调用者的额外信息需要被储存在调用栈(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)
假设有一个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
并完成打印工作。
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增长的情况下完成。要判断函数调用是否是尾调用,必须检查其是否处于尾部(比如最后一个行为)。下一章节将讲述如何做到。
我们已经了解到尾调用可以被更有效率的执行,那么如何认定一个尾调用呢?
首先,调用函数的方式是无所谓的。下列调用如果出现在尾部,就都可以被优化:
func(···)
obj.method(···)
call()
: func.call(···)
apply()
: func.apply(···)
箭头函数可以用表达式作为方法体。对于尾调用优化,因此必须找出表达式中函数调用的尾部。只有下列表达式会包含尾调用:
? :
)||
)&&
),
)
分别来举例看一下:
const a = x => x ? f() : g();
f()
和 g()
都在尾部。
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()
的方法调用(调用者在其返回后又做了些什么)处于尾部。
const a = () => f() && g();
同样,f()
不在尾部,g()
在尾部:
const a = () => {
const fResult = f(); // not a tail call
if (!fResult) {
return fResult;
} else {
return g(); // tail call
}
};
理由和逻辑或相同。
const a = () => (f() , g());
依然是,f()
不在尾部,g()
在尾部:
const a = () => {
f();
return g();
}
对于声明语句,下列规则适用,只有这些混合声明语句会包含尾调用:
{}
界定,有时会有一个label)if
: 包括逻辑上的 “then” 和 “else” 子句do-while
, while
, for
: 在其循环体中switch
: 在其判断体中try-catch
: 只在 catch
子句中,try
子句将 catch
子句作为上下文,导致无法被优化try-finally
, try-catch-finally
: 只在 finally
子句中,它会成为其他子句的上下文对于所有原子(非混合)声明语句,只有return
会包含尾调用。其他此类声明语句都有无法被优化的上下文。如下所示,当expr
部分包含尾调用时,下列声明语句就包含尾调用。
return «expr»;
在非严格模式下,大多数引擎会包含下面两个属性,以便开发者检查调用栈:
func.arguments
: 表示对 func
最近一次调用所包含的参数func.caller
: 引用对 func
最近一次调用的那个函数
在尾调用优化中,这些属性不再有用,因为相关的信息可能以及被移除了。因此,严格模式(strict mode)禁止这些属性,并且尾调用优化只在严格模式下有效。
下面的代码中,对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
}
如果一个函数的主递归调用发生在尾部,那这个函数就是尾递归。
譬如,下面的阶乘函数不是尾递归,因为行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)
}
}
这样,一些非尾递归的函数就可以转化成尾递归了。
尾调用优化使得在递归循环中不增长调用栈成为可能。下面举两个例子。
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
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)