尾递归

尾递归

1. 什么是尾递归？

尾递归，即在函数尾位置调用自身（或尾调用本身的其他函数等）。尾递归是递归的一种特殊情形，是在尾部直接调用自身的递归函数。

2. 为什么需要尾递归？

在普通递归调用过程中，系统会为每一层的返回点、局部变量等开辟栈来存储，递归次数过多容易造成栈溢出。

尾递归由于只存在一个调用记录，所以永远不会发生"栈溢出"错误——但前提是引擎真正实现了尾调用优化（TCO）。

3. 写法要点

尾递归的关键是：递归调用必须是函数的最后一步操作，并且不带上一个函数的参数（即不再需要保存当前栈帧的状态）。

function factorial(n, total) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

factorial(5); // 120

可以看到，每一次返回的就是一个新的函数，不带上一个函数的参数，也就不需要储存上一个函数了。尾递归只需要保存一个调用栈，复杂度 O(1)。

4. 注意事项

补充：

• 引擎是否开启 TCO 取决于实现：ES2015 标准要求支持，但 Safari/JavaScriptCore 已支持，V8 目前并未默认开启（出于可调试性考虑），所以即便按尾递归写法写，V8 仍可能发生栈溢出。
• 实务上常用蹦床函数（trampoline） 或改写成迭代（while/for） 来避免栈溢出。
• 尾递归优化适合：阶乘、斐波那契、累加、树形结构遍历等线性递归。

// 蹦床函数示例：避免 V8 栈溢出
function trampoline(fn) {
  while (typeof fn === 'function') fn = fn();
  return fn;
}

const fact = (n, total = 1) =>
  n <= 1 ? total : () => fact(n - 1, n * total);

trampoline(fact(100000)); // 安全运行

来源整理自：vue3js.cn 面试官系列