function countup(n) {
  if (n < 1) {
    return [];
  } else {
    const countArray = countup(n - 1);
    countArray.push(n);
    return countArray;
  }
}
console.log(countup(5));

After running the above code it returns an array: [1, 2, 3, 4, 5], but push() adds new values at the end of an array so when value of n was 5 it should push 5 to the end of the array and when value of n got 4 it should push 4 at the end of the array like [5,4].

So why not it is returning [5,4,3,2,1] ? It is hard to understand what is happening in this code probably because of this recursion. Isn’t unshift() (which add new values to start of the array) should return [1,2,3,4,5] and push() [5,4,3,2,1] why opposite is happening?

CodePudding user response：

As @Joseph stated in a comment the second to last function call would get pushed to the array first, then it would return that array, where it immediately adds the next number up the call stack.

Here are the steps being taken.

Initial call enters itself recursively n times, where the bottom call returns [] and then [1], [1, 2] ... [1, 2, ..., n] all the way up the call stack where upon the first function call ends and the program does something else.

To get [n, ..., 2, 1] you need to use the Array.prototype.unshift() method, which takes any javascript primitive type, ie String, Number, Boolean, and Symbols, in a comma separated format, like countArray.unshift(4, 5) or countArray.unshift(...anotherArray), and adds them to the beginning of the array.

ie

let someArr = [3, 2, 1];
someArr.unshift(5, 4);
console.log(JSON.stringify(someArr));
// outputs [5, 4, 3, 2, 1]

or

let someArr = [1, 2, 3];
let anotherArr = [5, 4]
someArr.unshift(...anotherArr);
console.log(someArr);
// outputs [5, 4, 1, 2, 3]

Where the output of

function countup(n) {
  if (n < 1) {
    return [];
  } else {
    const countArray = countup(n - 1);
    countArray.unshift(n);
    return countArray;
  }
}
console.log(countup(5));

will be [5, 4, 3, 2, 1] tested with node in Vscode.

CodePudding user response：

One useful way to think about this is to start by imagining you already had a function that does what you want for lower values, and then see how you would write one that works for higher values. That imaginary function should be a black box. All we should know is that it does what we want in the case of lower values. We don't care about its implementation details.

So lets say we had a function imaginaryBlackBox, and we knew that it returned the correct countUp values that we want. So, for instance, we know that imaginaryBlackBox (4) returns [1, 2, 3, 4].

Now, knowing that, how might we write a function that works for an input of 5 as well? How about something like this:

function countup(n) {
  if (n < 1) {
    return [];
  } else {
    const countArray = imaginaryBlackBox(n - 1);
    countArray.push(n);
    return countArray;
  }
}

Again, we don't know how imaginaryBlackBox works. We just know that it returns the correct result for lower values of n. Our base case remains obvious. For another case, some n greater than 0, we call imaginaryBlackBox(n - 1), and by our basic assumption, we know that will return [1, 2, 3, ..., (n - 1)], which we store in countArray. Then we push n onto that array, to end up with [1, 2, 3, ..., (n - 1), n]. We return that value and we're done.

Now here's the trick. We know an implementation of imaginaryBlackBox -- it's the function we're writing! So we can simply replace it with countUp and know it will work.

function countup(n) {
  if (n < 1) {
    return [];
  } else {
    const countArray = countUp(n - 1);
    countArray.push(n);
    return countArray;
  }
}

This required a few assumptions, and they are important to all recursive functions:

• There is at least one base case whose value we can calculate without any recursive call. Here, when n is < 1, we simply return [].

• For other cases, we can break down our problem into one or more recursive cases, where the input is in some clear and measurable way closer to a base case, so that subsequent steps will hit a base case in a finite number of calls. Here we reduce n by 1 on every step, so eventually it will be below 1.

• Our function is effectively pure: its outputs depend only on its inputs. That means we can't count on changing a global variable or reading from one that might be changed elsewhere. Note that I use the qualifier "effectively" here; it doesn't matter if this function has observable side-effects such as logging to the console, so long as its output is dependent only on its input.

Anytime you have those conditions, you have the makings of a good recursive function.