TypeScript中CPS实现斐波那契调用栈溢出而直接风格正常的原因是什么

先回顾两个实现的代码 #

问题CPS版本 #

const cpsFib = (n: number, f: (t: number) => void) => {
  if(n === 0 || n === 1) f(1);
  else {
    cpsFib(n - 1, (t0) => {
      cpsFib(n - 2, (t1) => {
        f(t0 + t1);
      });
    })
  }
}

const num = 16;
console.time('cps');
const ans = cpsFib(num, (ans) => console.log(`fib(${num}): ${ans}`));
console.timeEnd('cps');

正常运行的直接风格版本 #

const num = 40;
const fib: (arg: number) => number = (n: number) => n <= 1 ? 1 : fib(n-1)+fib(n-2);
console.log(`fib(${num}): ${fib(num)}`); 

核心差异：调用栈深度的增长逻辑 #

1. 直接风格的栈深度是线性的 #

直接风格递归的总调用次数虽然是O(2^n)，但最大调用栈深度永远等于输入值n：

• 执行时优先递归fib(n-1)分支，直到触达n<=1的终止条件，过程中栈深度逐步增加到n
• 触达终止条件后栈帧逐层弹出，再计算fib(n-2)分支时栈深度不会超过n
  n=40时最大栈深度仅为40，远低于JS引擎默认的调用栈上限（V8引擎默认约10000层），因此不会溢出。

2. 现有CPS实现的栈深度是指数级的 #

你当前的CPS写法没有做尾调用优化，且所有回调都是同步嵌套调用，导致栈深度随n指数增长：

• 每一层cpsFib的回调执行时，外层cpsFib的栈帧还未释放
• 回调内部调用下一层cpsFib时，会在现有栈的基础上继续压入新栈帧，不会弹出外层无用栈帧
  当n=16时，最大栈深度已经达到65536，远超引擎栈上限，直接触发溢出报错。

认知修正 #

你之前认为「CPS为传递的函数开辟栈空间、直接风格为函数调用开辟栈空间」的理解存在偏差：两种实现的栈空间都是在函数调用时开辟，核心差异是栈帧的释放时机：

• 直接风格递归：触达终止条件后会逐层弹出栈帧，栈深度始终保持线性
• 现有CPS实现：回调嵌套调用导致外层栈帧无法及时释放，栈深度指数级增长

优化方案参考 #

可以用蹦床函数消除嵌套栈帧积累，改造后n=40也能正常运行：

// 蹦床函数：循环执行返回的函数，避免栈帧堆积
const trampoline = (fn: Function) => (...args: any[]) => {
  let res = fn(...args);
  while (typeof res === 'function') res = res();
  return res;
}

const cpsFib = trampoline((n: number, f: (t: number) => void) => {
  if(n === 0 || n === 1) return () => f(1);
  return () => cpsFib(n - 1, (t0) => {
    cpsFib(n - 2, (t1) => f(t0 + t1));
  });
});

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