Replace Loops Using Recursion Clarification

Tell us what’s happening:

  1. I understand how basic function recursion works, the function is simply re-called within the function

  2. I understand that the function is calling itself and only when n <= 0 is false, then executes: return js multiply(arr, n - 1) * arr[n];

  3. I understand that n is being used for the index

  4. I cannot understand how return multiply(arr, n - 1) * arr[n]; works to actually multiply from index 0 through index 3 of the array.

  5. The hints do not thoroughly explain what is happening in the second return statement.

  6. The “VIDEO” help actually does not include a video, even though he refers to a video multiple times. AND… sorry to say, his elaborate explanation is not well written and confuses more than clarifies. I am surprised you guys accepted that verbose, filled-too-much-with-unessential-humor explanation.

  7. Please help :slight_smile:

Your code so far


var array = [1, 2, 3, 4];

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

console.log(multiply(array, 3)); // 24

Challenge: Replace Loops using Recursion

Link to the challenge:
https://www.freecodecamp.org/learn/javascript-algorithms-and-data-structures/basic-javascript/replace-loops-using-recursion

I highly recommend doing this: Run the code in the Chrome Developer tools in the debugging mode is a great way to see it all happen, and visually explains the execution so well. At least for myself.

You will then be able to see the recursion in operation, the call stack, and the local memory allocation in progression. Putting this all together will, I think help you out. You read pretty smart. It took me a few to understand it.

Take the code and put it in a folder with an html page. Link the script (.js) file in the html page to bring it in.

Visual Studio Code (or some other IDE) ,

Open the index.html page in VS Code and right click and select (if you need the extension, it is available in the VS Code extensions) “open with live server”. Then, in the browser window that it opens, (a Chrome browser) - just hit the F12 key on keyboard. Then go to the “sources” tab ans open the .js file. Then use the debugger to see it’s operation.

n = 3:
multiply(arr, 3-1) * arr[3]
n = 2:
multiply(arr, 2-1) * arr[2]
n = 1:
multiply(arr, 1-1) * arr[1]
n = 0:
arr[0] = 1

And now, as you got to the end of recursion and have the function result for n = 0, you can kind of go back.

(n=1)
multiply(arr, 0) * arr[1] = 1 * 2
(n=2)
multiply(arr, 1) * arr[2] = 1 * 2 * 3
(n=3)
multiply(arr, 2) * arr[3] = 1 * 2 * 3 * 4
1 Like

I think that this thread is the best so far at explaining what is happening here. A few different people have chimed in with how they explain recursion.

Regarding your second code block, is that really how it works, or is it actually as follows:

(n=1)
multiply(arr, 0) * arr[1] = 1 * 2
(n=2)
multiply(arr, 1) * arr[2] = 2 * 3
(n=3)
multiply(arr, 2) * arr[3] = 6 * 4

And when the following executes the first time, does * arr[3] actually not do anything?

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

I believe the crux of the problem for me is, what exactly does the following line do the FIRST time it runs.

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

What does this do on first run: multiply(arr, n - 1)
What does this do on first run: * arr[n];

Thanks for the heads up about Chrome dev tools. I am able to step through it and see the progression of n each time, and then it proceeds to return the multiplied numbers.

Does this mean that the function is looping two different times, one set of loops for N and then a second set of loops to multiply each of index item positions 0, 1, 2, 3 ?

I think I get your issue:
the line return miltiply(arr, n-1) * arr[n] is executed only after the function call returns a value
once multiply(arr, n-1) has a value, then the multiplication happens and only after that the obtained value is returned

all the functions stay pending, waiting for a value for their return statement

This reply is for anyone without any programming background at all. For beginners like myself learning through picking the code apart.

To your answer: for every return to the if-statement conditional, there is a “newly created function execution context” and another “multiply’” function which is placed on top of the call-stack.

I am currently editing this: for everyone > newbies, novices, and like me…trying to get it right!

The secret-sauce to fully understanding recursion, or, for that matter, any JS code, is to understand the “execution function context” which the JS Engine will perform on any, and all functions.

When I read code, I read it like the JS engine. Every time there is a “function invocation” , the engine will open a new execution context for that specific function. It works the functions code in it’s own little isolated box. However, within that “isolated box” if there is another function ( the secret sauce here), the engine will keep the current function on the “call stack” and pop out of the current function and into a brand new execution context. The new working function (and new execution context) gets it’s own memory store for it’s values; but these values can be accessed (depending on context) through the prototypical inheritance ( the chain).

The code:

var array = [1, 2, 3, 4]; //declare and instantiated array

