浅谈尾递归和尾调用

引言

之前在学习 JS 中 Promise 的时候，随便找了一个某厂相关的面试题来练手。

找到的题目很简单，要求是用 Promise 来实现红绿灯的功能，无限循环。但当看到那个样例代码的时候，我陷入了深深的沉思：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function light() {
  new Promise((resolve, reject) => {
    setTimeout(() => {
      console.log('红');
      resolve();
    }, 1000);
  })
    .then(() => {
      return new Promise((resolve, reject) => {
        setTimeout(() => {
          console.log('绿');
          resolve();
        }, 1000);
      });
    })
    .then(() => {
      return new Promise((resolve, reject) => {
        setTimeout(() => {
          console.log('黄');
          resolve();
        }, 1000);
      });
    })
    .then(() => {
      return light();    // ???????????????????
    });
}

light();

这个过程其实是简单而且优雅的，但是最后那一句 return light() 是什么鬼！

无限地调用自己，短期内看上去相当可行。但运行时间长的话，确定不会栈溢出或者起码浪费资源吗？

我内心里一直有上述这样的疑问，直到我了解到了“尾调用” (Tail Calls) 这一机制。

尾调用 & 尾递归

为什么需要尾调用优化

为了解决递归时调用栈溢出的问题，除了把递归函数改为迭代之外，改为尾递归的形式也可以解决。

注意⚠️

在 Node 6、Node 7 中可以使用命令行参数 --harmony-tailcalls 开启尾递归优化功能。但是这个特性已经被 V8 移除了，对应的 Node 8 之后的版本都已经没有了尾递归优化功能。在 Chrome 之前的某些版本确实可以通过 chrome://flags/#enable-javascript-harmony 开启，但是也已经被移除了。因为尾递归优化会破坏函数的调用栈信息，TC39 也正在寻找新的 JS 语法来显式指明需要使用尾递归优化。

事实上，在 JavaScript 世界中，尾调用只短暂地被 Node.js 支持过，但后来都由于技术原因而被废弃。到目前为止，只有 Safari 这一浏览器支持“尾调用优化” (Tail Call Elimination)，而无论是 Chrome 中的 V8、还是 Node.js 都还不支持。2016 年的 TC39 提案中，有关于这一点的公开讨论，一些开发人员仍强烈希望在 JavaScript 中支持 PCE。

尾调用优化目前还是 Stage 0 Draft 阶段，但是我们有理由相信在不久的将来这个一定会进入 ES 标准。即使目前大部分浏览器没有对尾递归 (尾调用) 做优化、依然会导致栈溢出，了解尾递归的优化方式还是很有价值的。

回归正文

当函数 func1 的最后一个动作是调用函数 func2 时，那么对函数 func2 的调用形式就是尾调用。例如：

1
2
3
4
5
6
7
8
9
10
11
const func2 = (a) => {
  let b = a + 1;
  return b;
}

const func1 = (x) => {
  let y = x + 1;
  return func2(y);
}

const result = func1(1);

在尾调用优化的模式下，执行该段代码的步骤就是：

  1. 执行函数 func1(1)，将其压入调用栈 (call stack) 中。

  2. 先运行完 func1 的主体部分，在执行到 return func2(y) 时，

    func1 的调用即可以出栈，并把对调用 func1 的信息传给 func2。

  3. 然后把 func2(y) 以及来自 func1 的信息，压入调用栈，

    最后在 func2 执行完成之后，把 func2 的结果返回到当初执行 func1 的那一步。

按照以上步骤，在执行 fun1 和 func2 时，始终只占用一个调用栈。

如果是在递归的环境下也只需一个调用栈，这样便大大减小了调用栈的大小。

什么是尾调用 (尾递归)

尾调用就是函数的最后一步是执行一个函数的过程，而尾递归就是通过尾调用来完成的递归过程。

譬如，形如以下代码的都是尾调用：

1
2
3
const a = () => {
  return b();
}

而下面代码，并不是尾调用

1
2
3
const a = () => {
  b();
}

原因是 b() 之后还隐式地执行了一段 return undefined，所以其最后一步并不是调用一个函数。

同理，如果我们要写一个计算阶乘的程序，按照以下方式进行编写

1
2
3
4
5
6
function fac(n) {
  if (n === 1) return 1;
  return n * fac(n - 1);
}

fac(5);

这样并不是尾调用，

因为函数 fac(n) 中，程序在执行完 fac(n-1) 的函数调用之后，还需取回值来进行乘法运算。所以程序需要保留 fac(n) 的调用栈，以便在获得值之后相乘。

我们可以通过一下代码，将其转为尾递归的写法：

1
2
3
4
5
6
function fac(n, total) {
  if (n === 1) return total;
  return fac(n - 1, n * total);
}

fac(5, 1);

然而

其实，尾调用就是给数据处理提供一个新的方式。

而递归通常能被写成迭代的方式，因为在目前的 V8、Node.js 等环境都还不支持尾调用 (可以通过这个网站查看”尾调用优化“的支持情况)，我们可以通过将尾递归改写成循环，来实现节省空间的目的。

Trampoline 是对尾递归函数进行处理的一种技巧。对于一段累加的代码：

1
2
3
4
const sum = (n, prevSum = 0) => {
  if (n <= 1) return n + prevSum;
  return sum(n-1, n + prevSum)
}

我们可以先把上面的 sum 函数改造一下，再由 trampoline 函数处理即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const sum0 = (n, prevSum = 0) => {
  if (n <= 1) return n + prevSum;
  return () => sum0(n-1, n + prevSum)
}
const trampoline = f => (...args) => {
  let result = f(...args);
  while (typeof result === 'function') {
    result = result();
  }
  return result;
}

const sum = trampoline(sum0);
console.log(sum(1000000));     // 不会栈溢出

可以看到，这里实际上就是把原本的递归改成了迭代，这样就不会有栈溢出的问题啦。

虽然递归理论上都能改写为迭代，但有些场景下使用递归可能会更加直观。如果一个递归能被转为”尾递归“，你就可以间接地用 trampoline 函数进行处理，或者把它改写成迭代的方法。