Breaking down the recursion example

Hi!

Here is the example of recursion I struggle to understand.

So, here we have

However, notice that multiply(arr, n) == multiply(arr, n - 1) * arr[n - 1] .

Mine issue is that I can’t understand this expression and how can I notice the thing.

A bit of my brainstorming:
So, we have 2 parts of the equation:

  1. multiply(arr, n) - the function that multiplies elements of the array
  2. multiply(arr, n - 1) * arr[n - 1] - since that moment I stop understanding things. As I can understand this expression, we multiply the result of the function and a certain element of the array. But why do we use n-1 instead of n as a second argument?
  3. what multiply(arr, n - 1) does stand for? As far as I understand, it’s the value of previous operations, isn’t it? And the only reason we have minus one in the second argument n-1 is just that it calculates everything that happened before. Am I right?
  4. arr[n-1] - here we access an element of an array. But why do we have to write here n-1 instead of just n?
  5. Finally, I can’t understand equality. Why the result of the function with one argument can be equal to the result of multiplying the same function but with the previous value of an argument by the value of the previous element of an array.

I hope you can help me with that. Thank you.

Assume arr = [1, 2 , 3, 4],
Suppose we have to find product of first 3 elements, so n=3

Let’s jump to the function,

  • initially we have, multiply(arr, 3)
    In this function we’ll written multiply(arr, 2)*arr[3-1]

    • arr[3-1] means arr[2] which is 3rd(nth) element of the array, and multiply(arr, 2) refers to product of first 2 elements of array…
      This is same as, product of first 3 elements of an array is equal to product of first two elements and 3rd element of the array
  • To generalize, product of first n elements of an array is equal to product of first n-1 elements and nth element(which is arr[n-1] with 0-indexed-arrays )

If, you’re still facing problem refer this or explanation of other recursive functions below




1 Like

Thank you! It seems I got the point. We don’t multiply anything unless we reach the base case but we just collect numbers. Once we reach the base case, the math happens. What a relief!