尾调用及递归优化

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){...}          |
|                                     |
+-------------------------------------+
  • 函数 greturn 进行返回后,因为 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

相关资源