Trouble with Recursion

After reading MDN and watching several tutorials Im still struggling to firmly grasp recursion.

I’ll use the first challenge from the JS curriculum as an example:

 function sum(arr, n) {
if (n <=0){
  return 0
  
}else return sum(arr , n -1) + arr[n - 1];
}

I am able to come to this answer however I’m not totally understanding how it works.

A test condition example would be sum([2, 3, 4], 1) should equal 2.

So if I pass that in:

if  (1 <= 0){
return 0  //this evaluates as false so we move on//
} else return sum([2 , 3 , 4], 1)  + [2 , 3 , 4][n-1];
//This line is where I get confused 

I am confused on how to calculate the line in my head.

In my head:

([2 , 3 , 4] , 1)
I dont see any math that can be done here? So we add that line to:
[2 , 3 ,4][1-1];

Some math can be done here however Im confused as to what exactly. The array is multiply to the index of n -1? So am I multiplying (in this case) everything by 0? Or just 2 since thats technically index 0?

In my head this simplifies to:

([2 ,3 ,4] , 1) + [0][0]

Or:

([2 ,3 ,4]) , 1 + [0 , 3 ,4][0]

Either way both result in n = 0 which would satisfy the first condition of the if statment returning 0 ultimetly.

However the test condition says that

function sum([2 ,3 ,4]) , 1)

Should return as 2? :melting_face:

Can someone help me out here :sweat_smile:

Any and all help is appreciated, thanks in advance!

This isn’t quite right. When you hit the else statement you get:

return sum([2,3,4], 0) + 2;

If n is 1 initially, then n-1 is 0 and thus sum(arr, n-1) is sum([2,3,4], 0). And then you add arr[n-1] which is arr[0] which is 2.

arr[n-1] isn’t multiplication. It’s getting the value in the array at position n-1.

1 Like

Thanks for the reply, im closer but still a bit confused.

If we pass in
sum([2 , 3 , 4, 5] , 3)

Accoring to the test condition this should equal 9
So if I pass it in to:

sum([arr] , n - 1) + [arr][n -1)

I get

sum ([2 ,3 ,4 ,5] , 3 - 1) + [2 ,3 ,4 ,5][3 - 1];

Which simplifies to:

sum ([2 ,3 ,4 ,5] , 2) + 4;

How does this equal 9?

Thanks again for the help! I really appreciate it!

You are definitely on the right track.

You stated correctly that it simplifies to:

sum([2 ,3 ,4 ,5], 2) + 4;

So what is the value of sum([2 ,3 ,4 ,5], 2)?

1 Like

I honeslty have no idea of how to simplify:

sum([2 , 3, 4, 5] , 2)

Obviously is the final sum is 9 it needs to simplify to 5.

A guess I have is that the line above wants me to add the first 2items of the array, however I dont see how the code knows to do this. Also since arrays use 0 based indexing wouldn’t 2 mean it wants me to add the first 3 values? Meaning wed get 9? Which added to 4 would be 13?

I think you do, perhaps you just don’t realize that you already simplified sum([2,3,4,5], 3). So why wouldn’t you do the same thing to simplify sum([2,3,4,5], 2)? Don’t worry about recursion at this point. Pretend you are calling this for the first time. What would the simplified version of sum([2,3,4,5], 2) be?

1 Like

If 2 the to the right of the array is telling me to go to index 2 of the array that would be 4, correct?

Which would ultimately get us 8?

Unless were not usint 0 based indexing which would be 3 which would ultimately get us 7.

Unless the 2 is not representing an index of the array which in that case I have no clue what ([2 ,3 ,4 ,5] , 2) would simplify to.

You didn’t simplify it properly. Why didn’t you do the same thing you did for sum([2 , 3 , 4, 5] , 3). You did that one perfectly. You got sum ([2 ,3 ,4 ,5] , 2) + 4.

Please do the same for sum ([2 ,3 ,4 ,5] , 2). No guessing. Show your work.

P.S. We’re not really “simplifying” here. We are just passing the arguments into the function sum and getting the output. That’s what you need to do for sum ([2 ,3 ,4 ,5] , 2).

Ok so:

([2 ,3 , 4 ,5] , 3)

Is what we are passing into:

sum([arr] , n - 1) + arr[n - 1]

So:

sum([2 ,3 ,4 ,5] , 3 -1) + [2 ,3 ,4 ,5][3 - 1]

Which simplifies to:

sum([2 ,3 ,4 ,5] , 2) + 4

Which is where im confused.

If im to interpret: ([2 ,3 ,4 ,5] , 2])

As find the value of the arr index 2 that would be 4. Which would he 4 + 4 which would equal 8.

Where am I going wrong?

Forget about the recursion for now. Please. Forget about your original sum([2 ,3 , 4 ,5] , 3). I don’t want to see that again for a while :slight_smile:

Please answer me this. What is the return value of sum([2 ,3 ,4 ,5] , 2)? Until you answer this question we can’t go any further.

It has to be 5.

As to how we get there,

I have absolutely no idea

