Replace Loops using Recursion questions

JavaScript
1

Hi I read articles on recursion and read the example question here, but can’t seem to understand the question enough to be able to explain it:

Write a recursive function, sum(arr, n) , that returns the sum of the first n elements of an array arr .

I understand that a value minus itself is used to count down or up in a recursion, but the idea of counting n elements and using that isn’t clicking in my mind. I can solve this question, but I don’t understand how it’s

return multiply(arr, n - 1) * arr[n - 1];

    if (n <= 0) {
      return 1;
    } else {
      return multiply(arr, n - 1) * arr[n - 1];
    }
  }

Challenge: Replace Loops using Recursion

Link to the challenge:

2

Yes, recursion melts the brains of everyone learning it. It even melts the brains of some of us that have done it before.

return multiply(arr, n - 1) * arr[n - 1];

So, in each iteration of this function, it is multiplying in the nth element (remembering that it is zero indexed.) So, if the number is 5, we want the 5th element or the element at the index of 4. That is the arr[n - 1].

That is being multiplied by the result of multiply(arr, n - 1). So, this function is being called with the number 4 as the second parameter, meaning that it will multiply in the 4th element, or the one at index 3.

That will in turn make a call with 3, which will make a call will 2, etc.

Another way to think of it, first we return:

multiply(arr, 5);

That is going to return:

multiply(arr, 4) * arr[4];

That first element is going to expand out and give us:

multiply(arr, 3) * arr[3] * arr[4];

and then:

multiply(arr, 2) * arr[2] * arr[3] * arr[4];

and:

multiply(arr, 1) * arr[1] * arr[2] * arr[3] * arr[4];

and:

multiply(arr, 0) * arr[0] * arr[1] * arr[2] * arr[3] * arr[4];

and then n is now 0 so it returns to 1:

1 * arr[0] * arr[1] * arr[2] * arr[3] * arr[4];

So, on that iteration, there was no recursive call so finally the functions ends and the whole call stack unfolds back to the initial call which returns our result.

2 Likes
3

Right so this is (arr, 5-1) * arr[5-1] and so on until n <= 0 right?

By index of 4 you mean 0,1,2,3,4 (4 being the 5th? or arr[5-1]?)

If I understand correctly, it’s not that it’s hard to understand the function it’s just hard to wrap my head around the format. I don’t understand the arr and n function being involved in such a function. In general I never liked math when things that didn’t add up were being used in a problem. Looking at this problem with just that in front of me was confusing:

Write a recursive function, sum(arr, n) , that returns the sum of the first n elements of an array arr .

4

Right so this is (arr, 5-1) * arr[5-1] and so on until n <= 0 right?

Yes.

By index of 4 you mean 0,1,2,3,4 (4 being the 5th? or arr[5-1]?

Yes.

If I understand correctly, it’s not that it’s hard to understand the function it’s just hard to wrap my head around the format.

Right, it’s not the function itself that is difficult, just that it’s calling itself recursively. I think to really understand it, you have to understand the call stack and what it is doing. Each time a new function is called, the old one gets pushed onto the call stack, frozen in carbonite. It keeps doing that. Then it starts popping those old calls off the call stack until it is done.

I might look through some youtube videos. I’m sure someone does a good job explaining what is happening.

5

Thanks you yourself did a great job

6

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.