Basic JavaScript - Replace Loops using Recursion

JavaScript
1

So, I understand the basic idea of recursion, and can easily solve the challenge by just adapting the example code.

However, I just can’t wrap my head around what the code is actually doing. I’ve trawled every post I could find here and found a couple of sort-of-useful explanations but nothing that really made it click for me.

I would love if someone could walk through, step-by-step, what the example code (below) is actually doing. In particular, I’m very confused by:

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

I don’t understand what is actually being done here, or how. Someone gave a good explanation of the call stack on another thread and how it essentially stops and stores the function call every time until the base case is fulfilled, but I don’t understand the exact order/process of this. What gets multiplied by what each time? Where does the code get to before the function restarts? What precisely is stored in the call stack?

Please relate your explanation specifically to the line of code I highlighted, rather than just explaining recursion in general!

Many thanks.

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

Challenge: Basic JavaScript - Replace Loops using Recursion

Link to the challenge:

2

Hi @Carces,
This video is a step-by-step explanation/solution of the lesson “replace loops using recursion” freeCodecamp: "Replace Loops Using Recursion", Solution. - YouTube

Cheers and happy coding :slight_smile:

1 Like
3

The best way to walk through this is by using a real example. What happens when you call:

multiply([3,4], 2);

You hit the else statement (since n > 0) and thus the function returns:

return multiply([3,4], 1) * 4;

All I’ve done is stick in the real values into the return statement. Do you see how I got those values?

Since this return statement calls multiply again, we have to do it one more time. Again, the function call multiply([3,4], 1) hits the else statement because n > 0 and it returns:

return multiply([3,4], 0) * 3;

So this means that return multiply([3,4], 1) * 4 is equal to return multiply([3,4], 0) * 3 * 4. Do you see how we did that? We are just solving for each call to multiply and putting that value back into the original return statement. But we still have one more call to multiply:

multiply([3,4], 0)

This one is easy since n === 0 and so we hit the base case and it returns 1. So we can put 1 into the equation and we get

return 1 * 3 * 4;

One more time, these are the steps:

return multiply([3,4], 1) * 4;  // original return
return multiply([3,4], 0) * 3 * 4 // original return after one recursion
return 1 * 3 * 4 // original return after two recursions

We are just solving for multiply in each one until we get to the base case.

1 Like
4

Thanks, the middle of your explanation assumed a bit too much about my maths knowledge and kind of lost me, but writing out the steps at the end helped, especially in understanding the order of what happens.

The only thing I don’t understand now is why the final calculation is 1 * 3 * 4 when it’s still multiplied by n - 1

Your last step was:
return 1 * 3 * 4

However, what happened to the ’ *arr[n-1] ’ in that final call?
It feels like it should be:
1 * 3 * 4 * arr[n-1]

Is that just ignored because there’s no such thing as a -1 index in an array?

5

The final calculation (or recursion) is not multiplied by arr[n-1]. The final recursion is when we reach the base case, that that just returns 1. So when we reach the base case we are no longer calling the multiply function.

if (n <= 0) {
  return 1; // no recursive call, just return 1
}
1 Like
6

Recursion sees the base case condition (n == 0) and returns 1 before multiply(arr, n - 1) * arr[n - 1] has a chance to run with n == 0. The function never runs with n == 0 because the base case condition catches it and returns 1 before the next part of the code can run.

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

7

Thanks for walking me through this, everyone, really appreciate you lovely people on the forums sharing your time. The internet at its best!