Basic JavaScript - Use Recursion to Create a Range of Numbers

JavaScript
1

Hello, I’ve just completed the Basic JavaScript portion of the JavaScript curriculum. I completed the few recursion lessons without the hints, but they’re pretty simple, considering they’re nearly identical to the example questions. I’ve watched a few youtube videos, now trying to really understand recursion, but I still don’t feel comfortable with it at all. I get the gist of recursion, it’s a function which calls itself, and you need a base case and recursive case…

But what I don’t get is the intricate workings of what’s happening behind the scenes when the recursive call is ‘stacking’, and then when the basecase is met and returned, how it begins to unpack, or work back through all those stacks. (sorry if that language is confusing, I don’t have the correct terminology yet).

The first piece of code below was written to pass the last lesson of the chapter. Below that is a piece of code I was playing around with to see if I could write it a different way, however, it doesn’t work and I don’t know why. It ends with only 1 being in the array. I have been using PythonTutor to try and step through problems to better understand it, but PythonTutor doesn’t work very well for showing what exactly is going on within recursive functions and how they’re recalled when the basecase is met.

//first piece of code

function rangeOfNumbers(startNum, endNum) {
  if (startNum > endNum) {
    return [];
  } 
  else {
    const rangeArray = rangeOfNumbers(startNum + 1, endNum);
    rangeArray.unshift(startNum);
    return rangeArray
  }
};

//second piece of code which doesn’t work and only displays [ 1 ] at end.

function rangeOfNumbers(startNum, endNum) {
  const rangeArray = [];
  if (startNum > endNum) {
    return
  } 
  else {
    rangeOfNumbers(startNum + 1, endNum);
    rangeArray.unshift(startNum);
    return rangeArray
  }
};
console.log(rangeOfNumbers(1, 5));

I think the reason I’m not fully understanding recursion is because I’m not grasping what’s going on behind the scenes when the recursive function is called within the function itself… I don’t think I’m comprehending how that data is stored (stacked?) as the recursive functions are called, and what exactly happens when the base case is reached and returned, thereby recalling all those previous stacks… For example, this piece of code:
const rangeArray = rangeOfNumbers(startNum + 1, endNum);

When the basecase is met, why is the ‘const rangeArray’ only filled with the empty array from the basecase return? Why isn’t each rangeOfNumbers(startNum + 1, endNum) which is being recalled at that point being stored in to rangeArray as it’s cycling back through all the stacks?

I’m sorry my language isn’t correct, and confusing for your to follow, just started working through this earlier in the week, so my vocabulary isn’t strong yet. Hopefully you can understand what I was trying to say.

To summarize my questions:

  1. why doesn’t my second piece of code work, and it only displays [1]
  2. how exactly does the ‘stacking’ work whenrecursive calls are being made, and, when the basecase is met and return is triggered, how then are they worked back through…
  3. Why doesn’t the const rangeArray get changed as all the recursive calls are being returned.

Thanks for your help.

Link to the challenge:

2

Let’s pretend you had the following line of code:

const allNumbers = getAllNumbers();

I’m assuming you understand that the function call to getAllNumbers needs to be run and then the value returned by getAllNumbers is assigned to allNumbers. You understand this without having to know all of the technical details behind what is happening when getAllNumbers is executed.

The getAllNumbers function is defined as follows:

function getAllNumbers {
  return findAllNumbersBetween1And100();
}

Again, I’m assuming you understand that the function findAllNumbersBetween1And100 will need to be executed first and then the getAllNumbers function can return the value returned by findAllNumbersBetween1And100. And again, you don’t need to understand the technical details about call stacks and such to understand this.

The findAllNumbersBetween1And100 is defined as follows:

function findAllNumbersBetween1And100 {
  let array = [];
  for (let i=1, i < 101; i++) {
    array.push(getNumber(i));
  }
  return array;
}

Granted, this is a silly example, but again, I’m assuming you understand that each time there is a push to the array the function needs to call the getNumber function and wait for it to return a value before it can push that value to the array. Again, you don’t need to understand anything about call stacks and such to understand how this is working.

And of course, the getNumber function merely returns the value passed into it:

