Beginner's question about a recursion example in JS

Question

I'm a beginner going through a JS tutorial and got stuck trying to understand the order of statement execution in this example of a recursive function:

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

I assumed, that each time const countArray = countup(n - 1); line is reached, it throws the execution back to line 1 with decremented n. That would explain the output array starting at 1 and going upwards, while n is going down. But in that case, shouldn't the function just return empty array [], since n would drop below 1, satisfying the first if and terminating before anything having been pushed into countArray (else)? **Tried googling about the use of breakpoints to see the actual flow, but only saw their uses in non-loops

A breakpoint is a breakpoint, regardless of if it's in a loop or not. `console.log` can also be your friend. But I'm not sure I understand your explanation of what's happening: When `countup(n - 1)` is hit the function is called *again* with the new value for `n` on entry. `n` won't be less than one until... it's less than one, e.g., first time, it'll be `4`. — Dave Newton, Aug 25 '20 at 17:04
IMO you'd be *best* served by "playing computer" with pencil and paper--just pretend you're the computer, write down each step, and remember that execution will resume immediately after the recursive call to `countup`, for each execution of `countup`. — Dave Newton, Aug 25 '20 at 17:05
Pay particular attention to what conditional branch is taken during each call. E.g., for the first iteration, what branch is taken? What's returned? For the first iteration, does it return immediately, or does it make the recursive call? Hint: your pen/cil & paper exercise, if you indent each call, should look like a backslash for most of it. — Dave Newton, Aug 25 '20 at 17:07
`const countArray = countup(n - 1);` doesn't throw the execution back to line 1! It makes another call to `countup` with `n-1`, once that call returns, the current invocation continues and returns it's own value. — phuzi, Aug 25 '20 at 17:14
Very related: [recursion: storage of multiple values in variables](https://stackoverflow.com/q/61600225/215552); [The empty array in this recursive code is accessible how?](https://stackoverflow.com/q/62205712/215552), [Understanding recursive loop that returns an inverted count](https://stackoverflow.com/q/41358428/215552). There have been many questions about this same function in relation to recursion. — Heretic Monkey, Aug 25 '20 at 17:16

score 3 · Answer 1 · answered Aug 25 '20 at 17:52

Let's simply assume that every function call with all its information will be stored in a stack. Note, stacks are LIFO(Last In First Out).

So in your code, countup(5) will be called and stored in stack[0].

Then inside the else condition it is again called as countup(4). This will pause countup(5) from being executed and countup(4) will be stored in the stack[1].

Just like this until n<1 countup will be called with a lower value and stored in stack.

At the end of all calls, stack will be like,

 - stack[4]    countup(1)
 - stack[3]    countup(2)
 - stack[2]    countup(3)
 - stack[1]    countup(4)
 - stack[0]    countup(5)

Now popping from stack will start. As stack is LIFO so element at top of the stack will be popped. Popped means you're deleting that element from your stack.

countup(1) will be popped first and finish its execution. That is countArray.push(1).

Then countup(2) will be at the top of stack. So, countup(2) is popped and finish its execution countArray.push(2).

Just like this, countup(3) is popped and finish its execution countArray.push(3). countup(4) is popped and finish its execution countArray.push(4). countup(5) is popped and finish its execution countArray.push(5).

At the end the entire array is returned.

*I've described it in simple terms. The real execution behind the hood has a lot more things going and has a lot other terms to know about. You can check this article that describes how recursion works in JS

score 0 · Accepted Answer · answered Aug 25 '20 at 17:17

I don't know if you're familiar with the "spread" syntax, but it might be easier to see what's going on if the body of the else clause were written as simply:

return [...countUp(n - 1), n];

That just means it's the array you get by taking countUp(n - 1) and adding the element n at the end. The code you show does the same, just in a slightly different way. Hopefully it's obvious from this description why the function does what it does - but if it still isn't, note that:

countUp(0) is empty
countUp(1) therefore consists of an empty array with an additional 1 on the end - so the singleton array [1]
countUp(2) is the above with a 2 on the end: [1, 2]

and so on.

Beginner's question about a recursion example in JS

2 Answers2