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?
Advertisement
Answer
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 n
th 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
.