function getNumber(num) {
  return num;
}

As you can see above, each function is calling another function and has to wait for that called function to finish and return a value before it can proceed. Function A has to wait on Function B to return a value. Function B has to wait on Function C to return a value. Function C doesn’t need to call another function, it just returns a value (doesn’t this sound similar to a base case using recursion?). So once Function C is done executing and returns a value to Function B, then Function B can continue on from where it left off and then ultimately return a value to Function A. And then Function A can continue from where it left off.

I explained the above without having to go into any technical details about call stacks and such. And I’m assuming you probably understand it. Recursion is working the same way as explained above. The difference is that instead of each function calling a function with a different name, recursion is calling a function with the same name, specifically, the name of the function itself. But when the recursive call is made it is the same thing as if it called a function with a different name. In other words, recursive function calls and non-recursive function calls work the same way behind the scenes. So if you understand how non-recursive function calls then you understand how recursive function calls work.

My point here isn’t to say that it might not be helpful to understand about call stacks and such, but rather that it isn’t required in order to understand how recursion works. Not that recursion isn’t a little tricky (it is). But behind the scenes, non-recursive and recursive function calls work the same way. Each call causes the calling function to pause and wait for the called function to return a value. After the value is returned then the calling function can proceed.

The rangeArray variable is only visible in the calling function. Don’t think of it as a global variable that is affected by other function calls, because it is not. When the following line is executed:

const rangeArray = rangeOfNumbers(startNum + 1, endNum);

As discussed above, the function calls rangeOfNumbers and must wait for it to return a value, which will be assigned to rangeArray. Until that value is returned, rangeArray is an empty array. Nothing about rangeArray changes until the recursive function call returns a value. Think of it this way, what if instead we did:

const rangeArray = aDifferentRangeOfNumbers(startNum + 1, endNum);

Now we are calling a different function and it is obvious that we need to wait for that function to return a value which we can then assign to rangeArray. Would you think that the function aDifferentRangeOfNumbers function should have any affect on rangeArray while it is executing? No, it does whatever it is supposed to do, completely independent of rangeOfNumbers and then returns a value. Now suppose the aDifferentRangeOfNumbers function is defined exactly the same way as the rangeOfNumbers function. In essence, that would make it a recursive call because the two functions do exactly the same thing. So we can just do the recursive call instead, but the recursive call is still completely independent of the calling function.

Don’t let the fact that you are calling the same function inside of itself lead you into believing that some sort of “magic” is going on behind the scenes. Every recursive function call is an independent action, just like if you called a function with a different name. The recursive call only knows about the values you pass into it through the parameter list.

3

Hopefully my previous post gave you some insight into this. But just in case it wasn’t as clear as I intended, your second code is doing:

const rangeArray = [];
if {...}
else {
    rangeOfNumbers(startNum + 1, endNum);
    rangeArray.unshift(startNum);
    return rangeArray
}

You are calling rangeOfNumbers, which returns a value, but you aren’t doing anything with that return value. After the recursive call finishes, rangeArray is still equal to an empty array because you didn’t assign it to the return value of the recursive call. Then you add startNum to the beginning of rangeArray, which since it was empty after the recursive call means that after the unshift it will just have one item (the value of startNum) and that’s why it is returning a single number in the array.

Again, the recursive call itself does not have any affect on rangeArray. Unless you assign rangeArray the value of the recursive call then it will remain an empty array after the recursive call.

4

Thanks for your responses.

I think I am overcomplicating it at this point, I think I watched a youtube video or two, too many… Your responses definitely gave me some insight and I appreciate it.

One last thing I was curious about, which I think I confused everyone about with my ‘stacking’ talk… was regarding the recursion calls inside the function, once the return call was made in the base case, e.g.:

const rangeArray = rangeOfNumbers(startNum + 1, endNum);

now, say we called the original function with rangeOfNumbers(1, 5);

as the recursion calls cycle through numbers 1-5, some people were saying to view it as such:

rangeOfNumbers(1 + 1,  1)
  rangeOfNumbers(2 + 1,  1)
    rangeOfNumbers(3 + 1,  1)
       rangeOfNumbers(4 + 1,  1)  
         rangeOfNumbers(5 + 1,  1)  ---I know this will return []

