Recursion. Why multiply(arr, n) == multiply(arr, n - 1) * arr[n - 1]?

Hi Campers,
Thanks for your help in advance.

if i understood right, recursion is a function that can continuously feed itself until reaches the base case established. Is that so?

In the Challenge Replace Loops using Recursion, it is established that:
multiply(arr, n) == multiply(arr, n - 1) * arr[n - 1]
I can´t understand that.

function multiply(arr, n)

I think “arr” and “n” are arguments of the function “multiply”
Where does (n - 1) come from ?
Why is the second [n - 1] with brackets ?
Its even more confusing to me, because I suppose to return a sum, not a subtraction.

{return sum(arr, n - 1) + arr [n - 1];}

got me completely lost.

  **Your code so far**

function sum(arr, n) {
// Only change code below this line
if (n <= 0) {return 0;}
else {return sum(arr, n - 1) + arr [n - 1];}
// Only change code above this line
}
console.log(sum([1], 0));
console.log(sum([2, 3, 4], 1));
console.log(sum([2, 3, 4, 5], 3));
  **Your browser information:**

User Agent is: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_13_6) AppleWebKit/605.1.15 (KHTML, like Gecko) Version/13.1.2 Safari/605.1.15

Challenge: Replace Loops using Recursion

Link to the challenge:

Your understanding of recursion is correct.

Here you are multiplying the last element arr[n-1] ( remember that array indices start from 0, so the last element is arr[n-1] ) by the rest of the array, by passing the rest of the array back to the recursive function.

So each time the last element is taken and multiplied with the already existing product and the remaining array is passed to the function. This continues till no element remains.

Knowing about the call stack can help knowing whats going on behind the scenes and make it easier to understand what is really going on.

2 Likes

I would recommend you write this out on paper. If I gave you the following:

sum([1,2,3], 3);

Write out on paper how that function call would execute. For example, you would initially hit the else statement and return

sum([1,2,3], 2) + 3

Do you see how all of those numbers got in there?

So now you have another function call:

sum([1,2,3], 2)

Writing that out returns:

sum([1,2,3], 1) + 2

Again, do you see how you got that result? And don’t forget, you still have the + 3 from the earlier function call, so now you really have:

sum([1,2,3], 1) + 2 + 3

Do you see how each recursive call is adding an item from the array into the eventual total sum?

Hi @daniel_Landau,

Two ideas are expressed in that line of code:

1.- A recursive definition of sum
2.- How to “access” a limited number of element(s) of an array using an index number

We can express the same ideas in other ways:

2.- How to “access” elements of an array (without using an index number)

To avoid the use of a index number, we can use the first and rest approach.

The idea is mimic when people take things out of a box: they usually take them out one a a time (first), leaving the other things (rest) inside the box (array).

You can implement first and rest in JS using a destructuring assignment[0] :

let arr = ["A","B","C","D","E"];
const [first, ...rest] = arr;
console.log("first:",first);
console.log("rest:",rest);

// first: A
// rest: [ 'B', 'C', 'D', 'E' ]

Using that approach you can access every element of an array:

As you can see in the gif, if you apply first and rest on an empty array you get undefined and an empty array (infinite):

let arr = [];
const [first, ...rest] = arr;
console.log("first:",first);
console.log("rest:",rest);
// first: undefined
// rest: []

To avoid that, you can use a condition.

1.- A recursive definition of sum

We can define sum recursively (using first and rest ) as:

/**
 * Returns the sum of every number in the array 
 * If the array is empty, return 0;
 * @param   {array}  arr  - the array  of numbers
 * @returns {number}    - the sum of every number in the array or zero 
 */
function sum(arr) {
 if(arr.length === 0) return 0;  // A condition (to avoid infinite recursive calls) 
 const [first, ...rest] = arr; 
 return first + sum(rest);      
}

console.log(sum([0]));     // 0 
console.log(sum([1]));     // 1
console.log(sum([0,1]));   // 1
console.log(sum([1,2]));   // 3
console.log(sum([1,-1]));  // 0

As you can see, the above sum is applied to every element of the array.

To limit to n elements:

function sum(arr, n) {
  const [first, ...rest] = arr;
  if (n <= 0) return 0; // I changed the base case
  return first + sum(rest, n-1); // without n-1 the base case is never reached
}

console.log(sum([1], 0));           // 0
console.log(sum([2, 3, 4], 1));     // 2
console.log(sum([2, 3, 4, 5], 3));  // 9

Conclusion

a.- I think that a sum function that apply to every element of the array is easier to understand than a sum function that only apply to some elements of the array.

b.- The part “… that returns the sum of the first n elements of an array arr” seems superfluous and arbitrary.

c. I read :

function sum(arr) {
 if(arr.length === 0) return 0;
 const [first, ...rest] = arr; 
 return first + sum(rest);
}

