Recursion lesson - Solution 1 - What is the code actually doing?

JavaScript
1

reference:
“Use Recursion to Create a Range of Numbers”

regarding the first solution:
function rangeOfNumbers(startNum, endNum) {
if (endNum - startNum === 0) {
return [startNum];
} else {
var numbers = rangeOfNumbers(startNum, endNum - 1);
numbers.push(endNum);
return numbers;
}
}

What I don’t understand:

I’m new to recursions, and especially using recursions on arrays confuses me.

What is the code actually doing?

also

is “var rangeOfNumbers(startNum, endNum-1)” refering to the indexes of the array?
I ask because if the end number is 10, wouldn’t it come out as 9 when the code runs the first time? So would’nt the array come out as [1,2,3,4,5,6,7,8,9] ?

2

Wow, just answered this same question last night. Below was my response. Regarding your specific question, its not refering to index of the array, but is recalling itself, but with the end number being one less. Hope the below helps:

Basically a recursive program is one that continues to call itself repeatedly to accomplish a task. That is what that line of code is doing. Lets look closer at that.

So basically rangeOfNumbers(startNum, endNum) wants to create an array with all the numbers from startNum to endNum. For our example lets use rangeOfNumbers(2,8). This could be done with a for loop:

for (let x=startNum; x < endNum+1; x++)
{numbers.push(x)}

but here we want to use recursion.

With recursion, you typically want the function to perform one step in the task, and then call itself to complete the rest of the tasks. In this instance, the line of code in question does that by calling itself, but with endNum - 1 instead:

rangeOfNumbers(2,7)

So that would make an array from 2 to 7, numbers = [2,3,4,5,6,7], so the only thing left to do is push the last number, endNum=8.

rangeOfNumbers(2,7) does the same thing, by recalling itself with endNum - 1, rangeOfNumbers(2,6)… which creates [2,3,4,5,6] and then pushes 7.

This repeates itself until the end condition is met, in this case when startNum === endNum. At that point it finally returns an array with just [startNum]. At that point, all the functions that were repeatedly called keep returning which builds the array of numbers.

Recursion is really tricky to explain. This process written out might look like this(each line being the recursive call):

 rangeOfNumbers (2,8) =          
  8 +  rangeOfNumbers (2,7)          returns [8,7,6,5,4,3,2]
    7 +  rangeOfNumbers (2,6)          returns [7,6,5,4,3,2]
      6 +  rangeOfNumbers (2,5)          returns [6,5,4,3,2]
        5 +  rangeOfNumbers (2,4)          returns [5,4,3,2]
          4 +  rangeOfNumbers (2,3)          returns [4,3,2]
            3 +  rangeOfNumbers (2,2)          returns [3,2]
              2                                  returns [2]
2 Likes
3

Thank you so much
I think I’m kind of starting to understand how it works now.
Especially with that diagram showing the process.

I’ll keep reviewing this.

Thanks again!

4

I know this is late but I am writing this out as much to help myself as to help you or other students. The thing that helped me the most in understanding recursion was this article. Specifically “The Call Stack” section. This drove home the fact that the return function IS NOT CALLED UNTIL THE FUNCTION REACHES ITS BASE CASE. Once it reaches the base case it starts working backwards through the call stack and returning those answers. For me this answered a lot of questions I had like why recursive functions returned values in the opposite order I expected. I’m surprised I do not see the call stack explanation in a lot of the answers here, I think that is why a lot of people are getting hung up on recursive functions. If I got anything wrong in here please correct me, I will edit or delete my comment if someone explains it better or more correctly.

4 Likes
5

I like your explanation.
Look what I found, it could be useful to visualize what you just said.
https://recursion.vercel.app/

Try to run this Python code there:

def fn(a, b):
  if b==1:
    return a
  else:
    return a + fn(a, b- 1)

It’s so cool to see how this process goes.

1 Like
6

That’s awesome! I often add “console.log” to the problems in fcc so I can better understand what is going on in the functions but this is a much clearer way to understand what is happening. I think fcc would benefit from adding functionality like this or at least a quick summary of the best ways to see how your code is working so you can better trouble shoot.

7

maybe, I don’t know
Anyway, pythontutor already exists for this kind of stuff

8

Thank you for your clear expaination.

But I have one question.

How can it create the array [2,3,4,5,6,7,8] instead of [8,7,6,5,4,3,2] ?

Because endNum is decreaseing by 1 and it is pushed to the end of the array.

Thank you

1 Like
9

If you have a question about a specific challenge as it relates to your written code for that challenge, just click the Ask for Help button located on the challenge. It will create a new topic with all code you have written and include a link to the challenge also. You will still be able to ask any questions in the post before submitting it to the forum.

Thank you.

1 Like
10