尾调用及递归优化
尾调用及递归优化
ES6 规范中添加了对尾调用优化的支持，虽然目前来看支持情况还不是很好，但了解其原理还是很有必要的，有助于我们编写高效的代码，一旦哪天引擎支持该优化了，将会收获性能上的提升。
讨论尾调用前，先看函数正常调用时其形成的堆栈（stack frame）情况。
函数的调用及调用堆栈
先看一个概念：调用堆栈（call stack），或叫调用帧（stack frame）。
我理解的调用堆栈：因为函数调用后，流程会进入到被调用函数体，此时需要传入一些入参，这些入参需要存放到一个位置，另外当函数调用结束后，执行流程需要返回到被调用的地方，这个返回的地方也需要被记录下来。所以会为这次函数调用分配一个存储区域，存放调用时传入的入参，调用结束后返回的地址。这个存储区域保存的都是跟本次函数调用相关的数据，所以，它是该函数的调用堆栈。
考察下面的示例代码：
function g(x) {
return x; // (C)
}
function f(a) {
let b = a + 1;
return g(b); // (B)
}
console.log(f(2)); // (A)
下面模拟 JaavScript 引擎在执行上面代码时的流程，
- 首先对于全局作用域来说，存在两个字面量（不算上全局 window）
f,g，所以一开始执行时，已经默认有一个全局的堆栈信息了，看起来大概是这样子：
+-------------------------------------+
| |
| f=function(a){...} |
| g=function(x){...} |
| |
+-------------------------------------+
- 调用
f(2)并生成调用堆栈，代码执行流程进入f的函数体中。形成了第一个 stack frame，里面有f(2)入参a，函数体中声明的变量b以及被调用的位置 A。此时的堆栈是下面的样子：
+-------------------------------------+
| |
| a=2 |
| b=2+1 |
| Line A |
| |
+-------------------------------------+
| |
| f=function(a){...} |
| g=function(x){...} |
| |
+-------------------------------------+
- 在函数
f的函数体中，调用g代码流程进入g的函数体，同样，为其生成相应的调用堆栈，保存入参x，调用位置B。
+-------------------------------------+
| |
| x=3 |
| Line B |
| |
+-------------------------------------+
| |
| a=2 |
| b=2+1 |
| Line A |
| |
+-------------------------------------+
| |
| f=function(a){...} |
| g=function(x){...} |
| |
+-------------------------------------+
- 函数
g中return进行返回后，因为g已经完成使命，其相关的调用堆栈被销毁。代码执行流程回到g被调用的地方A，相当于代码执行流程回到了f函数体中。此时的堆栈是这样的：
+-------------------------------------+
| |
| a=2 |
| b=2+1 |
| Line A |
| |
+-------------------------------------+
| |
| f=function(a){...} |
| g=function(x){...} |
| |
+-------------------------------------+
f函数体中拿到g的返回后，什么也没干，直接return返回，此时结束了f的执行，流程回到f被调用的地方 A，即流程回到全局作用域，销毁f的调用堆栈。此时的堆栈为：
+-------------------------------------+
| |
| f=function(a){...} |
| g=function(x){...} |
| |
+-------------------------------------+
- 全局作用域中，得到返回值后将其打印输出结束了整段代码。
尾调用
如果一个函数最后一步是调用另一个函数，则这个调用为尾调用。比如：
function g(x) {
return x;
}
function f(y) {
var a = y + 1;
return g(a);
}
但下面这个就不算尾调用了：
function g(x) {
return x;
}
function f(y) {
var a = y + 1;
return g(a) + 1;
}
因为这里 f 中最后一步操作并不是对 g 的调用，在拿到 g 函数的返回后还进行了另外的操作 g(a)+1。其代码相当于如下的形式：
function g(x) {
return x;
}
function f(y) {
var a = y + 1;
var tmp = g(a);
var result = tmp + 1;
return result;
}
经过改造后就能很明显看出，其中对 g 的调用不是尾调用了。
尾调用的判定
函数的调用形式
首先，JavaScript 中调用函数是多样的，只要这是另一函数中最后一步操作，都可称作尾调用。比如以下的函数调用形式：
- 正常函数调用：
fn(...) - 访问对象属性并调用：
obj.method(...) - 通过
Function.prototype.all调用：fn.call(...) - 通过
apply调用：fn.apply(...)
表达式中的尾调用
因为箭头函数的函数体可以是表达式，所以表达式最终的步骤是什么决定了该箭头函数中是否包含尾调用。
能够形成尾调用的表达式有如下这些，
- 三元表达式：
?:
const a = x => x ? f() : g();
其中 f() 和 g() 都是尾调用，表达式最终结果要么是对 f() 的调用，要么是对 g() 的调用。
- 逻辑或表达式：
||
const a = () => f() || g();
上面示例中， f() 不是尾调用，而对 g() 的调用是尾调用。这点可通过下面转换后的等效代码看出来：
const a = () => {
let fResult = f(); // not a tail call
if (fResult) {
return fResult;
} else {
return g(); // tail call
}
};
a||b 的意思是如果 a 真则返回 a 的值，否则继续判定 b，此时无论 b 真假与否，整个表达式的返回都是 b。
所以从上面的转换中看出，对于 f() 的调用，需要进一步对其返回值进行处理，而不是直接将 f() 进行返回，所以 f() 并不是函数体中最后一步操作，但 g() 是，因为对于 g() 的返回值没有其他操作，而是直接返回。
- 逻辑与表达式：
&&
const a = () => f() && g();
与逻辑或表达式雷同，这里需要对 f() 的返回值进一步处理，进行判定后决定整个表达式的执行，所以 f() 不是尾调用，而 g() 是。 其等效的代码如下：
const a = () => {
let fResult = f(); // not a tail call
if (!fResult) {
return fResult;
} else {
return g(); // tail call
}
};
- 逗号表达式：
expression，expression
const a = () => (f() , g());
这个就比较好理解了，逗号表达式是依次执行的，整个表达式返回结果为最后一个表达式。所以这里 f() 不是尾调用，g() 是。
需要注意的是，单独的函数调用并不是尾调用，比如下面这样：
function foo() {
bar(); // this is not a tail call in JS
}
这里 bar() 并不是尾调用，因为函数体中，最后一步操作并不是返回 bar()，而是隐式地返回 undefined。其等效的代码为：
function foo() {
bar();
return undefined;
}
像这种情况其实并不能简单地通过加一个 return 将其变成尾调用。因为这样就改变了 foo 的返回值，其功能有可能就变了，调用方就不能再依赖于 foo() 返回的是 undefined。
尾调用优化
回到最开始的那个示例：
function g(x) {
return x; // (C)
}
function f(a) {
let b = a + 1;
return g(b); // (B)
}
console.log(f(2)); // (A)
这里 f(a) 中就包含一个尾调用 g(b)。并且通过前面的调用堆栈的分析，可以知道，每一次函数调用都需要生成相应的调用堆栈，会有存储的开销。
如果仔细看前面调用过程的分析，会发现，在 f(a) 函数体中，当我们调用 g(b) 时，就可以将 f(a) 的调用堆栈直接销毁了，其中 f(a) 相关的内容不会再被用到，除了其中关于 f(a) 被调用位置的记录。这个位置需要在调用 g(b) 后返回。
所以，完全可以省掉 f(a) 作为中间商这一步，将 f(a) 反返回地址告诉 g(x)，这样 g(x) 在执行完成后直接返回到代码中 A 标记处。
上面优化后的执行场景下，其调用堆栈的分配则变成了：
- 调用
f(2)，为其分配堆栈 - 调用
g(b)，为其分配堆栈。同时发现g(b)在f(a)的末尾直接被返回，f(a)中存储的变量b这些在后续执行中不会再被用到，将f(a)的调用堆栈销毁。 - 执行
g(b)并返回到A标记处。
最最开始不同之处在于，在创建 g(b) 的调用堆栈时，同时销毁了 f(a) 的调用堆栈。这当然是 JavaScript 引擎去实现的。
其好处显而易见，在函数连续调用过程中，堆栈数没有增加。假如不止一次尾调用， g(x) 中还存在对另外函数的尾调用，这样的优化可以持续下去，也就是说，堆栈数并没有随着函数调用的增多而增加。
利用这个特性，我们可以将一些不是尾调用的函数想办法改成尾调用，达到优化调用堆栈的目的，这便是尾调用优化。
尾递归调用
如果函数的尾调用是对自己的调用，便形成了递归调用，又因为同时还是尾调用，所以合称 尾递归调用。相比于传统的递归，调用堆栈极速增加的不同，尾递归调用的调用堆栈是恒定的，这由前面的分析可知。
所以尾调用优化特别适合用于递归的情况，收益会很大。
计算阶乘就是典型的递归场景：
function factorial(x) {
if (x <= 0) {
return 1;
} else {
return x * factorial(x-1); // (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)
}
}
此时 facRec 便是一个尾递归调用。
其他示例
利用尾递归调用实现循环语句。
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