But once the rangeOfNumbers(5+1, 1) returns , I don’t quite understand the process of what exactly the other functions are returning after that, or if there’s a better way to visualize it.

Thanks again for your help.

5

I’d start with a simpler example.

rangeOfNumbers(1, 3)

original function call

Using the original working function, the first thing that is going to happen is:

const rangeArray = rangeOfNumbers(2, 3);

We can’t assign the value to rangeArray until rangeOfNumbers(2, 3) returns a value. Just to recap, at this point (inside the original function call), the value of startNum is 1.

first recursive call

So now we make the recursive call rangeOfNumbers(2, 3) and again the first thing that happens is:

const rangeArray = rangeOfNumbers(3, 3);

Again, we have to wait right here until we get a value from the recursive call. To recap, we are now inside the first recursive call and the value of startNum is 2. This is a completely separate startNum from the startNum in the original function call. Likewise, this is a completely separate rangeArray from the rangeArray in the original function call. This first recursive call knows nothing about the original function call. It only know the two numbers passed into it and the only thing it will do is return a value.

second recursive call

So now we make the recursive call to rangeOfNumbers(3, 3). And once again we get to:

const rangeArray = rangeOfNumbers(4, 3);

So now we are in the second recursive call and we need to wait for rangeOfNumbers(4, 3) to return a value before we can move on. Note that the value of startNum in this second recursive call is 3.

So now we execute rangeOfNumbers(4, 3) and we hit the base case and so rangeOfNumbers(4, 3) immediately returns an empty array. Notice that we have not left the second recursive call. There is no need to since rangeOfNumbers(4,3) immediately returns an empty array without making any further recursive calls.

Now that we have a value for rangeOfNumbers(4, 3) we can progress through the rest of the second recursive call:

else {
    const rangeArray = [];
    rangeArray.unshift(3);
    return [3];
}

I have filled in the actual values that are used in the second recursive call. The value of startNum is 3 since the second recursive call is rangeOfNumbers(3, 3). And thus the second recursive call returns the value [3].

returning to first recursive call

So now that the second recursive call has returned a value, the first recursive call can continue on, and it will look like this:

else {
    const rangeArray = [3];
    rangeArray.unshift(2);
    return [2, 3];
}

To refresh our memory, the first recursive call was waiting here:

const rangeArray = rangeOfNumbers(3, 3);

We now know that rangeOfNumbers(3, 3) returns [3] so rangeArray in the first recursive call gets set to [3]. And the value of startNum in the first recursive call was 2. So we add 2 to the beginning of the array and then return it.

returning to original function call

And now that the first recursive call has returned [2, 3], the original function call can proceed. Recall that the original function call was waiting at:

const rangeArray = rangeOfNumbers(2, 3);

We now know that rangeOfNumbers(2, 3) returns [2, 3] so we can continue on in the original function call as follows:

else {
    const rangeArray = [2, 3];
    rangeArray.unshift(1);
    return [1, 2, 3];
}

And so our original function call returns the value [1, 2, 3].

rangeOfNumbers(1, 3) // waits for rangeOfNumbers(2, 3)
    rangeOfNumbers(2, 3) // waits for rangeOfNumbers(3, 3)
        rangeOfNumbers(3, 3) // waits for rangeOfNumbers(4,3)
             [] // return value of rangeOfNumbers(4,3)
        [3] // return value of rangeOfNumbers(3, 3)
    [2, 3] // return value of rangeOfNumbers(2, 3)
[1, 2, 3] // return value of rangeOfNumbers(1, 3)

Each function call builds on the array that it received from the recursive call it made.

6

Thank you!
I believe you nailed this explanation.
I’m going to review it everyday until it sinks in.

7

Also try counting down using endNum-1, rather than startNum+1

8

those comments are so detailed XD and I give-up to read them. But for my point of view, the reason why your second pieces of code fail and only return [1] is const rangeArray = called every time you run the function rangeOfNumbers. So the code only consider the first unshift which simply putting 1 inside the array when rangeOfNumber(1,5)

9

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.