How to push the indexes of a loop into an array with recursion?

Question

I am recently learning about recursion due the factorial alogithm. Nevertheless, my question is:

1. how do I simulate the "for loop" with a specified length
2. how to push its indexes into an array with recursion?

for example, loop 5 times then push its "indexes" into an array rendering [1,2,3,4,5]

I have created 2 functions [ loop | recursive ] with each attempting to achieve the same output. The "for loop" version is as followed:

function loop(index, length) {
  const result = [];
  for (let i = index; i <= length; i++) result.push(i);
  return result;
}

console.log(loop(1, 5)); // [ 1, 2, 3, 4, 5 ]

However, the "recursive" version isn't printing the desire result.

function recursive(index, length) {
  const result = [];
  result.push(index);
  return (index < length) ? recursive(++index, length) : result;
}

console.log(recursive(1, 5)); // [ 5 ]

Can someone kindly show me why it didn't output [ 1, 2, 3, 4, 5 ]

Answer 1

Because result is being reinitialized to [] every time the function is called. You are not passing itself the previous result, so it gets reset. In the end, only the last iteration with the last index ([5]) is sent back.

What you can do is use a third argument, optional, that you can initialize to [].

function recursive(index,length, result=[]) {
  result.push(index);
  return (index < length) ? recursive(++index,length, result) : result;
}

console.log(recursive(1,5)); // [1,2,3,4,5]

Answer 2

The answer from Jeremy Thille is great. It explains what's wrong, and gives a useful and understandable alternative. The code is clean and as it's tail-recursive, it can take advantage of tail-call optimization if that ever becomes widespread. There is a bug in it, though: presumably recursive (10, 3) should return an empty array. Here it will return [10].

While we could easily fix that, let's look instead at an alternative which is logically simpler and which avoids the default parameter. (An earlier answer explains some of the potential issues with default parameters. Please understand that they are still a useful and powerful technique, but they do have a downside.)

So here's an alternative version, both in modern syntax:

const range = (from, to) =>
  from > to ? [] : [from, ... range (from + 1, to)]

and in an older style:

function range (from, to) {
  if (from > to) {
    return []
  }
  return [from] .concat (range (from + 1, to))
}

In either version, we simply recur by creating a new array, starting with the from value, and then including all the values from the recursive call. We hit a base case when from is larger than to and we return an empty array.

There is a big possible eventual disadvantage to this. It's not tail-recursive. Functions in which any recursive call is immediately returned without further processing is called tail-recursive. There are some very useful optimizations on that JS engines can apply to tail-recursive functions to avoid overflowing the recursion stack.

We could make this tail-recursive by adding the default parameter or adding a wrapper function which passes that parameter to an internal recursive helper function. Either would be easy to do. However, we can see that it makes little difference in modern JS, since at the time of this answer almost no engines support proper tail calls, even though I believe doing so is still in the specification. So for now, we won't bother.

Here is this version in action:

const range = (from, to) =>
  from > to ? [] : [from, ... range (from + 1, to)]

console .log (range (1, 5)) //=> [1, 2, 3, 4, 5]
console .log (range (4, 4)) //=> [4]
console .log (range (5, 1)) //=> []

.as-console-wrapper {max-height: 100% !important; top: 0}

Answer 3

One workaround could be to add an accumulator to your recursive function, in order to bring in every steps the array you started at the beginning of the first call.

function recursive(index, length) {
  const result = [];
  result.push(index);
  return recursiveAcc(++index, length, result);
}

function recursiveAcc(index, length, result) {
  result.push(index);
  return (index < length) ? recursiveAcc(++index, length, result) : result;
}

console.log(recursive(1, 5)); // [ 1, 2, 3, 4, 5 ]