# 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.

`([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?

Can someone help me out here

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

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)`.

`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 {
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]`.