Replace Loops Using Recursion - Comprehension

JavaScript
#1

Hello,

I have read other posts and watched various videos but am still stumped on comprehending the example code in this exercise.

  • I understand the concept of recursion being a “reflection,” calling itself as a sort of “shortcut” from using loops in order to execute statements until you reach the desired result.

  • I understand that a “base case” acts as your insurance against infinite loops, and the “recursive case” is your continuous, loop-like code.

  • I understand that there are no real advantages or disadvantages to either (aside from memory usage), that loops are preferred (or so I read), and that this concept of recursion will be important for algorithms later on. I want to get this down.

My issue is with understanding the logic of the example code.


//I understand this completely: 

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



//I cannot wrap my head around:

//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];
    }
  }

Specifically:

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

How did they make that equivalency? And are they using both the original multiply function in addition to this newer recursive function? How does this latest function execute any actual statements without the older function example?

Thank you for any assistance.

Challenge: Replace Loops using Recursion

Link to the challenge:

2 Likes
#2

There’s one more function of the base case. Without reaching it no actual calculations are made. Taking as example multiply(arr, n - 1) * arr[n - 1], while arr[n-1] is known multiply(arr, n - 1) not necessarily is known at that point. If that call is not reaching base case yet then recursive part would be called again, until base case is reached. Only then it’s possible to one-by-one calculate results for the previous calls.

1 Like
#3

it is showing how recursion work

something more simple
a factorial of a number, is the result of the multiplication of all numbers from 1 up to thay number
factorial of 3 is written as 3!

so 3! is 1x2x3

this is one classical thing to make with recursion

n! === n x (n - 1)!

so for example, 5! is equal to 4! multiplied by 5 (because 5! = 5x4x3x2x1 and 4! = 4x3x2x1)

in this case you have for example
multiply([6,4,9,11], 3) which will result in the multiplication of the first three numbers in the array, so 6x4x9
if we take multiply([6,4,9,11], 2), this is equal to the multiplication of the first 2 numbers, so 6x4, and if we also multiply by the third number in the array, 9, it becomes exactly as above
multiply([6,4,9,11], 3) === multiply([6,4,9,11], 2) x 9

putting the numbers you get
(6x4x9) === (6x4) x 9

1 Like
#4

I’m totally stuck on this too. I’ve been trying to wrap my head around the logic. I found this on the forum-

http://pythontutor.com/visualize.html#mode=edit

It shows you in sort of real time how the code is being executed. Unfortunately I still don’t understand the logic in this exercise but it might help you! And then maybe if you get it you can help me to understand it.

1 Like
#5

@CAL90 @zimizelle
you can also try reading this:

1 Like