Recursion: What is actually happening here?

Ok, my problem isn’t passing the challenge. My problem is understanding why the code in the challenge example actually does what it does. I don’t want to write code I don’t understand just to pass the challenge and move forward. I want to actually understand what is going on behind the scenes so to speak.

I left a few comments on the code below to help outline my confusion. I tried writing things out on paper but that got confusing. It seems to me that countArray doesn’t actually become an array until the very end when n = 0. If countArray isn’t an array at the beginning (when n = 5) how can we push a value onto a non-existent array?

I’m sure there is a simple concept I’m missing here and any help or suggested reading would be greatly appreciated.

Count Up Code


function countup(n) {
if (n < 1) {
  return [];
} else {
  const countArray = countup(n - 1); //What happens here?
  countArray.push(n); //When exactly does this push function execute? It seems like it would be pushing n onto an array that doesn't exist yet?
  return countArray;
}
}
console.log(countup(5)); // [ 1, 2, 3, 4, 5 ]

Challenge: Use Recursion to Create a Countdown (Note: the countup code is from the lesson section of the challenge)

Link to the challenge:
https://www.freecodecamp.org/learn/javascript-algorithms-and-data-structures/basic-javascript/use-recursion-to-create-a-countdown

3 Likes

Let’s walk the code with a specific number.

countup(5)
At your if statement, you will take the second branch. This means that you will execute
const countArray = countup(4);
This will return the array [1, 2, 3, 4]
You then push 5 onto this array and return the result.

If we look into how countup(4) works, we can see that it needs countup(3). This continues down until countup(0), which takes the first branch of your if and immediately returns [].

4 Likes

I haven’t had my coffee yet, so I’m going to take shortcut and refer you to my explanation from yesterday:

Let me know if that doesn’t make sense and I can walk through the call stack of your function.

4 Likes

Thank you @JeremyLT and @ArielLeslie for the responses. I now have the understanding I was needing.

Also, I decided to write it all out on paper and this helped tremendously as well. Here is a picture of that incase anyone is curious. I went with n = 3 to begin with so it wouldn’t be so long. I guess this is why we use computers lol!

The red indicates the flow back once the base case has been reached. @ArielLeslie I see now what you mean about setting up dominoes. Then the base case, or exit condition, gives the last domino a little flick to set it all into motion.

11 Likes

This is an extremely useful and underappreciated programming tool.

4 Likes

I dont understand why if the code is in this order:

  1. const countArray = countup(n - 1);
  2. countArray.push(n); // PUSH 2nd!!!
  3. return countArray;

You said that the steps are:

  1. const countArray = countup(4);
    2 ) This will return the array [1, 2, 3, 4]
    3 ) You then push 5 onto this array and return the result. // WHY PUSH 3rd???

What you have labeled as steps 1 and 2 for my explanation are the same as your step 1. When you call the function inside of the function, it has to execute and return before the code can continue.

I get this error “uncaught ReferenceError: head is not defined”. why does not it work:
console.log(body);
const body = document.querySelector(".body");

This question appears to have nothing to do with this thread. I think that it would be best if you create a separate thread with your code for the question.

I really dont get it. You say that:

Is equal to:

Right?

If you mind that. What happen in the code is (supose n=3):

const countArray = countdown(2); // excecution #1 with n=3
const countArray = countdown(1); // excecution #2 with n=2
const countArray = countdown(0); // excecution #3 with n=1
because n<1 // excecution #4 returns

Before reaching the countArray.push(n); ??? And if that happen before, how understand the code that countArray is [3, 2 , 1] if by the time the execution arrives the push the n=3, n=2 and n=1 where passed and n=0?

So previusly I understand that it works this way:

n=3
const countArray = countup(2);
countArray.push(3);
note: i really dont understand what is saved into the countArray

Then:
n=2
const countArray = countup(1);
countArray.push(2);
note: i really dont understand what is saved into the countArray

Then:
n=1
const countArray = countup(0);
countArray.push(1);
note: i really dont understand what is saved into the countArray

Then:
n=0
return [ ]

And something that REALLY confuse me is when the execution gives the countArray the category of “array [ , , , ]” if the array was never defined, why the code dont understand for example that countArray is a normal variable, or an object?

I guess you can treat recursion like a series of phonecalls. When you assign countArray to the function, it can’t do anything until the function call it’s being assigned to returns a value.

const countArray = countup(3) //"Hey, I need countup(2) value before I can continue

const countArray = countup(2) //I gotta get my value from countup(1)

const countArray = countup(1) //I can't do anything until countup(0) answers me

countup(0) //All done. Here's an empty array!

Meanwhile in countup(1)
const countArray = countup(1-1) = []
countArray.push(1) //countArray is now [1]
return countArray

From there, the other countup calls are returned and you can see how the numbers are pushed into the array.

1 Like

It is important to understand that every single function call is independent. countup(4) returns an array counting up from 1 to 4. [1, 2, 3, 4]

The function is recursive because it calls itself, but a function call always returns an array.

But in the line const countArray = countup(n - 1); the fuction is called so we’re not going to pass to the the next line that is countArray.push(n); so we remain calling decreasingly the function without pushing anything until we get n=0 that’s to say the base case.
I think the climax of this challenge is to understand what happen when calling countup(n-1) … any explanation ?

Basically the same thing that happens when you call any other function. You wait for the function to do its thing and return a value.

3 Likes

so you mean that when countup(n-1) is called the rest of the code is executed before the effective execution of the called function ?
It’s really confusing for me … I used to think that when a function is called we stop executing the rest of the code and go to execute the function first.

You wait until the function call completes and then the rest of the code in the function call proceeds.

function countup(n) {
  if (n < 1) {
    return [];
  } else {
    const countArray = countup(n - 1); // Recursive call runs *first*, producing an array from 1 to n - 1
    countArray.push(n); // Then the result of the recursive call has n pushed onto the end, resulting in an array from 1 to n
    return countArray;
  }
}
console.log(countup(5));

No, either I wasn’t clear or you misread what I wrote. You asked “what happen when calling countup(n-1)?” I was being very specific about what happens when the code reaches countup(n-1). It waits for countup(n-1) to do its thing and return a value.

You are correct. This is exactly what happens.

1 Like

I think that one thing that really hangs people up on recursion is that they think of a function like a pipeline, so it seems like you can’t call the function with new values if other data is already “in the pipeline”. Really, a function is a set of instructions that can be followed multiple times and simultaniously.

2 Likes

sorry it’s me … ther’i a gray area in the explanation and I need to clarify it.
so … in the line const countArray = countup(n - 1); calling countup(n - 1) should take us immidiately to this part :
function countup(n-1) {
if (n < 1) { etc …
and when arriving again to
const countArray = countup(n - 2); we go back up directly to
function countup(n-2) {
if (n < 1) { etc …

and so we’re not going to pass to the the next line to push(n);
no ?

Yes, when you reach countup(n - 1) you immediately execute the code in that function (which just happens to be the function itself). It’s just like if you had a completely different function in there:

const countArray = someOtherFunction(n - 1);

You have to call someOtherFunction to get the return value so you can set countArray to that return value. You don’t move on until that has been completed.

2 Likes