I just can’t understand the lesson "Replace loops using recursion" of freeCodeCamp. I'll quote that part below;

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.

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

Especially this part. multiply(arr, n) == multiply(arr, n - 1) * arr[n - 1]

I can understand if it's like this;

multiply(arr, n) == multiply(arr, n - 1) * arr[n]

That's because if arr = [2,3,4,5,6,7,8,9],

multiply(arr, 5); equals 2*3*4*5*6*7

multiply(arr, 4); equals 2*3*4*5*6

multiply(arr, 4) * arr[5]; equals (2*3*4*5*6)*7

So multiply(arr, n) and multiply(arr, n - 1) * arr[n] is the same value"

However, I can't understand why multiply(arr, n) == multiply(arr, n - 1) * arr[n - 1] ? Can anyone please tell what’s happening in this code? Why they are equal?

I just can’t understand the lesson "Replace loops using recursion" of freeCodeCamp. I'll quote that part below;

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.

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

Especially this part. multiply(arr, n) == multiply(arr, n - 1) * arr[n - 1]

I can understand if it's like this;

multiply(arr, n) == multiply(arr, n - 1) * arr[n]

That's because if arr = [2,3,4,5,6,7,8,9],

multiply(arr, 5); equals 2*3*4*5*6*7

multiply(arr, 4); equals 2*3*4*5*6

multiply(arr, 4) * arr[5]; equals (2*3*4*5*6)*7

So multiply(arr, n) and multiply(arr, n - 1) * arr[n] is the same value"

However, I can't understand why multiply(arr, n) == multiply(arr, n - 1) * arr[n - 1] ? Can anyone please tell what’s happening in this code? Why they are equal?

• javascript
• loops
• recursion

• Index starts from 0 , at index n , there will be undefined. – Harmandeep Singh Kalsi Commented Jul 5, 2020 at 19:05
• 1 The idea here is to pass the length of the array as the initial n, not the index of the last element. Also notice that the base case is n == 0, not n < 0. – Bergi Commented Jul 5, 2020 at 19:39
• Thank you both for the ment! But I still can't understand about this.. Is there anyone who can explain this with examples please? – Suzuran Commented Jul 6, 2020 at 14:00

8 Answers 8

Alright I will try to explain it the way I figured it out. I was having trouble with this one too.

This part is the confustion in here: multiply(arr, n) == multiply(arr, n - 1) * arr[n - 1]

So lets say we have an array which is: var arr = [1, 2, 3, 4, 5] Here, the n, which refers to the number of the elements in the array is 5, because we have 5 elements inside the array.

Now in the first function given:

function multiply(arr, n) {

var product = 1;

for (var i = 0; i < n; i++) {

    product *= arr[i];

}

return product;

}

Here we can find the left-hand side of our confusion as the function itself, which is multiply(arr, n).

Here the product is continuously being multiplied with the elements of the arrow until the variable i bees 5 and then it stops because it is no longer less than n but equal to n which happens to be 5, the number of the elements itself.

So it goes to be from 0 to 4 and these are index numbers of the elements which happen to be multiplied with the product, which is 1.

When the index is 0, then arr[0] is 1

When the index is 1, then arr[1] is 2

When the index is 2, then arr[2] is 3

When the index is 3, then arr[3] is 4

When the index is 4, then arr[4] is 5

They all are multiplied and the result is = 1 * 2 * 3 * 4 * 5 = 120.

So our left-hand side of the confusion has the value of 120

Then we e to the right-hand side of our confusion.

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

This part has two things being multiplied

First one is multiply(arr, n - 1) which is just the same thing except for you just got to take one element less than the last time. Think of the same function where only number of elements which is n, is 1 element less this time. So n is 4 now.

So now it es to this:

When the index is 0, then arr[0] is 1

When the index is 1, then arr[1] is 2

When the index is 2, then arr[2] is 3

When the index is 3, then arr[3] is 4

So for the first multiply(arr, n - 1) part they all are multiplied and the result is = 1 * 2 * 3 * 4 = 24.

Then es the next part which is arr[n - 1]

Here, we are only getting the n-1th index of our array, we know n is 5 and therefore n-1 will 4. As we know indexing starts from zero, so the 4th index will be the 5th item in the arrow, which is 5.

This means arr[n - 1] is 5.

NOW, lets multiply the two parts:

We have:

multiply(arr, n - 1) = 24 And, arr[n - 1] = 5

5 * 24 = 120, the same result we had from the left-hand side of our confusion.

Hope this helped.

However, I can't understand why multiply(arr, n) == multiply(arr, n - 1) * arr[n - 1] ? Can anyone please tell what’s happening in this code? Why they are equal?