I’m not sure why you are refusing to answer my question? You know how to use the sum function because you already did it for sum([2 , 3 , 4, 5] , 3). Do you remember that? Do you remember how you converted that to sum ([2 ,3 ,4 ,5] , 2) + 4?

All I am asking you to do is to do that conversion for sum([2 , 3 , 4, 5] , 2). I’m finding it hard to believe you can’t do that when you did it so nicely for sum([2 , 3 , 4, 5] , 3).

Ok i see what your asking now (I think).

sum([2 , 3, 4, 5] , 1) + 3

Would be the output if we put

([2 ,3 ,4 ,5] , 2)

Into:

sum([arr] , n - 1) + [arr][n - 1]

Correct?

Awesome. So now you know that

sum([2, 3, 4, 5], 2) === sum([2, 3, 4, 5], 1) + 3 

This is a huge step. Now let’s go back to the original function call of sum([2 , 3 , 4, 5] , 3). Remember what that produced?

sum([2 , 3 , 4, 5] , 3) === sum([2 ,3 ,4 ,5] , 2) + 4

Now look closely at the right side of that equation. The first part in particular. It is sum([2 ,3 ,4 ,5] , 2). Now didn’t you just figure that out? You did. The output is sum([2 , 3, 4, 5] , 1) + 3. So it seems like we can replace sum([2 ,3 ,4 ,5] , 2) with sum([2 , 3, 4, 5] , 1) + 3 since they are equal, right?

So let’s look at this again, starting with the original function call and making the replacement you just figured out.

sum([2 , 3 , 4, 5] , 3) === sum([2 ,3 ,4 ,5] , 2) + 4
sum([2 , 3 , 4, 5] , 3) === sum([2 , 3, 4, 5] , 1) + 3 + 4

Does this replacement make sense to you? Now you have one more replacement to do. What is the output for sum([2 , 3, 4, 5] , 1). No guessing. No just saying “it has to be 2”. I want to know what the function returns.

Ok so

sum([2 ,3 ,4 ,5] , 3) === sum([2 ,3 ,4 ,5] , 2) + 4
Then:

sum([2 ,3 ,4 ,5] , 2) === sum([2 ,3 ,4 ,5] , 1) + 3

Then:

sum([2 ,3 ,4 ,5] , 1) === sum([2 ,3 ,4 ,5] , 0) + 2

Correct?

I think you got it. And what does sum([2 ,3 ,4 ,5] , 0) equal? That’s your base case. So the recursion will stop there, and then you are left with all of those numbers to add up. 0 + 2 + 3 + 4 === 9!

The thing to remember is that each recursive call is its own function call and doesn’t really depend on what happened before it. You are passing values into the function each time and returning a value based only on what was passed into the function. That’s why I was so insistent that you tell me the return value for each recursive call and I didn’t care about the actual recursion at the moment.

So now the replacement sequence looks like:

sum([2 , 3 , 4, 5] , 3) === sum([2 ,3 ,4 ,5] , 2) + 4
sum([2 , 3 , 4, 5] , 3) === sum([2 , 3, 4, 5] , 1) + 3 + 4
sum([2 , 3 , 4, 5] , 3) === sum([2 , 3, 4, 5] , 0) + 2 + 3 + 4
sum([2 , 3 , 4, 5] , 3) === 0 + 2 + 3 + 4
1 Like

Ok Im much closer now. I guess my only remaining question would be how the code is telling me to add all those value together?

Can
sum([arr] , n - 1) + [arr][n - 1]

Be repleaced with the pseudo code

sum(next arry and n value to pass in at the beginning of the function until n <= 0 is reached) + (the values that will ultimately be added together)

This code will have to loop (recurse?) 4 times to get 9?

I guess my confusion come from me reading the + between the two statments as the code doing an addition operation?

Am I hitting close to home at least?

Look at the else statement in the function:

return sum(arr , n -1) + arr[n - 1];

Isn’t that adding two values together? That’s where the addition is taking place. You are adding the return value of sum(arr , n -1) to the value of arr[n - 1]. The only wrinkle here is that you have to then wait for sum(arr , n -1) to return a value before you can add these two together. But don’t let it throw you that it is a recursive call. It’s just like calling any other function and waiting for its return value. For example, let’s say we had the following function:

function addTogether(num1, num2) {
  return num1 + num2;
}

This is a pretty simple function. I trust you understand what it does. So now let’s pretend the else statement in sum returned the following:

else {
  return addTogether(5, 10) + arr[n-1];
}

I bet you could tell me right away what that would return. It doesn’t seem weird at all to have the addTogether function in that return statement, does it. You know that you are adding the value at arr[n-1] with the value returned by addTogether(5, 10). But we have to wait for the addTogether function to return its value before we can add it to arr[n-1]. In other words, first the function addTogether is called, and we wait for its return value, and only once we get the return value can we add it to arr[n-1].

Recursive calls are the same thing. The only difference is that each recursive call will make another recursive call until we reach the base case, at which point we just return a single value. Look again at the last replacement sequence I posted. That’s all we are doing, waiting for each recursive call to return its value.