如何避免返回递归调用时触发Maximum call stack size exceeded错误

问题描述 #

我写了这段递归脚本：

const returnCount = (n: number): number => {
  if (n === 0) return 0;
  return returnCount(n - 1);
};

const result = returnCount(100000);

运行时触发了栈溢出错误：

Project/src/2023/23/test.ts:2
  if (n === 0) return 0;
  ^
RangeError: Maximum call stack size exceeded
    at returnCount (Project/src/2023/23/test.ts:2:3)
    at returnCount (Project/src/2023/23/test.ts:3:10)
    at returnCount (Project/src/2023/23/test.ts:3:10)
    ...

我能理解下面这种写法会报错，因为要等递归调用返回后才能计算0 + returnCount(n-1)：

const returnCount = (n: number): number => {
  if (n === 0) return 0;
  return 0 + returnCount(n - 1);
};

但我以为return returnCount(n - 1);这种写法会让调用栈“短路”，直接返回下层调用的结果，不会堆积栈帧。请问怎么实现这种“短路”来避免栈溢出？

原因分析 #

你的思路没错，但JavaScript/TypeScript的**尾调用优化（Tail Call Optimization, TCO）**有严格的触发条件：

• 递归调用必须是函数的最后一个执行操作，不能有任何后续处理（比如第二种写法里的加法就破坏了这一点）
• 运行环境必须支持TCO：目前只有Safari完全支持，Chrome、Node.js等V8引擎环境默认不开启（即使是严格模式下）

你写的第一个函数确实符合尾调用形式，但因为V8不支持，所以栈帧还是会不断堆积，最终溢出。

解决方法 #

1. 手动改写成循环（最可靠） #

递归本质是循环的语法糖，直接用循环可以彻底避免栈溢出问题：

const returnCount = (n: number): number => {
  while (n !== 0) {
    n--;
  }
  return 0;
};

const result = returnCount(100000); // 正常运行

2. 用“蹦床函数（Trampoline）”模拟尾调用优化 #

蹦床函数可以把递归调用转换成循环调用，避免栈帧堆积：

// 蹦床函数：接收一个返回函数或值的函数，循环执行直到得到最终值
const trampoline = <T>(fn: () => T | (() => T)): T => {
  let result = fn();
  while (typeof result === 'function') {
    result = result();
  }
  return result;
};

// 改写递归函数，让它返回一个待执行的函数，而不是直接递归调用
const returnCount = (n: number): number | (() => number) => {
  if (n === 0) return 0;
  return () => returnCount(n - 1);
};

// 通过蹦床函数执行
const result = trampoline(() => returnCount(100000)); // 正常运行

3. 开启V8的尾调用优化（仅限特定场景） #

Node.js中可以通过--harmony-tailcalls参数开启，但这个特性一直处于实验阶段，不建议生产环境使用：

node --harmony-tailcalls your-script.ts

注意：即使开启，也只有在严格模式下才会生效，所以你的代码需要加上'use strict';。

内容的提问来源于stack exchange，提问作者Valentin Vignal