function multiply(arr, n) { //the function definition, declaration, statement, expression

if (n <= 0) { // if statement (Boolean conditional)

return arr[0]; // if True, return this statement

} else { // the else clause gets fired if conditional is False

return multiply(arr, n - 1) * arr[n]; // nested recursive function (closure)

} // ends the if code block

} // ends the outer function code block

console.log(multiply(array, 3)); // 24 this line invokes the whole thing!

The function call:

Pretending I am the JS engine: ( third person? ) :slight_smile: :rofl:

Since JavaScript is synchronous, “I read code line-by-line” from top-to-bottom in a single thread and to keep it simple. I then read the entire code and put things where they need to be in my memory, and then, as things have it; I get called with a “function call” at the bottom of the code which makes me execute the code. Sometimes, I even get called by other functions, or even by variables that I am assigned to. I am First Class!

First things first.

  1. I read and store the [Array] name ’ arr ' with its two ‘parameters’, and allocate memory.

  2. Next, I also read the function’s definition body into memory.

  3. I continue reading down the code until I come upon: console.log( multiply ( array, 3 ))

    An Aside: The JS built-in log() function is invoked (remember > parentheses) and says, " I need to look inside the parentheses to see what I am to invoke/run/execute". It looks inside and reads the ‘function’ name multiply with associated parentheses ( ).
    1. The parentheses tell me to ‘execute’ this named-function, ‘multiply’.
    2. I find the function’s name in memory, multiply, with its two parameters, arr and n. The function name also references it’s function definition located in memory.
    c. I pass in the two arguments from the function call; the ‘array’ , which has been instantiated with an array containing a sequence of integers (primitive number object’s in JS), from 1 to 4 .
    d. I also pass in the argument, number ‘3’ into the ‘n’ parameter in the function definition (statement).

arr is [1,2,3,4], and n is 3.
4. I am now in the function body: everything between the { } curly brackets at:
if ( n <= 0 )

n = 3

if (3 <= 0 )

This evaluates to a falsy and so the engine will run what’s in the “else-clause”.

If it were truthy, the JS engine would then execute the “first statement” in the if-conditional, the return arr[ 0 ]

This array has (4) elements each with a number value. These values are consumed by their ‘index’ values.

console.log( arr [ 0 ] ) // 1

So, using the array: arr = [ 1, 2 ,3 ,4 ]

index 0 = 1
index 1 = 2
index 2 = 3
index 3 = 4

Take Note : Inside the if-conditional is a 'nested' function with the same name as the outer function's name. They have the same name, but when executed they will have their own 'execution context environment' which holds their own returned values upon code completion of that function.

Working with the nested function: Inner function of the if-conditional

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

  1. So, once again, when this multiply function is invoked, the JS engine creates a new execution context.
Take Note: For every time the multiply function gets called, as it is looped through the if-conditional ( 4 times : because 4 array elements) , the JS engine creates a separate execution context for each function call.

arr is : arr = [1,2,3,4] // just as a reference

n is 3

First function call of multiply: gets placed on the call-stack:

(arr, 3 - 1) * arr[ 3 ] // arr is array, n=3, so 3-1 is '2' * arr[3] is index 3: value of '4

n = 2
arr [ 3 ] is value 4, from index 3 of arr.

Second function call of multiply: it gets placed on the call-stack on top of previous multiply:

(arr, 2 - 1) * arr[ 2 ] // n=2, so 2-1 is 1 * arr[2] is index 2: value of 3

n = 1
arr [ 2 ] is value 3 , from index 2 of arr.

Third function call of multiply: it gets placed on the call-stack on top of previous multiply:

(arr, 1 - 1) * arr[ 3 ] // n=1, so 1-1 is 0 * arr[ 1 ] is index 1: value of '2'.

n = 0 // In if > if ( n <= 0 ) still truthy, so execute the else clause.

arr[ 1] is value 2, from index of arr.

Fourth function call of multiply: it gets placed on the call-stack on top of previous multiply:

(arr , 0 - 1) * arr[ 0 ] // n=0, so 0 - 1 is '0' * arr[0] is index 0: value of '1'.

Finally, the if statement evaluates to a truthy condition: n=0, 0 is = 0!

Remember: the JS engine is still in the INNER or NESTED multiply function
This is otherwise known as a “closure” in JS.

return arr[0];

On the call-stack we have:

top of call stack

multiply 4th func: n=0, val=1
multiply 3rd func: n=1, val= 2
multiply 2nd func: n= 2, val= 3
multiply 1st func: n=3, val= 4

bottom of call stack

so the engine returns the ‘value’ of n[0] each successive time the function’s are asked to return their return values; functions are 'pooped from the stack in this order: LIFO (last-in, first-out);

