Understanding JS Recursion to Create an Array-CodePudding

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.

CodePudding user response：

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.

CodePudding user response：

I would just add to the first part of LMD's answer (I can't comment because of no reputation):

When you define constant array, you are not saying that the array is constant and can't change. You are creating constant reference to that array. So you still can edit its elements, but can not overwrite it with new array.

More info here: https://www.w3schools.com/jS/js_array_const.asp

CodePudding user response：

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?

The const declaration is block-scoped. The reference only exists inside the else-block. There is not one generic arr that is shared by each call. Instead, inside of each call to countdown, we get an if-condition. If that fails, we create the else block and assign a brand-new arr variable. When this is returned, and the function ends, that reference is gone, and only the function return value remains.

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?

First of all, be careful of "the function loops itself". Recursion is a different mechanism from looping; and although they have equal power, they are not at all the same.

But recall that the recursive call returns the result of calling this with n - 1. So

const arr = countdown(n - 1);

when called with n of 4 sets arr to [3, 2, 1]. Now that we have this value, we can do the unshift operation on it.

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?

Again, you need to stop thinking in terms of looping.

Here's an alternative way of thinking about it: For any smaller value of n than our current value, we assume that countdown will magically provide us the correct answer, and then, when we call it, we will prepend our n value to the result.

Recursion is simply the trick of making that magic work. If we know the answer to our simpler problem(s) and we can use these to build the answers to our more complex ones, then all we need is a way to stop breaking down into smaller problems: our base cases.

So, for countdown (3), we call our magical countdown (2) function, which returns [2, 1] and use unshift to prepend 3 and get [3, 2, 1]. Of course if we wanted to dig into how that magical countdown (2) actually worked, we could and we'd see that it called the magical countdown (1), getting [1] and prepended 2 to get [2, 1], and so on. The magic, it turns out, is rather mundane.

But that's what recursion is, at its core: the notion that there is a sequence of simpler and simpler problems, bottoming out in some base case(s), and that we can build our more complex result based on those simpler ones. But while writing the logic to do this, it's easiest to think of those simpler ones as magical.

CodePudding user response：

It might help to clarify how the code is working a little. Hopefully, the explanation clears up your questions a bit. Let's start with the most basic case:

countdown(0) - When you call countdown(0) your if-block runs and returns an empty array []. So we see that countdown(0) outputs []. This is the base case.

Next, let's imagine we call the function again, this time as:

countdown(1) - In this scenario the else block runs. We see that it calls countdown(0), which means the interpreter executes the function again, passing n as 0. Above we saw what happens when countdown(0) is called, it returns an empty array [], so that's what gets assigned to arr within the else block. We then unshift n (which is 1 here) onto this empty array, which adds 1 to the start of the array stored in arr. This is then returned. So we say that countdown(1) outputs [1].

Now let's see what happens if we were to call the function again with 2:

countdown(2) - Again, the else block runs, triggering a call to countdown(1). We saw above what occurs when this is called, we get back an array with [1], which is stored in the local variable arr, and we then .unshift(2) so that 2 is added to the beginning of the array which we then return. So we see that countdown(2) returns [2, 1].

When thinking about recursion, it can be helpful to think of it as breaking down your input until it's at a small enough value that it can't be broken down anymore (your base case). Once you hit that, you work your way back up, stitching together your previous calls now that you have "solved" the sub-problems.

To answer your questions more directly:

arr is assigned to the recursive call so that we can build upon the results it returned. If countdown(1) returns [1], then we can build onto that result by storing it in arr and unshift 2 onto it to calculate countdown(2). It could have been made let, but const is commonly used if the variable doesn't need to be reassigned. We don't want to move arr outside of the function as then calling countdown() multiple times will modify the same global array. You would also need to change your code so that we can gradually "build-up" the result by further recursive calls if you did that also, which is more of a "loop mindset" than a "recursive mindset".
Moving the .unshift() component before the recursive call wouldn't work as you wouldn't have anything to unshift to. The recursive call is what provides you with the array result of countdown(n-1) so that you can build onto that later by using .unshift().
Returning your array in the else block is what allows you to obtain results when n is greater than 0. In the countdown(1) example above, we need to return arr so that it outputs [1]. This needs to be in the else block because we're returning arr which is defined in that else-block (and hence can't be accessed outside of it).