Trying to understand why recursive code works

Tell us what’s happening:
I feel like I am missing something at the most basic level with this challenge, looking at the other two forum topics on it I am still not fully understanding why the code below works.

Using this example:
sum([2, 3, 4, 5], 3) should equal 9.

My understanding here (3) means “use the first three numbers in the array”, so we want our code to recursively select 2, 3 and 4 and add them together. On a side note, how does this factor in with zero-based indexing? Am I right in thinking the (n - 1) makes it start counting from 2 down to 0?

This is the line I am not understanding:
return sum(arr, n - 1) + arr[n - 1];

I half get that the first part is what makes it run until n = 0 and the second part is selecting different parts of the array (I think??) but I would greatly appreciate some help / a breakdown of what that line does.

Thanks.

Your code so far


function sum(arr, n) {
// Only change code below this line
if (n <= 0) {
  return 0;
} else {
  return sum(arr, n - 1) + arr[n - 1];
}
// Only change code above this line
}

Your browser information:

Challenge: Replace Loops using Recursion

Link to the challenge:

I’ll try a slightly different approach on this topic.

Let’s change the sum function so that it’s not recursive. Let’s make it:

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

I made one change. Now it’s calling a function named dummy instead of calling itself recursively. It still passes in the same args to dummy. It still adds the result from dummy to arr[n-1]. Everything is exactly the same except that now we call dummy. And the only thing dummy does is:

function dummy(arr, n) {
  return 0;
}

Now if you call sum([1,2], 2), what happens? Well, n is greater than 0 so we hit the else statement which would execute:

return dummy([1,2], 1) + arr[1];

We know what the values in the return statement are. dummy always returns 0 and arr[1] is 1, so the return would return the value 1. The point is that the return statement just executes the dummy function and then adds it to arr[n-1]. What the dummy function does is completely independent from what the sum function does. sum doesn’t need to know anything about the dummy function. It just calls it, gets the value, and adds it to arr[n-1].

Recursion is just like calling any other function. You call the function, passing in values, and the function returns a value that you can use, just like we did with dummy. The only difference is that instead of calling dummy we are calling the function that we are are actually in, we are calling the function itself. But this doesn’t make it any different than calling a different function like dummy. There is no magic going on here. We are still passing values into the function, getting a result, and then doing something with that result. So you can think of a recursive call to sum as calling a completely different function that you pass values into and get a result back from.

Now what if our dummy function above called another function?

function dummy(arr, n) {
  return foobar(arr, n - 1) + arr[n-1];  
}

We don’t even need to define the new foobar() function because it’s not important to know what it does. The only thing we care about is that it returns a value that we can use to add to arr[n-1] and then return a value. So now we have the following:

  • sum() calls dummy() to get a value, which it can then do whatever it wants with to return a value
  • dummy() calls foobar() to get a value, which it can also do whatever it wants with to return a value

Can you see how sum() has to wait for dummy() to return a value before it can return a value? And likewise, dummy() has to wait for foobar() to return a value before it can return a value? And if foobar() called a function then it would have to wait for that function to return a value before it could return a value. Each return statement is dependent upon another function to return a value.

Recursion is the same concept. Every time you make a recursive call you are just adding another level of waiting for a function to return a value so that you can do something with that value. Don’t get too hung up on the fact that you are calling the function itself. Even though it has the same name it is really being treated as a completely different function. So with recursion we have:

  • sum() calls sum() (first recursive call) to get a value, which it can then do whatever it wants with to return a value
  • the first recursive call to sum() calls sum() (second recursive call) to get a value, which it can then do whatever it wants with to return a value
  • the second recursive call to sum() calls sum() (third recursive call) to get a value, which it can then do whatever it wants with to return a value

and so on… Each time we call sum() we are a starting a new independent function and waiting for its return value. But at some point we’ll need to stop these recursive calls, which is where the base case comes in:

if (n <= 0) {
  return 0;
}

Remember that each time we call sum() we are reducing the second arg by one:

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

That second arg reduces the value of n by 1.

So at some point the second arg passed into sum() will equal 0 and sum() won’t call itself because it will just return 0. Just like our original dummy() function above returned 0. That’s what the base case is for in a recursive function, to stop the recursive calls so they don’t go on forever. When we reach the base case then we can finally start getting all those values from the functions we are waiting on to return a value and work our way back up to the first call of sum().

4 Likes

Thanks a lot for your reply!!

So looking at the return sum(arr, n - 1) as its own function, that purely exists to reduce n to base case and stop counting right? and the arr[n - 1] part is taking a value from the array each time it counts down so by 0 they can all be added up at the end?

I think i’m getting it :crossed_fingers:

I think you are too.

The concept of recursion is really not too difficult if you keep in mind that it is really nothing more than calling a function and getting a return value to work with, just like you would with any other non-recursive function.

The tricky part is actually writing the recursive function properly so it doesn’t call itself forever. That just takes a little practice.

1 Like