Replace Loops using Recursion: How does it work?

Hello,

would anyone explain to me in small bits how this code works and why there has to be return 0 in the if statement, please?

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 answer is greatly appreciated, thank you! :slightly_smiling_face:

Recursion is just the act of a function calling itself.

In this case it needs the if (n <= 0) conditional to know when to break and stop calling itself.

Let’s say arr = [1, 2, 3] and n = 3, and call sum(arr, n).
The code will now check to see if (n <= 0), which is false, and return sum(arr, 3-2)

The code will then check to see if (n <= 0), which is false, and return sum(arr, 2-1)

The code will then check to see if (n <= 0), which is false, and return sum(arr, 1-1)

The code will then check to see if(n <= 0), which is true, so it will return 0 and stop calling itself. At this point the code will work its back up the call stack. Returning in order:

sum(arr, 0) which equals 0
sum(arr, 1) which equals 0 + 1
sum(arr, 2) which equals 1 +2
sum(arr, 3) which equals 3 + 3

so our returned value will end up being 6! The program kinds of digs this big hole of function calls. When the final return statement is met, it works its way from the bottom all the way back to the top and gives us our desired output.

I still don’t get it.

Let me explain, in as much detail as possible, step by step, how I think the code works:

  1. We call the function sum(arr, n) and give it arguments of array [1, 2, 3] and number 3
  2. The function checks if n <= 0, which in this case is false, so the if statement is not executed
  3. The else statement is executed and returns the same function, the only difference is that n = n - 1, giving us n = 2
  4. The function checks if n <= 0, which in this case is false, so the if statement is not executed
  5. The else statement is executed and returns the same function, the only difference is that n = n - 1, giving us n = 1
  6. The function checks if n <= 0, which in this case is false, so the if statement is not executed
  7. The else statement is executed and returns the same function, the only difference is that n = n - 1, giving us n = 0
  8. The function checks if n <= 0, which in this case is true. The function has reached the base case so it stopped calling itself NOW. The function should return 0 and that’s it, we’re done.

If the function calls itself until it reaches the base case and then it executes the if statement and stops calling itself how do we end up with return value of 6? When and where does the function add arr[n - 1] to the return value?

If you don’t know what the call stack is i would recommend looking it up. It can be very difficult understanding what is going on with recursion if you don’t know what is really happening when you make a function call. Basically every time you call a function, it gets put on the stack, run, then returns a value to where it was called and popped off the stack. With recursion that gets a little more complex because your function calls itself, so its actually making multiple versions of itself. There all kinda of “chained together” because there expecting a result from each of those function calls and are waiting patiently for the answer.

So in the function when it says sum(arr, n - 1) + arr[n - 1], you can kind of think of it more like ? + "some number from the array arr at index n-1". That function call needs to be run for ? to be a number.

You have a good understanding of the first half of how its building up the stack, but are missing the part where it all “collapses” and we end up with a nice clean answer. Remember that when a function is called its run, then its value is returned to where it was called from. So when we reach the last function call that will be our base case the sum(arr, n - 1) part of the return of the function call before that one actually becomes a number, which is 0 because of the base case returning 0. So now ? + "some number from the array arr at index n-1" is 0 + 1, which is just 1, and we return that to where it was called from. And so on and so on till all those numbers are added together nice and neatly.

Watch it running might be better then my wordy explanation.

1 Like