4th ‘multiply’ function is popped off the stack, returns a value of ‘1’.
3rd ‘multiply’ function is popped off the stack, returns a value of ‘2’.
2nd ‘multiply’ function is popped off the stack, returns a value of ‘3’.
1st ‘multiply’ function is popped off the stack, returns a value of ‘4’.

Each time the JS engine recursively is multiplying the returned function-call values together.

4th: val=1, 3rd: val=2, 2nd: val=3, 1st: val=4. 1 x 2 x 3 x 4

Do it recursively multiples 1 x 2 x 3 x 4.

24

The hours it took me grasp this.
I am a self-taught programmer and 63 years old. Yes, old F…T. :sunglasses:

I hope this can help others.
I am currently studying Python, TensorFlow, OpenCV, and ML.

Please inform me of any errors right away so that I can correct them.

4 Likes

My secret sauce for understanding recursion is a little simpler: substitution. Let’s take a factorial function:

function factorial(n) {
  if (n === 1)
    return  1;
  else
    return n * factorial(n - 1);
}

I hope this is familiar enough. I’m going to go ahead and turn it into an arrow function.

const fac = n => n === 1 ? 1 : n * fac(n - 1)

Now let’s do fac(5), and to do that, we need to “expand” the body of fac:

n === 1 ? 1 : n * fac(n - 1)

Substituting n with the parameter gives us:

5 === 1 ? 1 : 5 * fac(5 - 1)

We can simplify this down to:

5 * fac(4)

Now expand fac(4) the same way we did before, adding some parentheses to make it clearer:

5 * (4 === 1 ? 1 : 4 * fac(4 - 1))

Again, we can simplify it:

5 * (4 * fac(3))

Now expand and simplify fac(3). I’m just heading straight to the reduced form instead of showing the intermediate full expansion step now

5 * (4 * (3 * (fac(2)))
5 * (4 * (3 * (2 * (fac(1)))

And so on until we eventually get to:

5 * (4 * (3 * 2 * (1 === 1 ? 1 : 1 * fac(1 - 1))))

Now we see that 1 == 1, and we don’t use fac anywhere in the expansion. That’s our base case. So we get:

5 * (4 * (3 * (2 * (1))))

Or 120.

TL;DR version: when you see a function call, just substitute the whole body of the function, replacing the parameter names with their values. Keep doing this until there are no more function calls left. This works for any chain of function calls BTW, not just recursive ones, but only as long as they don’t assign to any variables (which includes changing the contents of a list).

Forget about “stacks”. Just substitute and simplify as you go.

2 Likes

Ah, yes… that is the sticking point:
Within the line return multiply(arr, n-1) how does multiply(arr, n-1) ever get a value that can then be multiplied by arr[n]. I get that return multiply(arr, n-1) is calling function multiply(arr, n) but at no point can I see how (arr, n-1) or (arr, n) would turn into a number that can be multiplied by arr[n]

hi chuckadams, please see my reply to ieahleen of Replace Loops Using Recursion Clarification

because it is a function call, and every function call have an output. In this case it is a number, because that’s how it is defined.

arr is [2,4,9]
we call multiply(arr, 2)
the return statement of this function is return multiply(arr, 1) * arr[2]
→ so now multiply(arr, 1) is called, the outer function is put on hold as it doesn’t have yet a value to return
→ the return statement of this last function is return multiply(arr, 0) * arr[1]
→ this function is put on hold, and the function called in the return statement start executing
→ -> so now there is multiply(arr, 0), in this case n <= 0 is true, so the return stament is just return arr[0]
→ -> multiply(arr, 0) returns 2
→ so now we can pick up again the previous function, and we can substitute the output of the function in the return statement. So when before it was return multiply(arr, 0) * arr[1] now it can become return 2 * arr[1] and so return 8
so now we can return to the first called function, multiply(arr, 2), the return statement of this one is return multiply(arr, 1) * arr[2] - the function in this return statement has now an output, so the return statement becomes return 8 * 9
multiply(arr, 2) returns 72

Hi guys,

from your explanations here I think I understand how this works now,

But I’m confused because on my version of the assignment the correct formula for the solution is different.

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

I don’t understand why my solution involves sum(arr, n - 1) + arr[n - 1]

when all of your solutions don’t have the second subtraction
i.e. sum(arr, n -1) + arr[n] - which makes total sense to me.

any help would be great

I think there was a recent change in the challenge.
Everything told above is correct, it’s just that this version of the algorithm will sum the first n elements (so up to index n-1) instead of the elements up to index n like it was discussed above.
so to get sum(arr, n) you sum the elements from index 0 to index n-1.

1 Like

Hey man, just wanted to say thank you. Your explanation helped me understand the last bits I was missing. Thanks :slight_smile: