连续传递样式导致 "Maximum call stack size exceeded " 错误

Question

我试图在 typescript 中使用“Continuation-passing style”来解决“fibonacci”序列，这是一个非常简单的例子，但只是为了尝试

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');

问题是当我将 16 作为输入时，它会导致

Maximum call stack size exceeded

但是当我尝试使用 direct style 并提供超过 40 的输入时，它工作得很好

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)}`);

所以我想深入了解为什么 CPS 不能用超过 16 解决它，而直接样式可以。

据我所知，CPS 为每个函数传递打开内存中的堆栈，direct style 为每个函数调用打开内存中的堆栈。

Answer 1

嗯，direct 风格只在堆栈上存储 n，而 CPS 风格存储 n 和一个 lambda。我不知道打字稿是如何在内存中存储 lambda 的，但至少它需要 t 和一个函数指针，所以每次调用至少需要 3 倍的堆栈量 space.

更重要的是，由于嵌套，CPS 解决方案的每个递归步骤也会使堆栈更深，直接样式在堆栈中下降 f(n-1)，然后备份堆栈，然后再次下降 f(n-2)。

通常要使 CPS 堆栈安全，您必须实现蹦床或使用具有尾调用优化的语言实现。

连续传递样式导致 "Maximum call stack size exceeded " 错误

Continuation-passing style causes "Maximum call stack size exceeded " error

functional-programming

typescript