Javascript Recursion and Functions

Question

Struggling to understand how this code works

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

I can understand why once it gets to the Array.push that it prints out [1], but after that I don't understand how it goes from [1] to [1,2,3,4,5].

Also, wouldn't (n-1) always have to be 1-1 as without it the if (n < 1) won't be true?

• DBS: In the first call, n is the 5 that's passed in. The n - 1 is in the if's else statement, so only runs when n >= 1
• user16540390: Open your browser's dev tools. Set a breakpoint in console.log(countup(5)); and step line by line through the code to see the program flow. Every time you reach const countArray = countup(n - 1); you can analyze the value of countArray. Learning your tools should be one of the first things every programmer does.
• AGE: countArray.push(n) is not called until the recursive call reaches 1, when that is done the recursive block comes to an end, an empty array is returned which then the code proceeds to grab each countArray.push(n) at the current nth position. The current nth position at this point in time is 1. We then return at return countArray; and going back the recursive 'ladder', we will then be at 2, then 3, and so on. Therefore the array formed is 'in order'
• BadHorsie: Recursive functions can be hard to visualise in your head because you need to keep many things in memory to understand the recursion. So a skill you need to develop for this is debugging code, not just reading the code by eye. Then you can leverage computing power itself to take away some of the memory requirements that your brain has to do otherwise.

Answer 1

It should all become clear if you step through it line by line in a debugger:

screen recording

I wasn't able to record it as slowly as I would have liked to, because I was running into some max. sizes for creating a GIF from it. It's probably best if you do the same yourself anyway. Watch the call stack and the values of the local variables. When you do this interactively, I'd encourage you to also explore the local variables of the higher-up instances of your function in the call stack (you can click on a call stack entry to switch to its scope).

1. countup(5) is called, so n = 5. Since 5 is not less than 1, we go to the else branch. With n = 5, we get n - 1 = 4 so countup(4) is called.
2. Same as #1, but with n = 4, eventually calling countup(3).
3. Same as #1/#2 several more times until we end up calling countup(0). At this point we have a total of 6 instances of the function in the call stack.
4. With n = 0, we enter the first branch of the if, returning an empty array [].
5. The countup(1) instance receives the return value of [] from countup(0) and stores it into countArray.
6. The countup(1) instance pushes n (1) into countArray, yielding [1]. The array is then returned to the called (countup(2)).
7. The countup(2) instance receives the return value of [1] from countup(1) and stores it into its own countArray.
8. The countup(2) instance pushes n (2) into countArray, yielding [1, 2]. The array is then returned to the caller (countup(3)).
9. Steps #5-8 continue for countup(3), countup(4) and countup(5), until at the end countup(5) pushes 5 into its countArray, ending up with [1, 2, 3, 4, 5], and that array is now returned to the caller (the main function).
10. The main function got the result [1, 2, 3, 4, 5] from countup(5) which is now passed into console.log.

You can also think about it like this:

• countup(0) returns []¹.
• countup(n) for any nonzero n returns [...countup(n - 1), n]².

(...where ...array means the spread operator so [a, ...[b, c], d] becomes [a, b, c, d])

So we get the following evolution:

Upwards:

countup(0) = []
 \_______________________
 \
countup(1) = [...countup(0), 1] = [...[], 1] = [1]
 ______/
 /
countup(2) = [...countup(1), 2] = [...[1], 2] = [1, 2]
 ____/
 /
countup(3) = [...countup(2), 3] = [...[1, 2], 3] = [1, 2, 3]
 ____/
 /
countup(4) = [...countup(3), 4] = [...[1, 2, 3], 4] = [1, 2, 3, 4]
 ____/
 /
countup(5) = [...countup(4), 5] = [...[1, 2, 3, 4], 5] = [1, 2, 3, 4, 5]

Downwards:

