Is there a design issue in this recursive function?

Question

function range(x, y) {
  const arr = []
  const innerFunc = (x, y) => {
    if (x === y - 1) {
      return arr
    }
    arr.push(x + 1)
    return innerFunc(x + 1, y)
  }
  innerFunc(x, y)
  return arr
}
console.log(range(2, 9))

output: [ 3, 4, 5, 6, 7, 8 ] It is a function with a recursive function inside. I did this because every time I recursively called this function, the array will reset.

Answer 1

As far as I know only Safari in strict mode has implemented tail call optimisation (TCO) which is (as I understand it) a way to optimise recursive functions when the recursive call occurs at the end (i.e. the tail) e.g.,

function range(x, y) {
  // ...
  return range(x+1, y);
  //     ^.................recursive call at the end
}

Without TCO recursive functions can fail and yours is no exception. I worked out that after approx. ±9500 calls your function will exhaust the stack:

range(1, 9500);
// Uncaught RangeError: Maximum call stack size exceeded

Thinking recursively

As Nick Parsons rightly pointed out you want to apply your recursive function to a shrinking set of input until your reach your exit condition.

Assuming the easiest use case where x < y this is what I'd do:

const range =
  (x, y, ret = []) =>
    (x + 1 === y
      ? ret
      : range(x + 1, y, (ret.push(x + 1), ret)));

range(2, 9);
//=> [3, 4, 5, 6, 7, 8]

However this function will also exhaust the stack when it recurses too much. In fact it's even worse because I worked out that it will at approx. ±7000 calls:

range(1, 7000);
// Uncaught RangeError: Maximum call stack size exceeded

So arguably you already had done a very good job and this is no improvement at all.

Can we fix this?

Turns out we can with a technique known as "trampoline" but first let's see what is the problem we're trying to fix.

When you do range(1, 10) your computer does something like this:

range(1, 10)
  range(2, 10)
    range(3, 10)
      range(4, 10)
        range(5, 10)
          range(6, 10)
            range(7, 10)
              range(8, 10)
                range(9, 10)
                  range(10, 10)
<-- return

Where each call is held into memory until your reach your exit condition and return the accumulation to the user. So we can sort of imagine that with lots of calls, if the computer doesn't protect itself, you will eventually exhaust all memory and cause crashes.

With a trampoline it would look something like this:

range(1, 10)
  range(2, 10)
range(3, 10)
  range(4, 10)
range(5, 10)
  range(6, 10)
range(7, 10)
  range(8, 10)
range(9, 10)
  range(10, 10)
<-- return

The idea behind "trampolining" a function is to have the recursive function return a function to compute the next call to itself and have those functions executed in a loop.

Here's a contrived example:

const range = (x, y, z) => {
  if (x + 1 === y) return z;
  return () => range(x + 1, y, (z.push(x + 1), z));
};

const trampoline = fn => (x, y, z = []) => {
  let res = fn(x, y, z);
  while (typeof res == 'function') res = res();
  return res;
};

trampoline(range)(2, 9);
//=> [3, 4, 5, 6, 7, 8]

trampoline(range)(1, 20000); // <-- a classic recursive function would have exploded here
//=> [2, …, 19999]

Above range computes an Array and uses Function to signal there is more work to be done. But what if we wanted to compute a function? Recursion is a functional style, after all. Another pitfall above is trampoline makes an assumption about the input function's parameters. Trampolines can be implemented in countless ways and below we address some of those concerns:

const range = (x, y, z = []) => {
  if (x + 1 === y) return z;
  return call(range, x + 1, y, (z.push(x + 1), z)); // <- call
};

const call = (f, ...args) =>     // <- call is a simple object
  ({ call, f, args })

const trampoline = fn => (...init) => {
  let res = fn(...init);
  while (res?.call)              // <- check for call
    res = res.f(...res.args);    // <- apply call
  return res;
};

console.log(JSON.stringify(trampoline(range)(2, 9)));
//=> [3, 4, 5, 6, 7, 8]

console.log(JSON.stringify(trampoline(range)(1, 20000)));
//=> [2, 3, 4, ..., 19997, 19998, 19999]

Answer 2

Using an auxiliary function can be a good technique, but here you're using your recursive function as if it were a loop. For something like this a recursive function isn't needed, as a simple loop would do the trick. With that being said, usually, when you write a recursive function, it should build up a result gradually as you return from it, while simultaneously shrinking the input arguments towards the base-case / termination clause of your function (ie: a part of your function that no longer contains any recursive function calls). So rather than thinking about how you can go about populating one global array, try and think about how you can build your result through joining sub-results of your recursive function. Eg:

//    a  b     a+1                    a+1    b
range(2, 6) = [ 3 ] joined with range(3,     6)                                    
                               |---------------|
 | ----------------------------|
 V
range(3, 6) = [ 4 ] joined with range(4,     6)
range(4, 6) = [ 5 ] joined with range(5,     6)
range(5, 6) = [] -----------------/\ (once base case is hit, we can work our way back up)

With that, each call to range() produces a new array with a further call to the range function. Once you reach your base case you can return an empty array, which will then be returned to where the function was called and joined with the previous call to range().

function range(x, y) {
  if(x+1 === y) return [];
  return [x+1].concat(range(x+1, y));
  //          /\--- "joined with"
}
console.log(range(2, 9))