In this article I’ll show you the way to modify recursion to use heap instead of stack and yet keep it almost indistinguishable from the regular one.

Stack Finiteness Problem

Let’s take a look at some arbitrary recursive, but not tail-recursive function. As an example I’ll use Ackermann function:

const ackermann1 = (m, n) => {
  if (m === 0) {
    return n + 1;
  }

  if (n === 0) {
    return ackermann1(m - 1, 1);
  }

  return ackermann1(m - 1, ackermann1(m, n - 1));
};

Pretty quickly we’re going to run into stack limits. At m = 3, n = 12, this function will fail with stack overflow. Usually, in such cases one just changes recursion to loop and calls it a day. In some functions (graph search algorithms, tree traversing) this approach works well, code becomes a bit more complicated, but still simple enough. In others… well, you’ll see.

In general to replace recursion with loop, you have to save state of variables and your current position, do a recursive call, and then restore state and position. Essentially you are writing assembly-like code with jumps and stack frames inside of a high-level language, and no wonder it’s a nightmare to read:

const ackermann2 = (m, n) => {
  const stack = []; // Stack frames

  let state = "initial"; // Instruction Pointer, kind of
  let value = undefined; // Value returned by a recursive call

  const call = (params, returnState) => {
    // Add a new frame and jump to the beginning of the function
    stack.push({ params, returnState });
    state = "initial";
  };

  const ret = (val) => {
    // Remove a frame and jump back to the calling point
    const frame = stack.pop();
    value = val;
    state = frame.returnState;
  };

  call([m, n]);

  while (stack.length !== 0) {
    const frame = stack.at(-1);
    const { params: [m, n] } = frame;

    if (state === "initial") {
      if (m === 0) {
        ret(n + 1);
        continue;
      }

      if (n === 0) {
        call([m - 1, 1], "recursive call n=0");
        continue;
      }

      call([m, n - 1], "general recursive call 1");
    } else if (state === "recursive call n=0") {
      ret(value);
    } else if (state === "general recursive call 1") {
      call([m - 1, value], "general recursive call 2");
    } else if (state === "general recursive call 2") {
      ret(value);
    }
  }

  return value;
};

It would be great to combine ordinary recursion simplicity with the loop stack size.

Solution

In many modern languages it is possible to suspend function execution and resume it later. Of course, I am talking about asynchronous and generator functions. In older javascript versions, when generators had already been added, but async functions still not, it was possible to write a function converting generator into async function. The following code will use similar ideas, but applied to recursive functions.

Instead of recursive functions we will use generator functions. Recursive call will be replaced by yield, delegating computation to the “recursive scheduler”. “Recursive scheduler” will save the generator state, compute the result of the recursive call, then continue generator execution, with the result send back to it.


const ackermann3 = recursive(function* (m, n) {
  if (m === 0) {
    return n + 1;
  }

  if (n === 0) {
    return yield [m - 1, 1];
  }

  return yield [m - 1, yield [m, n - 1]];
});

Now let’s try to write recursive function to bind computations:

const recursive = (generator) => (...params) => {
  let generatorObj = generator(...params);

  let request = undefined; // Recursive request from generator
  let result = undefined; // Result of a recursive call 

  const stack = [];

  while (true) {
    // IteratorResult (next request or result of the call)
    const message = generatorObj.next(result); 
    
    if (message.done) {
      // If generator is done - pass value up the stack, 
      // or finish execution if stack is empty

      if (stack.length === 0) {
        return message.value;
      }

      result = message.value;
      generatorObj = stack.pop();
    } else {
      // Otherwise - push generator state to the stack, and create 
      // a new generator to handle recursive request

      result = undefined;
      request = message.value;

      stack.push(generatorObj);
      generatorObj = generator(...request);
    }
  }
};

Now you we can write recursive code without worrying about the stack.

Benchmarks

All tests are conducted on node v20.16.0 LTS.

First of all, let’s measure performance degradation. I’ll do 100 tests for each version with params m = 3, n = 10.

const benchmark = (fn, params) => {
  try {
    const start = performance.now();
    fn(...params);
    const end = performance.now();
    return end - start;
  } catch (e) {
    return undefined;
  }
};

const params = [3, 10];
let fns = [
  ["naive         ", ackermann1],
  ["explicit stack", ackermann2],
  ["implicit stack", ackermann3],
];

for (let [name, fn] of fns) {
  const samples = 100;
  let data = [];

  for (let i = 0; i < samples; i++) {
    data.push(benchmark(fn, params));
  }

  const total = data.reduce((acc, time) => acc + time, 0);
  console.log(`${name} mean: ${total/samples}ms`);
}

The results are:

naive          mean: 178.13901175999723ms
explicit stack mean: 916.1059493000008ms
implicit stack mean: 2552.887184250003ms

Implicit stack version is x2.7 times slower than explicit stack and x14.3 times slower than naive implementation.

Second, let’s measure how much we’ve increased our stack size. To do this I’ll use the following function:

const count1 = (n) => {
  if (n === 0) {
    return 0;
  }

  return 1 + count1(n - 1);
};

const count2 = recursive(function* (n) {
  if (n === 0) {
    return 0;
  }

  return 1 + (yield [n - 1]);
});

On my machine count1 works up to 10’468 and breaks on 10’469. count2 works up to 29’229’797 and breaks on 29’229’798. That yields 2’792 times increase of stack size.