countup(5) = [...countup(4), 5]
 |············\__ \__
 |···············\ \
 = [...countup(3), 4, 5]
 |············\__ \__ \__
 |···············\ \ \
 = [...countup(2), 3, 4, 5]
 |············\__ \__ \__ \__
 |···············\ \ \ \
 = [...countup(1), 2, 3, 4, 5]
 |············\__ \__ \__ \__ \__
 |···············\ \ \ \ \
 = [...countup(0), 1, 2, 3, 4, 5]
 |··· _______/ | | | | |
 |···/ | | | | |
 = [...[], 1, 2, 3, 4, 5]
 \_x_/ | | | | |
 = [ 1, 2, 3, 4, 5]

---

_{1: Technically, any n < 1 would make countup(n) return [], not only n = 0.}

_{2: Technically, the same array is used all the time here and just mutated in every step. In a pure functional way of handling this, a copy would have to be created (const countup = n => n < 1 ? [] : [...countup(n - 1), n]). But that doesn't matter for this explanation because the array is of course no longer needed in the previous function after it was returned.}

• AGE: correct, to understand recursiveness you need to follow the flow of execution instead of focusing on the data itself
• user17773050: Would I be right in saying this happens? After it runs for the first time, the "return countArray;" prints [1] then that is finished. We go back to when countup(n) n = 2. And rather than running the code again, that n is put into the array giving [1,2] etc till it goes to [1,2,3,4,5]?
• CherryDT: I'm not sure what you mean when you say "rather than running the code again". What code are you referring to? Except for the case of countup(0) that returns [], the exact same code is ran every time (just with different local variables n and countArray²).
• user17773050: Once the 'return countArray;' is performed. All the times where '(n < 1)' was false (2,3,4,5) gets added to the array?
• CherryDT: I still don't quite understand what you are asking. We have 5 times that return countArray happens. And every time before it there is a different n pushed into the array. See the explanation in steps listed above. I really recommend stepping through the code in the debugger yourself so you get a feel for it.

Answer 2

Adding some logging should help you understand the execution sequence. This is triggered initially with countup(5), which then recursively calls countup(n-1) until n-1 is 0. That returns an empty array, and then each previous call of countup appends n to the array and returns it. So you end up with an execution order like:

countup(5)
calls countup(4)
calls countup(3)
calls countup(2)
calls countup(1)
calls countup(0), which returns [] to countup(1)
the call from countup(1) appends 1 to the (empty) array and returns [1] to countup(2)
the call from countup(2) appends 2 to the array and returns [1, 2] to countup(3)
the call from countup(3) appends 3 to the array and returns [1, 2, 3] to countup(3)
the call from countup(4) appends 4 to the array and returns [1, 2, 3, 4] to countup(4)
the call from countup(5) appends 5 to the array and returns [1, 2, 3, 4, 5]

function countup(n) {
 console.log('countup('+n+')');
 if (n < 1) {
 console.log('returning empty array');
 return [];
 } else {
 console.log('calling countup - 1');
 const countArray = countup(n - 1);
 console.log('pushing '+n);
 countArray.push(n);
 console.log('returning countArray:');
 console.log(countArray);
 return countArray;
 }
}
console.log(countup(5));

• user17773050: If you could read what I replied to CherryDT with, is that how this works?

Answer 3

Recursive approaches are interesting but kind of difficult to understand at first glance. In this particular example, the function evaluates for a very specific constraint. If n < 1 the function will return an empty Array. Let's dive into the code execution:

• On the first iteration n = 5 that allow the else block to be executed. Once the second countup call (countup(n - 1)) it evaluates the input again, and since n is still greater than 0 the whole process will repeat itself.
• Once the countup function receives an input of 0 (n = 0) it returns an empty array. Such array is then assigned to the countArray variable (in this particular point countArray = []) and the current value of n is pushed into the array (since the n = 0 case already returned, you'll land on the case where n=1). Again this process will repeat itself in every step up until you reach the case where n=5 (technically your first iteration). Once 5 has been pushed into the array, the function will return the array containing every value from 1 to the provided number n sorted from the smallest to the largest number.