Trouble understanding JS recursive countdown function from freeCodeCamp

Question

So, I've already understood the idea of recursion in JavaScript (having a function that loops itself until it reaches a base condition, at which point it stops and returns the final result), but I'm having a bit of a headache when I apply that to the actual syntax of trying to apply it to create arrays.

Let's use this countdown exercise from freeCodeCamp as an example. This is the correct result:

function countdown(n) {
  if (n < 1) {
    return [];
  } else {
    const arr = countdown(n - 1);
    arr.unshift(n);
    return arr;
  }
}

The idea here is obviously to have a function to count down from a given n to 1. I understand the idea, but I have a couple of questions:

1 - Why is the array declared as a constant and assigned to the recursion call? Shouldn't the array be better declared outside as a variable (since it changes value)– and doesn't its current position mean that it is declared (and over-written) every time the recursion takes place?

2 - I get the unshifting of the current value, but why is it declared after the recursive call? Shouldn't it be positioned before (one line above) so as to unshift the value before the function loops itself?

3 - Similarly, why is the full final array returned within the else loop? Shouldn't it be better returned outside, or on the base condition above, so as to not be returned every time the function loops?

As it is, my understanding is that when n reaches 0, the loop should return an empty array, and not the full array that has been created with the recursion.

~ ~ ~

FINAL EDIT / UNDERSTANDING: Thanks to every answer! So, if my current understanding is correct, recursion does not loop the function, as I initially thought – instead, it sort of "opens" a call of "chained functions" that goes downwards until it finds and resolves the base case.

When that "base" case or function is resolved, the chain goes "up", so to say, resolving each recursive step above, .unshifting each n value, and returning the resulting array "upwards", until we reach the initial n value, at which point the final array is returned, and the function is exited.

I think I (sort of) got the point now! Actually writing recursive functions won't be easier though, but I have a better grasp of how the process actually takes place.

Answer 1

Why is the array declared as a constant and assigned to the recursion call?

It is not. The array is variable. Every call to this function will return a new array. No arrays get "overwritten". const in JavaScript is merely used to declare a constant variable which has lexical scope (that is, the variable arr ceases to exist after return arr) and is constant (can't be mutated / assigned to).

I get the unshifting of the current value, but why is it declared after the recursive call? Shouldn't it be positioned before (one line above) so as to unshift the value before the function loops itself?

You can't position it above since the recursive call is required to obtain arr in the first place. After you have counted down from n-1 to 1, you must prepend n at the first position, which is what unshift does.

Similarly, why is the full final array returned within the else loop? Shouldn't it be better returned outside, or on the base condition above, so as to not be returned every time the function loops?

There is no such thing as an "else loop". The reason for returning the array there as well is that you want countdown(n) to return the array it has just generated, using the array countdown(n-1).

As it is, my understanding is that when n reaches 0, the loop should return an empty array, and not the full array that has been created with the recursion.

That's exactly what if (n < 1) return []; does.

---

That said, for the task at hand the recursive implementation given is highly suboptimal. First of all, you don't need the else since return will exit the function anyways:

function countdown(n) {
  if (n < 1) return [];

  const arr = countdown(n - 1);
  arr.unshift(n);
  return arr;
}

second, this is most readable (and performant) as a simple for loop:

function countdown(n) {
  const arr = Array(n)
  for (let i = 0; i < n; i++) arr[i] = n - i;
  return arr;
}

(bonus: the array size being known ahead of time can be leveraged using the Array constructor to prevent JS having to resize the Array as you push elements).

third, the current implementation has a quadratic time complexity of O(n²) because arr.unshift is a linear-time operation which is applied n times to arrays of length 0 to n-1.

Recursion is extremely useful when you need the stack (f.E. in a depth-first traversal). Creating a countdown doesn't require a stack. This is not using but rather abusing recursion to implement a highly suboptimal algorithm. If you - for whatever reason (perhaps you are forced to use a purely functional language that has no loops, only recursion?) - wanted to replace the perfectly fine for loop with a recursive call at all cost, simply use tail recursion and lexical scope (closures):

function countdown(n) {
  const arr = [];
  function loop(n) {
    if (n < 1) return;
    arr.push(n);
    loop(n-1);
  }
  loop(n);
  return arr;
}

or if you don't like closures, what about an optional arr parameter? This allows turning the recursion around since the caller now has the arr before the callee and can thus append its number before subsequent recursive calls do the same:

function countdown(n, arr = []) {
  if (n < 1) return arr;
  arr.push(n);
  countdown(n - 1, arr);
  return arr;
}

same result, but (IMO) cleaner, and most importantly, significantly faster code. Try running all these functions on n = 1e6 and you will see that the freeCodeCamp one fails to complete in a reasonable timeframe whereas the other ones finish almost instantly.