如何避免 JavaScript 长递归导致的堆栈溢出？ #50

pfan123 · 2019-11-25T10:54:12Z

递归 (recursion) 是很多算法都使用的一种编程方法。

理解递归

假设我们要实现数学里面计算阶乘的例子，如：

1
2x1
3x2x1
4x3x2x1
5x4x3x2x1
6x5x4x3x2x1

第一种方法我们采用是 while 循环，累乘代码下去：

function factorial (number) {
  let result = 1
  while (number > 1) {
    result = result * number * (number - 1)
    number = number - 2
  }
  return result
}

第二种方法使用递归——函数调用自己，这种方法的伪代码如下.

function factorial (number) {
  if (number < 2) {
    return 1
  } else {
    return number * factorial(number - 1)
  }
}

这两种方法的作用相同，但第二种方法更清晰。递归只是让解决方案更清晰，并没有性能上的优势。实际上，在有些情况下，使用循环的性能更好。在 Stack Overflow 上说的一句话: “如果使用循环，程序的性能可能更高;如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。”

递归引起堆栈溢出

JavaScript 代码运行时，函数调用会在内存形成一个"调用记录"，又称"调用帧"（call frame），保存调用位置和内部变量等信息。如果在函数A的内部调用函数B，那么在A的调用记录上方，还会形成一个B的调用记录。等到B运行结束，将结果返回到A，B的调用记录才会消失。如果函数B内部还调用函数C，那就还有一个C的调用记录栈，以此类推。所有的调用记录，就形成一个"调用栈"（call stack）。

计算当前使用的JavaScript引擎可以支持多深的调用：

function computeMaxCallStackSize () {
  try {
    return 1 + computeMaxCallStackSize()
  } catch (e) {
    // Call stack overflow
    return 1
  }
}

由于递归函数的特点，导致如果边界检查存在缺陷，那么就可能导致超过这个最大深度，从而超出堆栈的存储能力，也就是所说的“内存溢出”，那遇到这种情况，则需求对递归进行优化，前面例子循环代替递归是一种解决方案，但除了这个方法之外也还有其他许多方法。

尾调用优化

函数调用自身，称为递归。如果尾调用自身，就称为尾递归。

递归非常耗费内存，因为需要同时保存成千上百个调用记录，很容易发生"栈溢出"错误（stack overflow）。但对于尾递归来说，由于只存在一个调用记录，所以永远不会发生"栈溢出"错误。

还是前面的例子，计算 number 的阶乘，最多需要保存 n 个调用记录，复杂度 O(n) 。

function factorial (number) {
  if (number < 2) {
    return 1
  } else {
    return number * factorial(number - 1)
  }
}

如果改写成尾递归，只保留一个调用记录，复杂度 O(1) 。

function factorial (number, result = 1) {
  if (number === 1) return result
  return factorial(number - 1, number * result)
}

由此可见，"尾调用优化"对递归操作意义重大，所以一些函数式编程语言将其写入了语言规格。ES6也是如此，第一次明确规定，所有 ECMAScript 的实现，都必须部署"尾调用优化"。这就是说，在 ES6 中，只要使用尾递归，就不会发生栈溢出，相对节省内存。

注意：

尾递归写法的函数在 Chrome 浏览器的控制台下依旧出现了调用栈溢出的异常，是因为 chrome 对尾递归调用（proper tail calls）不支持，可查看 ES6在各大平台上的兼容性。

Node V8 引擎实际上已经实现了尾调用优化，但是默认是关闭该功能的。执行 node --v8-options 可以找到一个启用尾调用优化的参数--harmony_tailcalls

“事件驱动” （Event-Driven）的特性

在 JavaScript 中，由于其 “事件驱动” （Event-Driven）的特性，使用 "setTimeout"、 “nextTick” 等方式对指定函数的调用，实际上是将该函数的引用（指针）储存起来，并在适当的时候调用。
换句话说，JavaScript 中， setTimeout、 nextTick 等方式调用的函数，并不会形成类似于递归那样， “一层套一层” 的调用链。下一次函数调用时，上一个 “父” 函数的调用已经执行完毕，就不会存在堆栈溢出的风险。

function factorial (number, result = 1) {
  if (number === 1) {
    console.log('result', result)
    return result
  }
  setTimeout(() => {
    factorial(number - 1, number * result)
  }, 0)
}

factorial(10000000)  // result Infinity