# Problem understanding this recursion example

Tell us what’s happening:

Hi, I am really stuck with this one. Though I understand recursion through other examples, I can’t figure out how this example works.

What is happening in the line below between the two parameters arr and n-1? What is being multiplied ? What makes me confused is that the function has two paramenters: arr and n. I don’t understand their relationship here.

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

Thanks for any help, really appreciated!

``````
function sum(arr, n) {
// Only change code below this line

// Only change code above this line
}

``````

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

Challenge: Replace Loops using Recursion

1 Like

`multiply(arr, n - 1)` at that point still needs to be computed, only after that the actual multiplication can happen here.

Keep in mind that `multiply(arr, n-1)`, depending on the current `n` may also need to wait for the computation `multiply(arr, n-2)` and so on all the way to the base case (`n <= 1` in this case).

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

multiply([2, 5], 2);
``````

Let’s break down what happens with this short example, where `arr` is `[2, 5]` and `n` is 2.

On the first run through `n` is 2 which is not less than or equal to 0, so the else block is executed.

``````multiply([2, 5], 2) === multiply([2, 5], 1) * 5
``````

Now we have a new function call with `n` as 1. Again, 1 is not less than or equal to 0 so the else block is executed.

``````multiply([2, 5], 1) === multiply([2, 5], 0) * 2
``````

Now we’ve reached the base case. 0 is less than or equal to 0, so the if block is executed.

``````multiply([2, 5], 0) === 1
``````

Now we can go back through the tree, plugging in values as we go (think back to algebra in school).

`multiply([2, 5], 1) === multiply([2, 5], 0) * 2`
Plug in 1 for `multiply([2, 5], 0)` and you get `1 * 2`.
Therefore `multiply([2, 5], 1)` is 2.

`multiply([2, 5], 2) === multiply([2, 5], 1) * 5`
Plug in 2 for `multiply([2, 5], 1)` and you get `2 * 5`.
Therefore `multiply([2, 5], 2)` is 10, and that’s our answer.

3 Likes

Thank you so much for the walkthrough. I understand the logic in the function now. What I still dont get is how does the function know it has to multiply n numer of array items together? Where is it defined that

([2, 5], 1) x 5 = 5 x 2

? is it intrinsec to this kind of notation?
I feel I’m missing something really basic here…

`n` defines how many array elements are to multiply. Notice that in example first function call was with `n == 2`, but with each recursive call `n` was decremented by `1`. Until it reaches the base case, which in here is `n <= 0`.

``````multiply([2, 5], 2) // (arr = [2, 5]; n = 2)
multiply(arr, 1) * arr[1] // (n == 2; n - 1 == 1)
multiply(arr, 0) * arr[0] * arr[1] // (n == 1; n - 1 == 0)
1 * arr[0] * arr[1]
1 * 2 * 5
``````

If the first call would be with n == 1, we would have only

``````multiply([2, 5], 1) // (arr = [2, 5]; n = 1)
multiply(arr, 0) * arr[0] // (n == 1; n - 1 == 0)
1 * arr[0]
1 * 2
``````
1 Like

thank you, i get it now!!

Hi colinthornton,
Your breakdown of how the code executed is really a big help!!

From the lesson:

## Basic JavaScript: Replace Loops using Recursion

Recursion is the concept that a function can be expressed in terms of itself. To help understand this, start by thinking about the following task: multiply the first `n` elements of an array to create the product of those elements. Using a `for` loop, you could do this:

```

• function multiply(arr, n) {*
• var product = 1;*
• for (var i = 0; i < n; i++) {*
• ``````   product *= arr[i];*
``````
• }*
• return product;*
• }*
```

However, notice that `multiply(arr, n) == multiply(arr, n - 1) * arr[n - 1]` . That means you can rewrite `multiply` in terms of itself and never need to use a loop.

``````
Could you please help to explain how multiply(arr, n) arrived to == multiply(arr, n - 1) * arr[n - 1]?``````

It’s the associative property.

I’m gonna write out some multiplication expressions.

``````1 * 2 * 5  // 10
50 * 2 * 3 // 300
2 * 2      // 4
``````

We can rewrite them as follows, however the results stay the same.

``````1 * (2 * 5)  // 10
(50 * 2) * 3 // 300
2 * 2        // 4
``````

That’s the associative property in action.

Now, let’s imagine we have a function `multiplyArr` that takes one argument, an array of numbers. Don’t worry about the contents of `multiplyArr`, just know that it returns the product of every number in the array.

``````multiplyArr([1, 2, 5])  // 10
multiplyArr([50, 2, 3]) // 300
multiplyArr([2, 2])     // 4
``````

Since we know that multiplication operations are associative, we know that these lines of code will have the same results:

``````multiplyArr([1, 2]) * 5  // 10
multiplyArr([50, 2]) * 3 // 300
multiplyArr([2]) * 2     // 4
``````

Does that help at all?

PS, they also take advantage of the identity property in the base case of the recursive `multiply` example.

Thank you for your prompt response. I think I’m getting there…
What does n - 1 do in multiply(arr, n - 1) and what does n - 1 do in arr[n - 1]?

Recursion is all about getting to the base case and working up from there.

If
`arr = [1, 3, 2, 2, 1]`
Then
`multiply(arr, 5)`
needs to know
`multiply(arr, 4)`
and so on until we reach the base case
`multiply(arr, 0)`
which is always `1`.

1 Like

If we have an array

``````['a', 'b', 'c', 'd']
``````

And we want to look at the first three elements (`n = 3`), then this is the relationship:

``````| n=3 | n-3 | n-2 | n-1 |  n  |
| idx |  0  |  1  |  2  |  3  |
| val |  a  |  b  |  c  |  d  |
``````

If we want to look at the first three elements, then we’ll start at the third element which is at the index `n - 1`, and work our way down to the index `0` by successively subtracting one from `n`.

Thank you so so much! I’ve been struggling since yesterday with recursion but finally I see the light at the end of the tunnel. Your detailed examples decoded for me.

2 Likes