Help with recursion and zero based indexing(mass confusion)

JavaScript
1

Tell us what’s happening:
I’m not sure how this answer is mapped out…Could someone break it down for me?

Im confused about zero based indexing with -1, and the last line is really difficult for me to comprehend.

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
}

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/81.0.4044.138 Safari/537.36.

Challenge: Replace Loops using Recursion

Link to the challenge:

2

ES6 way:
(recursion-explanation) => https://javascript.info/recursion ;

3

Your recursion seems to bed OK and I hope I understand your question and the task!
But I suppose "n"is the length of the array and it is always >= 0, so that the “if statement” should be "if (n == 0) {return 0;}

Let us see an example:
arr = [1, 2, 3, 4]

  1. n = lenOfArr = 1 => sum(arr, 1 - 1) + arr[1 - 1] = sum(arr, 0) + arr[0] = 0 + 1 = 1
  2. n = lenOffArr = 2 => sum(arr, 2 - 1) + arr[2 - 1] = sum(arr, 1) + arr[1] = 1 + 2 = 3
  3. n = lenOffArr = 3 => sum(arr, 3 - 1) + arr[3 - 1] = sum(arr, 2) + arr[2] = 3 + 3 = 6
  4. n = lenOffArr = 4 => sum(arr, 4 - 1) + arr[4 - 1] = sum(arr, 3) + arr[3] = 6 + 4 = 10

I hope it helps you!

4

Using n <== 0 really is a best practice so that you can make a function that is valid for all n. If a wrong value is passed in, you don’t want to start an infinite recursion.

1 Like
5

as @JeremyLT said, don’t miss negative values ending in infinite recursion…

6

Thanks very much! I have done that only because of the confusion with “the indexing with -1” mentioned in the question.

1 Like
7

Thanks for the response!
Can you take the last line of code and explain it from the example?
I did not write this code i looked at the answer-what it requested of me was to
" Write a recursive function, sum(arr, n) , that returns the sum of the first n elements of an array arr "
My brain is not working this out…
I have the parameters (arr, n)
does the paramter “arr” make an array just by listing it that way? I think the last line basically tells it to add itself?

8

Also,
why is there brackets being used in the second part of the last line ?

9

The second part of the last line is an elment of the array.
If you have an array and you want to get an element you have to use brackets.
For example array = {3, 4, 5, 1}
the first element is array[0] = 3
the second element is array[1] = 4
the third element is array[2] = 5
the fourth element is array[3] = 1

In arrays the indexes begin with 0 and so on!

1 Like
10 
return sum(arr, n-1) + (arr [n-1]);

I suppose the function returns the sum of the first N elements in given array.

EXAMPLE:

let’s make simple example var arr = [1, 2, 3], n = 3; and call the function

1st function call

function sum(arr, 3)

if (3 <= 0) { 
return 0; 
}
=> false

let’s move into the else section

return sum(arr, 3 - 1) here it pauses!!!

why? because we’re calling function sum(arr, 3-1) => sum(arr, 2)

2nd function call

function sum(arr, 2)

if (2 <= 0) { 
return 0; 
}
=> false

return sum(arr, 2-1) here it pauses!!!

why? because we’re calling function sum(arr, 2-1) => sum(arr, 1)

3rd function call

function sum(arr, 1)

if (1 <= 0) { 
return 0; 
}
=> false

return sum(arr, 1-1) here it pauses!!!

why? because we’re calling function sum(arr, 1-1) => sum(arr, 0)

4th function call

function sum(arr, 0)

if (0 <= 0) { 
return 0; 
}
=> true

AND NOW, we are going back to the 3rd function call and return 0 from this 4th function call

back to 3rd function call

return sum(arr, 0) + (arr [1-1]); => 0 + arr[0] => return 1
cause arr[0] = 1

now it takes 1 from it and place it as result of function call from 2nd function call

back to 2ng function call

return sum(arr, 1) + (arr [2-1]); =>  1 + arr[1] => return 3

back to 1se function call

return sum(arr, 2) + (arr [3-1]); =>  3 + arr[2] => return 6

RESULT = 6

1 Like
11

okay, SO-
Its taking the sum until it cannot go any further because it starts at 0?
and then the first part referring to the actual numbers values within the array?
You guys are the bomb for dealing with me but im desperate to understand this…

12

let me know if you still don’t understand, I think I made it pretty clear there :slight_smile:

1 Like
13

I love the logistics of this but im extremely far from turning myself into a pickle…Let me look over what you gave me here.

14

One more question-
what is n to the array when you define the parameters like that?
It just seems like some abstract number…

15

I know recursion in that case is a little difficult!

We take an other example:

Suppose we have an array a = {4, 2, 7, 1} and we want to apply your code auf that array.

  • n = the length of the array = 4
  • the indexes are 0, 1, 2, 3

we want to calculate the sum of the elements of a using sum(a, n)
according to sum(a, n-1) + (a [n-1])

We calculate sum(a, n) = sum(a, 4)

  1. sum(a, 3) + a[3] = sum(a, 3) + 1
  2. sum(a, 2) + a[2] = sum(a, 2) + 7
  3. sum(a, 1) + a[1] = sum(a, 1) + 2
  4. sum(a, 0) + a[0] = sum(a, 0) + 4

sum(a, 0) = 0 (see if-statement)!

  1. => 0 + 4 = 4
  2. => 4 + 2 = 6
  3. => 6 + 7 = 13
  4. => 13 + 1 = 14 (That is the solution for taht case!)

The easiest way to understand recursion is to practice factorial and/or Fibonacci!

I checked your code im my IDE and it works!

I hope it helps you a litte bit!

16

well, it’s your basically your input…
it’s the number of how many first elements of the array you want to sum up
the array has 3 elements so I set n = 3 thus it sums up all of them but you can set n = 2, n = 1…
but if you want to calculate the sum of all of them, you can say n = array.length

17

Here is example with factorials…

function factorial(number) {
 if (number === 0) {  //factorial 0! = 1
 return 1;
 }
 else {
 return factorial(number-1) * number;
 }
}
18

You can use for a loop as well, actually, every recursion can be replaced with for loop.

// factorial can be applied only for an interval of integers in <0, +infinite)
// therefore the smallest posible outcome is equal 1
function factorial(number) {
    if (number < 0) {
        return undefined;
    }
    let result = 1; 
    for (let i = 1; i <= number; i++) {
       result = result * i;
    }
    return result;
  }
19

and here is ES6 one-liner :rofl:=>

function factorial(number) {
    return number < 0 ? undefined : number === 0 ? 1 : factorial(number-1) * number;
  }

I just enjoy figuring out one-liners :smiley: and this is what you can achieve only by recursions…

20

Let me look everything over thanks again…