尾递归

使用递归的一个潜在缺陷是可能会导致栈溢出。当处理非常大的嵌套数组时，递归调用会不>断增加调用栈的深度，最终可能导致栈溢出错误。

维护栈的成本比直接遍历更大

在日常开发中，经常会遇到递归相关的操作，而且递归写起来更加容易理解并且得心应手，例如下面这个求和的递归。

function sum(n) {
  if (n === 0) return n;
  return n + sum(n - 1);
}

const result = sum(100);

console.log(result); // 5050

但是递归虽然写起来简单，同时容易理解，但也会伴随着风险。对于递归而言，这类风险就是‘栈溢出’。由于递归需要不断的调用自己，需要同时保存成百上千的调用栈，所以很容易发生栈溢出。如下图所示，在上面的求和函数中，每调用一次，就会在调用栈中记录一个 sum，而当计算量过大时，便会发生下面的栈溢出

尾递归

尾递归，顾名思义，就是在递归调用执行在尾部，例如下面这个例子。这里同样是一个求和的递归函数，但这里的递归与上面的递归有所不同，下面的例子将求和值放入了函数的参数，

对于 sum 函数而言，不存在需要记录的内部变量，所以不需要保存其栈帧，所以能够减小其调用栈和内存占用。

但是实践中发现

尾递归将普通递归中的参数放到了 total 进行保存，所以在尾递归中，不存在任何需要保存的变量，那么实际上呢，这里我们利用 vscode 来调试。可以看到，对于 sum 这个函数而言，存在 arguments 和 caller，或许这就是导致我们调用尾递归失败的原因。到这里，熟悉 js 的小伙伴可能很快就明白了，我们可以利用严格模式来禁止这两个属性，在严格模式下，这两个属性是禁用的。我们开启严格模式下重新尝试调用尾递归

function sum(n, total) {
  "use strict";
  if (n === 0) return total;
  return sum(n - 1, total + n);
}

成功调用了尾递归，使得在递归时的调用栈不会溢出

实现尾递归

经过上面的讨论，我们知道，目前无论是 node 还是浏览器，明面上都不支持尾递归，需要在严格模式下，那么这对于在用户端使用是不现实的。那么我们有没有办法去自己实现一个尾递归的方法呢。这是当然可以的，下面就是实现一个支持尾递归的函数。

扩展

熟悉 nodejs 的同学知道 nextTick 能将调用栈展开，相应的就不会触发栈溢出，那么我们同样可以依靠这个特性来实现不会栈溢出的“递归”(不推荐用于业务代码)，代码如下所示。

function sum(n) {
  return new Promise((resolve) => {
    if (n === 0) return resolve(n);
    process.nextTick(() => {
      sum(n - 1).then((result) => {
        resolve(n + result);
      });
    });
  });
}

sum(10000000).then((result) => {
  console.log("result", result);
});

虽然 nextTick 不会导致栈溢出，但是内存占用还是会不断增加，如果递归特别深的话会一直递归，直到触发 oom。

参考 https://github.com/ruanyf/es6tutorial/blob/cee42e6227cf3ded43f89b598b2f840d3ccf1e77/docs/function.md#%E5%B0%BE%E9%80%92%E5%BD%92 https://www.cnblogs.com/xiaoqifeng/p/11744062.html

尾递归

尾递归​

实现尾递归​

扩展​

尾递归

实现尾递归

扩展