Problem understanding this recursion example

JavaScript
1

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!

Your code so far


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



// 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/80.0.3987.149 Safari/537.36.

Challenge: Replace Loops using Recursion

Link to the challenge:

1 Like
2

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).

3 
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
4

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…

5

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
6

thank you, i get it now!!

7

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]?
8

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.

9

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]?

10

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
11

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.

12

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