A few questions about how Recursion works

So I am learning recursion, starting with this challenge: Basic JavaScript: Use Recursion to Create a Countdown

It presents this code:

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

I am just a little confused on how it works. It calls the function again before pushing to the array, so how are the numbers in the correct order?

How is the value of countArray stored if it is being reinitialized each time the function is called?

How come return countArray; does not create return anything until the very end? I would think output this:

[1]
[1,2]
[1,2,3]
[1,2,3.4]
[1,2,3,4,5]

But it is not.

4 Likes

Hello michaelnicol,

This is the order that things happen:

countup(5) ->
else statement, countArray = countup(5 - 1 = 4) ->
else statement, countArray = countup(3) ->
else statement, countArray = countup(2) ->
else statement, countArray = countup(1) ->
else statement, countArray = countup(0)

It is important to remember that countArray is declared at each step, at a different scope. So each countArray is equal to what is returned from our last countup() call.

countup(0) returns [] as countArray, so we move back up to the line: countArray.push(n) (remember, n = 1 here). So we push n (1) into our empty countArray. Now our countArray looks like [1], and we return it.

That means that countup(1) = [1]. When n = 2, our countArray is countup(1), so it is [1]. Then we push n (2) to countArray, and return that, so on and so forth. So we end up with:

countup(5) {
    const countArray = countup(4) {
        const countArray = countup(3) {
            const countArray = countup(2) {
                const countArray = countup(1) {
                    const countArray = countup(0) {
                        return [];
                    countArray.push(1);
                    return countArray; //[1]
                countArray.push(2);
                return countArray; //[1, 2]
            countArray.push(3);
            return countArray; // [1, 2, 3]
        countArray.push(4);
        return countArray; // [1, 2, 3, 4]
    countArray.push(5);
    return countArray; // [1, 2, 3, 4, 5]
}

This is VERY annoying to type out (believe me, I just did it lol), and it would be MUCH more annoying if we had to do n = 10, or n = 100. This is why recursion is awesome: it lets us perform the same action repeatedly as many times as we need to, with a lot less code.

5 Likes

So even though I call with (5) first, nothing happens until it reaches 1? Still slightly confused.

something happens alright, but the functions called can’t get an output till the function called isndie each one gets an output
the only way for a function to get an output without waiting for the output of an other function is to trigger the base case if (n < 1) {return [];}, so now one function has an output, the function that called that can have an output too and so on, till the one in the console.log has an output too, finally

countup(5) {
    const countArray = countup(4) {
        const countArray = countup(3) {
            const countArray = countup(2) {
                const countArray = countup(1) {
                    const countArray = countup(0) {
                        return [];
                    countArray.push(1);
                    return countArray; //[1]
                countArray.push(2);
                return countArray; //[1, 2]
            countArray.push(3);
            return countArray; // [1, 2, 3]
        countArray.push(4);
        return countArray; // [1, 2, 3, 4]
    countArray.push(5);
    return countArray; // [1, 2, 3, 4, 5]
}

If you look here, you can see that what we want to do is:

countup(5) {
    const countArray = countup(5 - 1);
    countArray.push(5);
    return countArray;
}

The problem is, countArray isn’t exactly an array… It is a function call that will end up returning an array. So, the computer has to figure out what that array is before we can push anything to it. Now we have:

countup(5) {
    const countArray = countup(4) {
        const differentCountArray = countup(4 - 1);
        differentCountArray.push(4);
        return differentCountArray;
    countArray.push(5);
    return countArray;
}

As you can see, we run into the same problem: instead of an array, we have a function call. The computer will keep calling the function, with n getting 1 lower every time. When n = 1, countArray = countup(0). Since countup(0) returns [], when n = 1, countArray = [].

countup(1) {
    countArray = countup(0); // = []
    countArray.push(1);
    return countArray; // [1]
}

Then ‘1’ is pushed into that countArray and it is returned. Which means that countup(1) returns [1]. So,

countup(2) {
    const countArray = countup(1); // = [1]
    countArray.push(2);
    return countArray; // [1, 2]

Then we go all the way back up until we reach the original call:

countup(5) {
    const countArray = countup(5 - 1); // = [1, 2, 3, 4]
    countArray.push(5);
    return countArray; // [1, 2, 3, 4, 5]
6 Likes

So basically, it keeps going down into more and more layers of scopes because no array is being returned. It then returns an empty array at 0, which then sends that array back up through all the arrays, pushing in the appropriate number.

Close. The base case returns []. The other cases return the result of countup(n-1) with the n pushed onto that array.

countup(5) needs to know countup(4) before it can return.

1 Like

In your written out example, how does const declaring the varaible not interfear scope wise? Shouldn’t it already be defined?

If I Googled correctly “The const declaration creates a read-only reference to a value. It does not mean the value it holds is immutable, just that the variable identifier cannot be reassigned. For instance, in the case where the content is an object, this means the object’s contents (e.g., its properties) can be altered.”

1 Like

So I tried doing the challenge again with this new knowledge and I could not figure it out.

I looked up the awnser and this is what I got:

function sum(arr, n) {
// Only change code below this line
if (n <= 0) {
return arr[0];
}
return arr[n] + sum(arr,n-1)
// Only change code above this line
}

I am roughly understanding what it is doing.

If i call with: sum([2, 3, 4], 1)

Does it go to the highest index (1 in this case - so second element/ number), and counts down using recursion to add all the previous indexs? It isn’t really counting down, but goes until n is equal to the base (zero) and then counts up?

I think your code would return 5 when you call sum([2, 3, 4], 1). Is this what you are seeing/expecting?

1 Like

michaelnicol,

I asked a similar question regarding this exercise as well. See this post:

This might help.

1 Like

Wow! That site is awesome. I will use that a lot more. Thanks so much!

That site helps me get a good visual, and along with major help of @JeremyLT and @lucassorenson, I have finally grasped this concept.

(Bob, it was returning 5 btw)

Huzzah! I’m glad I helped. I think recursion is one of those things where it takes a few iterations for it to ‘click’!

1 Like

Uhmm… But why push happens first at 1 and not at 5 ?

Hi!, can you explain to me why 1 is got to push first and not 5 ?.

The push for 5 depends on the function call for 1 being completed first.

1 Like

this is amazing, crystal clear!!!

The problem is, countArray isn’t exactly an array… It is a function call that will end up returning an array

this is what i needed to understand!!!

1 Like