The given algorithm is multiplying the first n elements of an array arr and returning the answer.

Now, to multiply the first n elements, we can multiply the first (n-1) elements and then multiply the result with the nth element of the array.

So, multiply(arr, n) == multiply(arr, n - 1) * arr[n - 1].

multiply(arr, n) means multiply the first n elements of the array arr.
multiply(arr, n - 1) means multiply the first n-1 elements of the array arr.

I've just gotten to this lesson myself and found myself rather lost for a little while. Our problem es from not realising the the nth term of arr is not equal to arr[n] but arr[n-1].

multiply(arr, 5); equals 2*3*4*5*6*7

in this case you're summing the first 5 terms 2*3*4*5*6

multiply(arr, 4); equals 2*3*4*5*6

in this case you're summing the first 4 terms 2*3*4*5

multiply(arr, 4) * arr[5]; equals (2*3*4*5*6)*7

because of the difference between term number and index (1st term is at [0], 2nd term is at [1], etc.), multiply(arr, 4) * arr[5]; in fact equals (2*3*4*5)*7 due to arr[5] being the 6th term of the array rather than the 5th.

So i doudt multiply(arr, n) and multiply(arr, n - 1) * arr[n] will give the same value. multiply(arr, n) gives you a result from the first nth term. See proof below:

Note: The code below is a Pseudocode

//given the array below
var arr = [1,2,3,4]
// if n = 3
return multiply(arr, n); //output will be [1,2,3] = 1*2*3 = 6

//but
multiply(arr, n - 1) * arr[n]; //output will be [1,2]*4 => 1*2*4 = 8
//therefore 
multiply(arr, n) != multiply(arr, n - 1) * arr[n];

But

//given the array below
var arr = [1,2,3,4]
// if n = 3
return multiply(arr, n); //output will be [1,2,3] = 1*2*3 = 6

//but
multiply(arr, n - 1) * arr[n - 1]; //output will be [1,2]*3 => 1*2*3 = 6
//therefore 
multiply(arr, n) == multiply(arr, n - 1) * arr[n - 1];

I hope this was quite helpful

multiply(arr,n) == multiply(arr, n-1) * arr[n-1] //equation

arr = [1,2,3,4,5,6,7,8] //sample array used

For this question you need to be fond of factorials, if you cannot recall please look into it on youtube.

within arr, n is the number of values in the array that is being multiplied.

example:

when n = 4
multiply(arr,4) //calls the first 5 elements of array to be multiplied  by each other.

leftside
multiply(arr,4) = 1x2x3x4 = 4! = 24 //

rightside
multiply(arr,4-1) x arr[3] //arr[3] is the 4th element of the arr
multiply(arr,3) x 4
(arr,3) = 1x2x3 = 3!
(arr,3) = 1x2x3x4 = 4! //this is multiply(arr,3)*4

therefore you can see that the equation is true, to which ever value of n within arr you provide.

let myArr = [2, 4, 5, 6];
function multiply(arr, n) {
  if (n <= 0) {
    return 1;
  } else {
     return multiply(arr, n - 1) * arr[n-1];
  }
}

That code Works like this:

For every call of the function if I pass myArr and 4 as arguments

multiply(arr, 4 - 1) == 6
arr[3-1] == 5
multiply(arr, 2 - 1) == 4
arr[1-1] == 2
multiply(arr, 0 - 1) == -1 n < 0 ; return 1
where : 6*5*4*2*1 == 240

Here is my explanation.

For e.g arr = [1,2,3,4], n = 4 (total number of elements in array)

This is the formula

multiply(arr,n) = multiply(arr, n - 1) * arr[n - 1];
multiply([1,2,3,4], 4) = multiply([1,2,3,4], 3) * arr[3];   
multiply([1,2,3,4], 4) = multiply([1,2,3,4], 3(first 3 elements of array) * 4(last element in array);
multiplt([1,2,3,4], 4) = (1*2*3) * 4; ==> 12

So, basically we are multiplying all elements except the last one. Then product of all is multiplied with last one.

yeah, from what I've seen (or noticed) this concept doesn't work UNLESS last "n" value is same as index value. 2x4x7x6=1680 (n then being 2x4x7x"6"=1680..."6" being another random number...just not 3 vs n=(2x4x7x"3") with index @3 (under n-1 conditions), THIS will work out. 2x4x7=280...x"3"=840 where with n=2473. This is just what I've noticed, so yes, this concept works...to an extent, unless...this concept is INTENDED only for the last n-number being the same as index value. End result: n being(2473=1680), and n-1 being (247=280)x3=1680... SAME RESULT.

Help if I'm wrong, thanks)