Is it possible, in general, to transform a recursive function in one that uses a manual stack in JavaScript?

user_1031791 0
Viewed 90

Mind the following function:

function count(n) {
  if (n === 0) {
    return 0;
  } else {
    return 1 + count(n - 1);
  }
}

It is the simplest recursive function that counts from 0 to N. Since JavaScript has a small stack limit, that function easily overflows. In general, any recursive function can be converted in one that uses a manual stack and, thus, can't stack overflow; but doing so is complex. Is it possible, for the general case, to convert a JavaScript recursive function in one that uses its own stack, without using a continuation-passing style? In other words, suppose we had written:

const count = no_overflow(function(count) {
  return function(n) {
    if (n === 0) {
      return 0;
    } else {
      return 1 + count(n - 1);
    }
  }
});

Is it possible to implement no_overflow in such a way that this new count function is equivalent to the old one, except without stack overflows?

Notes:

  1. This is not about tail call optimization, since no_overflow should work for non-tail-recursive functions.

  2. Trampolining is not helpful since, for the general case, it requires the function to be written in a continuation-passing style, which it isn't.

  3. Writing the function with yield doesn't work either for a similar reason: you can't yield from inner lambdas.

  4. That no_overflow would, essentially, work like a stack-free Y-combinator.

recursion javascript
1 Answers

In JavaScript, calling a function f(x, y, ...) subjects us to the underlying implementation details of the stack and frames. If you recur using function application, you will absolutely, unavoidably run into a stack overflow.

However, if we can adopt a slightly different notation, such as call(f, x, y, ...), we can control function application however we want -

const add1 = x =>
  x + 1

const count = (n = 0) =>
  n === 0
    ? 0
    : call(add1, call(count, n - 1)) // <-- count not in tail pos

console.log(noOverflow(count(99999)))
// 99999

Implementing noOverflow is a wrapper around loop, defined in this Q&A -

const noOverflow = t =>
  loop(_ => t)

Unsurprisingly this is a non-trivial problem but the answer(s) there should help detail the things you have to consider and some good test cases, should you choose to implement a solution of your own.

Expand the snippet below to verify the results in your browser -

const call = (f, ...values) =>
  ({ type: call, f, values })

const recur = (...values) =>
  ({ type: recur, values })

const identity = x =>
  x

const loop = (f) =>
{ const aux1 = (expr = {}, k = identity) =>
    expr.type === recur
      ? call (aux, expr.values, values => call (aux1, f (...values), k))
  : expr.type === call
      ? call (aux, expr.values, values => call (aux1, expr.f (...values), k))
  : call (k, expr)

  const aux = (exprs = [], k) =>
    call
      ( exprs.reduce
          ( (mr, e) =>
              k => call (mr, r => call (aux1, e, x => call (k, [ ...r, x ])))
          , k => call (k, [])
          )
      , k
      )

  return run (aux1 (f ()))
}

const run = r =>
{ while (r && r.type === call)
    r = r.f (...r.values)
  return r
}

const noOverflow = t =>
  loop(_ => t)

const add1 = x =>
  x + 1

const count = (n = 0) =>
  n === 0
    ? 0
    : call(add1, call(count, n - 1))

console.log(noOverflow(count(99999)))
// 99999

user_6331830
Related