As:
The sum of all elements of an array is: the first element of the array plus the (result of the) sum of the rest of elements of the array.

Cheers and happy coding :slight_smile:

Notes:
[0] Destructuring assignment - JavaScript | MDN

1 Like

Thanks skymat,

The Challenge asks to write a recursive function that returns the sum of the first n elements of an array arr .

I don´t understand why it is multiplying the last element?
I don´t see that is uses * to multiply.

I understand now [n-1] refers to the last element of (n). Thanks.
In those cases below, I guess it is always just one element as (n): 0, 1,3.
Isn´t it?

´´´
console.log(sum([1], 0));
console.log(sum([2, 3, 4], 1));
console.log(sum([2, 3, 4, 5], 3));
´´´

Last, where is it specified that the existing product is used to add to the remaining array?

Thanks.
I still feel very confused about that line:

´´´
else {return sum(arr, n - 1) + arr [n - 1];
´´´

So you’ve got two different functions. One that performs multiply, and one that performs sum… they do the same thing, so I’ll just address the sum one.

So you are given an array: arr = [2, 12, 6, 18, 9]
You are giving how many of those numbers you want to add together: n = 3

So you want to add 2, 12, and 6 together using recursion.

So using an array index:
arr[n] would be the number 18
arr[n-1] would be the number 6
arr[n-2] would be the number 12

and so on.

If that doesn’t make sense you may want to review Arrays and how to access values inside them.

So using recursion, you basically want to take one of those numbers, and then call the function again to add the remaining numbers together.

mySum = first number + sum(remaining numbers)

Your code here is doing exactly that:

else {return sum(arr, n - 1) + arr [n - 1];

arr[n-1] being your first number, sum(arr,n-1) being adding the remaining numbers… your program will keep calling itself until n gets to 0, then it is done.

Does that make sense?

When you make a function call it goes onto the stack. that function then gets run, and if it has a return will return that value to where it was called. so in its simplest form:

function someNumber(){
    return 5;
}

let variableThatWillHoldTheReturnOfOurFunctionCall = someNumber();
console.log(variableThatWillHoldTheReturnOfOurFunctionCall)//5

So let variableThatWillHoldTheReturnOfOurFunctionCall = someNumber() said "hey i want to store the value of someNumber". The computer says “Ok, hold on, let me get the value of someNumber first”. someNumber then gets tossed on the stack, then run, then popped off the stack and returns 5. NOW variableThatWillHoldTheReturnOfOurFunctionCall actually has a value after waiting a little bit of time.

So when we say return sum(arr, n - 1) + arr [n - 1], the sum(arr, n - 1) part is making a function call just like above. Its waiting in line in the call stack waiting to return a value. When it finally gets that value it will then do the return value + arr [n - 1]. And arr[n-1] is just referencing a number from an array, so also just a value. So to try and break it down all return sum(arr, n - 1) + arr [n - 1] is saying is return value + value. We just need to find the value of the sum(arr, n - 1) before we can actually do that math. That is why we need a base case. At some point sum needs to return just a value and stop making more calls. so the base case is return 0. So we are adding all the array numbers with 0 at the end.

This video helped me understand more about how you are building up the stack, then having it basically collapse back down with all those return values. It also explains a bit about what multiply(arr, n) == multiply(arr, n - 1) * arr[n - 1], basically another way of looking at the same problem.

Thanks for your help bbsmooth,

You are right, I don´t really see how all of those numbers got in there?

[1,2,3] I understand that are arguments of the array. Ok.

3 outside brackets should be other argument of the function, which is added to each element in the array. Is that right?

Where did that ,2) outside brackets come from?

I guess, each element in the array is to be added initially to the other argument in the function, and then to the product of that sum, recursively, until the base case is reached.

So writing down would be something like:
1 + 3 = 4
4 + 2 = 6
6 + 3 = 9
Being:
1 (first element inside array) + 3 (element Outside the array) = 4
4 (product) + 2 (second element inside array) = 6
6 (product) + 3 (third element inside array)= 9
1 + 3 (element outside the array) = 4 / 4 + 2 (Second element inside array) = 6 / 6 + 3 = 9
1 (first element inside array) + 3 (element Outside the array) = 4
4 (product) + 2 (second element inside array) = 6
6 (product) + 3 (third element inside array)= 9

Is that correct?

It is essential you understand how we got from the initial function call:

sum([1,2,3], 3);

To this:

sum([1,2,3], 2) + 3;

These two statements are equivalent. Look at the body of the function. What happens for the first function call above? The two parameters are arr which equals [1,2,3] and n which equals 3. Inside the function we first check to see if n <=0, which it is not, so we move on to the else statement. At that point we do a return. Plug the values into the return statement and you get:

sum([1,2,3], 2) + 3;

Does that make sense? We can’t go any further until you understand how your function executes.

Notice that the return statement includes another function call, a recursive call to sum to be exact. So before the return statement can actually return a value it has to execute that function call. So the return statement has to wait for the recursive call to finish and return a value so it can add that value to 3 and then return its value.

Let’s forget about recursive functions for a second. Say you have the following return statement:

return randomInt() + 3;

And let’s pretend that the randomInt function returns a number between 0 and 1000. Does it make sense that before this return statement can actually return a number it first has to get a random number from the randomInt function? So this return statement is calling another function and waiting for that function to return a number before it can add that number to 3 and return its own value. Does that make sense?

If that makes sense then you are very close to understanding recursion because that’s the same thing that happens with recursion. The return statement has to wait for a function to return a value. The main difference is that with a recursive function, the function being called in the return statement is itself. But that’s OK. When a function calls itself it’s just like calling any other function. Try not to let it throw you :slight_smile:

Hi kinome 79,

“n” being how many of the numbers of the array I will be adding together is a vital Information. I didn´t know.
Thanks for that.

When n = 3
arr[n] would be the number 18
arr[n-1] would be the number 6
arr[n-2] would be the number 12
Got that.

So in:

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

console.log(sum([1], 0));
´´´
n = 0 (n <= 0)
return 0
´´´

console.log(sum([2, 3, 4], 1));
´´´
n = 1
n - 1 = 2
return 2

``
console.log(sum([2, 3, 4, 5], 3));

n = 3
n -1 = 4
4 + the remaining numbers together
4 + 5 = return 9

It makes a lot of sense now.
sum(arr,n-1) being adding the remaining numbers is another vital Information that I didn´t know.

Thanks a lot kinome79 and all the team.
Now I can see some sun in the Horizon.
All the best.

I’m hoping it makes sense…but the way you wrote it its possible you might not be understanding exactly. Maybe better to use numbers not so close to gether. Lets take

sum([15, 21, 19, 37, 8], 3)

so you want it to sum together the first 3 elements of the array… so 15 + 21 + 19;

So to walk through this,arr[n-1] points to 19. So your function would be doing this:

return 19 + sum([15,21,19,37,8], 2), so 19 + the sum of the first two numbers, 15 and 21

so sum ([15,21,19.37,8] 2) , n-1 points to 21, so now its 21 + sum([15,21,19,39,8], 1). It will do it one more time until n=0…

So in the end, it will sum 15 + 21 + 19… right?

Thanks bbsmoth,

It makes sense now that the Second recursive call (sum) has to return a number and then the First function (return) will be executed and return a value.

Meaning:
n = 3
n - 1 = 3

and

n = 2
n - 1 =2

Sum: 2 + 3 (previous result) = 5

Thanks to your help, I think I am very close to understanding recursion. Thanks for that.

1 Like

Yes kinome79, to use numbers not so close together helped me to understand better.

arr[n-1] points to 19. Got it.

Will (arr, n - 1) reduce 1 from (n) each new step?
if so, now n = 2 ?

Now n-1 = 21

and then

return = 15

And next n = 0,
so
´´´
if (n <= 0) {return 0;}
´´´

One last question.

function sum(arr, n) {
if (n <= 0) {return 0;}
else {return sum(arr, n - 1) + arr [n - 1];}}
console.log(sum([1], 0));
console.log(sum([2, 3, 4], 1));
console.log(sum([2, 3, 4, 5], 3));
(sum([1], 0));
(n <= 0) {return 0;}

Ok

(sum([2, 3, 4], 1));
n = 1
n -1 = 2
0 + 2 = 2
return = 2.

Ok.

sum([2, 3, 4, 5], 3));
n = 3
n - 1 = 4
2 + 4 = 6

Why the correct answer should return 9 ??

This isn’t complete. There aren’t just two steps here. You will have several recursive calls until you reach the base case. Each time you make a recursive call you are reducing the value of n by one. You don’t reach the base case until n is 0. So you will have the initial function call, in which n is 3, and then one recursive call with n=2, and then another one with n=1 and then a last one with n=0. You left out some of those in your logic above.

Also, it is not the case that n - 1 === 2 here. n - 1 != arr[n - 1] and n - 1 != sum(arr, n - 1).

I see.

Should be:
sum([2, 3, 4, 5], 3));
n = 3
[n - 1 ] = 4

sum([2, 3, 4, 5], 2));
n = 2
[n - 1 ] = 3
4 +3 = 7

sum([2, 3, 4, 5], 1));
n = 1
[n - 1] = 2
7 + 2 = 9
return 9 . GOT IT !

sum([2, 3, 4, 5], 0));
n = 0
if (n <= 0) {return 0;}

Many many thanks for your patience bbsmooth
and all the team.

[n - 1] doesn’t mean anything. I know it feels pedantic, but computers are super pedantic.

1 Like

Yes, you are right Jeremy LT
I should have said arr[n-1] = 2

1 Like