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

Question

I was trying to solve "fibonacci" sequence using "Continuation-passing style" in typescript which is a very easy example, but just to try

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

The problem is when I go over 16 as input it causes

Maximum call stack size exceeded

But when I try it with direct style and with providing input more than 40, it works very well

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

so I am trying to get a deep look on why CPS could not solve it with more than 16 while direct styling could.

As I get CPS opens stack in memory for each function passing and direct style opens stack in memory for each function invocation.

Karl Bielefeldt Karl Bielefeldt · Accepted Answer · 2021-10-21T13:48:01

Well, direct style only stores n on the stack, whereas CPS style stores n and a lambda. I don't know how precisely how typescript stores lambdas in memory, but at the very least it needs t and a function pointer, so each invocation takes at least 3 times the amount of stack space.

Much more significantly, each recursive step of your CPS solution also makes the stack deeper, due to the nesting, where the direct style goes down the stack for f(n-1), then back up the stack, then down again for f(n-2).

Usually for CPS to be stack safe, you have to implement trampolining. Also using a language implementation with tail call optimization would probably help a bit.

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

1 Answers