Recursion - add numbers to an array

Question

I am taking the course of Freecodecamp and on the subject of recursiveness I came across this code:

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

It returns me an array corresponding to size N (if I put 5, returns an array [1,2,3,4,5]).

I understand the concept of recursiveness, but I couldn’t understand this code. Because the const countArray = countup(n - 1);? What is the meaning of this line? Because for me, from the moment I call the function countup(n - 1), what is below it does not run. Can you help me?

Answer 1

After you call countup(n - 1), the lines below are executed yes, but only after this call returns.

To make it simple, let’s see what happens when you call countup(2):

• countup(2): n is equal to 2, so does not enter the if (n < 1)
• is called countup(n - 1), that is to say, countup(1)
  • within the call countup(1): n is equal to 1, so does not enter the if (n < 1)
  • is called countup(n - 1), that is to say, countup(0)
    • within the call countup(0): n is equal to 0, then enters the if (n < 1) and returns an empty array ([])
  • countup(0) returned the empty array, which was placed in the variable countArray (is what the line const countArray = countup(n - 1) ago)
  • countArray.push(n): here n value 1, then 1 is placed in the array (which is now [ 1 ])
  • the array [ 1 ] is returned
• countup(1) returned the array [ 1 ], which is placed on the variable countArray
• countArray.push(n): here n vale 2, then 2 is placed in the array (which becomes [ 1, 2 ])
• the array [ 1, 2 ] is returned

That is, the first call starts at the initial value of n (in the above example was 2), and with each recursive call it decreases, until it reaches zero. When it reaches zero, it returns the empty array and the process starts to "return", inserting the numbers into the array and returning it to the previous call.

What can confuse is that with each call the context changes: the value of n and the array countArray being manipulated have different values. But in the end everything "joins" and the result is an array containing all the numbers from 1 to n.

The important thing is that making a recursive call doesn’t stop the execution, as you imagine. What happens is that a recursive call may end up making other recursive calls (such as when countup(2) calling for countup(1), which in turn called countup(0)), and these calls are "hung" waiting for the others to return. And after they return, the execution continues on the following lines.

What ensures that this process does not last forever is the stopping condition (if (n < 1)), because that’s when no more recursive calls are made.

---

To understand recursion, first you need to understand recursion

It might help if you think about setting the solution recursively: how I create an array containing the numbers from 1 to N?

1. if N < 1, the interval from 1 to N will have no number, so the array is empty (is what the if ago)
2. if N >= 1 (i.e., the block else):
   • 2.a) create an array containing the numbers from 1 to N - 1 (using this same algorithm recursively, i.e., I return to step 1, but using the value of N - 1)
   • 2.b) adding the N in that array

Step 2.a corresponds to const countArray = countup(n - 1) (I solve the same problem recursively for N - 1), and step 2.b corresponds to countArray.push(n).

The idea of recursion is basically this: there is a "base" case with a trivial solution (the empty array), and for the other cases you solve smaller instances of the problem recursively, until you get to the base case, and in the end you put it all together.

---

Explaining in another way

Because of this doubt in the comments, I will try to explain in a little more detail. To simplify, let’s assume that I called countup(1).

The call is made to countup(1):

• here the n is worth 1, so do not enter the if (n < 1)
• inside the block else:
  • const countArray = countup(n - 1); ← as n worth 1, then the call is made to countup(0)

Here we pause to explain that the call to countup(0) is "independent" of the call to countup(1). Although it is the same function, and it is called within itself, it is two different calls and each one executes according to its context (in this case, the value that is passed as parameter is different).

So the call countup(1) is running the line const countArray = countup(n - 1);. That means she needs to get back to countup(0) and assign the value returned in the variable countArray. I mean, she needs to wait countup(0) fully execute.

And how countup(0) executes? Like this:

• n is worth 0, so get in the if (n < 1) and returns an empty array ([])

Like countup(0) has already finished (returning an empty array), so countup(1) can continue running from where you left off:

const countArray = countup(n - 1);

On this line she picks up the return of countup(0) (the empty array) and assigns this value to the variable countArray. Then she runs the following lines:

countArray.push(n);
return countArray;

I mean, she adds n to the array (and how we are inside the call countup(1), the n is worth 1, so number 1 will be added to countArray). And finally, countArray (which is now the array [1]) is returned, and countup(1) ends its execution.

Note that every call to countup is "independent": only because one is in the if, doesn’t mean another can’t be in else (because each one has a different context, since the values of n that each receives is different). And just because one of them returned, it doesn’t mean that the others should return immediately: each returns only when it arrives in some line containing return.

---

Similarly, when we call countup(2):

• here the n Worth 2, so don’t enter the if (n < 1)
• inside the block else:
  • const countArray = countup(n - 1); ← as n worth 2, then the call is made to countup(1)

That is, the call countup(2) need to wait countup(1) end to assign the return to the variable countArray.

And from the above explanation, we already know that countup(1) returns the array [1]. That is, after that countup(1) ends, the array [1] is returned and assigned in the variable countArray.

After that, the call countup(2) can continue running. The next line is countArray.push(n);, and how countArray is [1] and the n vale 2, the number 2 is added in the array, which becomes [1, 2].

After that the array is returned, and the result is [1, 2].

Answer 2

See that every time the countup is called within himself, the interpreter waits until the function returns a value so that it can continue executing the code.

To facilitate understanding follow the scenario below and read the comments within the code.

Consider countup(2):

First execution:

function countup(2) {
    if (2 < 1) {
        return [];
    } else {
        // O interpretador vai parar aqui até que a função
        // retorne seu valor...veja o Segunda execução
        const countArray = countup(2 - 1);
        countArray.push(n);
        return countArray;
    }
}

Second execution

function countup(1) {
    if (1 < 1) {
        return [];
    } else {
        // O interpretador vai parar aqui até que a função
        // retorne seu valor...veja o Terceira execução
        const countArray = countup(1 - 1);
        countArray.push(n);
        return countArray;
    }
}

Third execution

function countup(0) {
    if (0 < 1) {
        // Para o valor 0 esta função irá retornar um array vazio.
        // Este resultado será recebido na segunda execução
        return [];
    } else {
        const countArray = countup(0 - 1);
        countArray.push(n);
        return countArray;
    }
}

Returning to the second execution

function countup(1) {
    if (1 < 1) {
        return [];
    } else {
        // Agora com o resultado na mão da terceira execução o 
        // interpretador irá prosseguir até o return
        const countArray = [] /* countup(1 - 1) = [] */;
        countArray.push(n); // Agora o array vazio ganha o valor 1 = [1]
        return countArray;
    }
}

Returning to the first execution

function countup(2) {
    if (2 < 1) {
        return [];
    } else {
        // Agora com o resultado na mão da segunda execução o 
        // interpretador irá prosseguir até o return
        const countArray = [1] // countup(2 - 1) = [1];
        countArray.push(n); // O array ganha o novo valor 2: [1, 2]
        return countArray;
    }
}

Answer 3

When N < 1 (first condition), the recursion will start to return. I mean, on the line you’re in doubt const countArray = countup(n - 1);, the method will return 0, therefore const countArray = 0. From this it will run the bass lines:

countArray.push(n);
return countArray;

That is, N will be added to the array in recursive turn. If you put these lines before countArray = countup(n - 1);, the array will return as [5,4,3,2,1], 'cause you’ll be adding n to the array before arriving at the start of the count.