Help please! Replace Loops using Recursion

I need help understanding this

I coldn’t find the answer by myself so i looked in google for it. This works, but i don’t completely understand how it works. For example, why does it return 0 once the code finished running? Thanks in advance. By the way, the courses are really good, i appreciate them.
Your code so far


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

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/84.0.4147.105 Safari/537.36.

Challenge: Replace Loops using Recursion

Link to the challenge:

Hello~!

Let me see if I can help explain it. First, the return 0 portion is the “base case”. A recursive function needs to have a base case, or it will continue on for infinity (or until the browser crashes).

In order to understand recursion, we need to understand the call stack. As each function call gets generated, it is added to the stack. When the function calls end (because the base case is reached), the stack begins resolving. This happens in a “First-In-Last-Out” basis, or in the reverse direction of the call order.

If we break this down visually… Let’s create an array called myArray and call our function on it with an n value of 5.

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

This function call will give us the sum of the first 3 elements in the array. But what does that look like?

sum(myArray, 3) // returns another function call plus arr[n-1]
  sum(myArray, 2) + myArray[3-1] // returns another function call, but now n is 2
    sum(myArray, 1) + myArray[3-1] + myArray[2-1] // keep going...
      sum(myArray, 0) + myArray[3-1] + myArray[2-1] + myArray[1-1] // now n is 0.
//with n being 0, our base case is reached. The stack begins resolving here. 
      0 + myArray[3-1] + myArray[2-1] + myArray[1-1]
    0 + myArray[2] + myArray[1] + myArray[0]
  0 + 3 + 2 + 1
6 //this is the final result of our function call

I hope this visualisation helps you understand how the recursion works. :slight_smile:

2 Likes

Hi,

You know, I looked at this and I thought 'tiens, I thought I got this and now I really really don’t. I’m sure you are right but I don’t get it. You are saying:

So this means that sum(myArray, 0) actually resolves to zero. Why is that? Maybe it’s so simple I don’t see it. Since the function call is really empty and the action is going on adding something to the call (which I didn’t know was possible), something empty is really zero? Why is there no error?

Enfin, greets,
Karin

Yes, the sum(myArray, 0) resolves to 0, because of the base case you established:

if (n <=0) {
  return 0
}
1 Like

Hi,

Right, I knew it was simple. It was just so weird to look at. Thanks, I’m going to bed all calmed down now. :grinning:

Greets,
Karin

1 Like

Thanks a lot :slight_smile:

1 Like