什么是尾递归？为什么那么优雅？

尾递归是个好东西。

今天我使用通俗的话，来讲讲。

递归的好处是，可以让代码看着非常干净和安全。

而且阅读起来也更加的舒服。毕竟其实很多问题，它的逻辑天然就是递归的。

虽然现在 AI 时代了，但是我偶尔还是喜欢手写一些代码，感受代码的优雅。

先从一个最简单的代码开始，就是从 1 到 n ，算出所有的整数的和。

// 计算所有的整数和
function sum(n) {
  if (n === 0) {
    return 0;
  }

  return n + sum(n - 1);
}

let answer = sum(10);

console.log(answer);

函数里面嵌套函数，是不是非常的漂亮！

但是！

有一个问题，就是如果我不是 sum(10) , 而是 sum(999999999) 呢？

先别那么多 9 了，就 sum(100000) 都计算不了，都报错 Uncaught RangeError: Maximum call stack size exceeded 。

每次执行的时候，都会在栈上留下一个 sum 。这个空间是有限的，因此，会报错。这个是物理限制，告诉你没有空间了。

尾递归

于是需要尾递归来优化。

function sumTR(n, acc) {
  if (n === 0) {
    return acc;
  }

  return sumTR(n - 1, acc + n);
}

let answer = sumTR(10, 0);

console.log(answer);

哈哈，看懂了吗？

太美了。

脑子在看这个代码的时候，就好像人掉入了一个无限的虫洞，首尾上下照应，离的很近，靠人的重力去穿越一样，一环环的进入。直到 n === 0 ，啪，return 了。

这样的好处是，运行时，计算的总数，是保存在 acc 这个变量里的，而不是 函数 堆里。

浏览器不支持尾递归！！！

但是！！！！！

理论上，在 浏览器 上运行时，sumTR(1000000, 0); 没问题，可是依然报错了。

发生了什么？？？？

原来 浏览器 竟然不支持 尾递归！

查一下资料发现，现在的 JS 运行时都不支持 尾递归。其他大部分程序语言都支持。

那怎么办？

那就只能放弃尾递归了。

比如直接了当的写：

function sumIter(n) {
  let acc = 0;
  for (let i = n; i > 0; i--) acc += i;
  return acc;
}

sumIter(1000000); // 不报错
sumIter(10000000000);  // 依然不报错，但是会有点慢

尾递归那么好。可惜 JS 都不支持。

当然也可以不放弃，研究了一下，发现可以使用蹦床模式。

曲线救国，使用 蹦床模式 ，这个时候你会惊讶的发现，尾递归 竟然有效了！

function trampoline(fn) {
  while (typeof fn === "function") {
    fn = fn();
  }
  return fn;
}

function sum(n, total = 0) {
  if (n === 0) {
    return total;
  }

  return () => sum(n - 1, total + n);
}

trampoline(() => sum(1000000));  // 不报错
trampoline(() => sum(10000000000));  // 依然不报错，但是会有点慢

为什么这样就可以使用尾递归了呢？

按照 Your Recursion Is Lying to You文章的说法：

【如果你想为了可读性保留递归结构，但又需要避免栈增长，可以使用蹦床：一个循环，反复调用一个函数，该函数要么返回最终结果，要么返回另一个要调用的函数。蹦床以额外的函数分配和调度开销换取栈安全，因此当保留递归结构比原始性能更重要时，它们最有用。】

也就是说，它是自己用 while 循环，模拟了原本希望 JS 引擎帮你做的事情。

JS 引擎为了栈安全，所以不允许直接把递归变成循环。。。 但是只要我们套一个循环，使用我们自己的方式把递归给转为循环，那么它就管不到了。