Replace Loops using Recursion Help Please

JavaScript
1

I have so many questions here I don’t know where to start. I should say that I have done all the exercises up to this point but otherwise have had absolutely no experience with coding. Therefore it is entirely possible, in fact likely, that despite my best efforts I have not understood everything fully up to this point.

OK so let me try and explain where I am. I have managed to get the correct solution without understanding anything (which is often possible on this site). So I am not trying to find the solution but seeking a level of understanding.

Line 1 // function sum(arr, n) { // sets up a function and names it ‘sum’. It gives it two parameters. One is an array to be filled with number elements. The other is how many number elements in the array (starting from the left) we wish to add together.

Question 1 - is ‘arr’ a special keyword or could anything be written here - like “numberList” for example? I’m assuming any name could be used.

Line 2 / 3 // if (n <= 0) { return n; // This sets up the ‘base case’ which is the eventual exit out of the recursive state. This is the point at which there are ‘no / no more’ numbers in the array.

Question 2 - Why does it return ‘n’? ‘n’ is just the number of elements you state to be added together. Why does it not just return ‘0’?

So then we have the ‘recursive case’

Line 5 // return sum (arr, n - 1) + arr[n-1]; // I have no idea what this means. I have read an extremely long thread on this and got something out of it but not a full understanding. I know that an array indexing starts at ‘0’ instead of ‘1’. That must be why the ‘n’ becomes ‘n - 1’.

Question 3 - What does sum (arr, n - 1) tell the computer?

Question 4 - Is ‘sum’ a special keyword so the computer knows to add all the numbers in the array? I don’t remember coming across this.

Question 5 - Does ‘n’ refer to the index number as the recursive function keeps calling itself? So it would count down until it reaches zero.

Question 6 - What is the difference between (arr, n -1) and arr[n - 1]? The second one refers to a specific element in the array, but what does the first one mean?

Essentially I don’t understand what is actually happening in a recursive function. I get that it keeps calling itself until a return statement it met, but so does a loop have exit criteria.

Any help would be really appreciated because I’m beginning to struggle here.

Your code so far


function sum(arr, n) {
// Only change code below this line
if (n <= 0) {
return n;
} 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/79.0.3945.130 Safari/537.36.

Challenge: Replace Loops using Recursion

Link to the challenge:

2

correct, parameters, like variables, can be named anything (well, respecting valid characters restrictions, but let’s say everything). It is anyway recommended to use descriptive names.

is this your code? or have you found the answer somewhere?
Anyway, you are returning 0 anyway, because that part is executed for n <= 0 and there are no challenge tests for n being less than 0.
It would be better to just return 0.

to call the function (this is the definition of recursion, a function calling itself), but reducing the value of the second argument by 1 (so if the function had first an n of value 5, so meaning that it should sum the first five numbers in the array, this line call the function with an n = 4, so summing the first 4 elements of the array.

no, sum is the name of the function:

It is just a number, in this case it is the second parameter of the function, and it indicates the number of how many elements of the array should be summed together. (because that’s what the function description say it should do, that’s what the logic flow of the function make it be)

First, (arr, n-1) is a completely different thing than sum(arr, n-1), and it is the second one that is present in this case.
So, sum(arr, n-1) is a function call, and arr[n-1] is an element inside the array.
They can be summed, because the function returns a number, and the array element is a number.

1 Like
3

Thank you Ieahleen (or do I call you magical girl?),

Wow that was a quick and helpful response that has certainly helped. Not quite there yet though with the full understanding.

The last couple of lines have got me thinking… The 'sum(arr, n-1)` is a function call, so here it is calling itself which makes it recursive, is that right? How does that also return a number? Which number is it recalling?
This recursive function would seem to add the numbers in the array from right to left because it counts down from ‘n’, but doesn’t it needs to add from left to right.

Thank you again

4

if we call sum([1, 2, 3], 3), this function will have inside the line return sum([1, 2, 3], 2) + arr[2], for this line to finish executing, the function inside it will need to be called, and give an output.
So, inside sum([1, 2, 3], 2) there is return sum([1, 2, 3], 1) + arr[1], same as above, it needs to wait for result of the function
and inside sum([1, 2, 3], 1) there is a line return sum([1, 2, 3], 0) + arr[0]
inside sum([1, 2, 3], 0) there is just a line that says return 0
so now we can return to the last function, the one with return sum([1, 2, 3], 0) + arr[0], and we can put inside numbers. it becomes return 0 + 1
now that also that one is resolved, there is the return statement above that, return sum([1, 2, 3], 1) + arr[1], we have just found the value from the function, so this one is return 1 + 2

and so on (try to make a scheme on paper of the above, and complete it)

the order doesn’t matter, you can sum numbers in any order and it will give the same result. you can do 1+2+3 and it will give the same result as 3+2+1

5

Thank you again, I’m getting closer I think.

So the ‘sum (arr, n - 1)’ keeps recalling the function until it reaches the ‘base case’ of n<=0. The second part ’ + arr[n-1]’ just keeps a running total (in the stack) until it returns out of the recursive case, at this point it returns the total - in your example it adds 3 + 2+ 1 then returns 6.

I understand the left to right business as well now, because regardless of the value of ‘n’ an array is indexed from left to right. So, as you say, with addition or multiplication it doesn’t make any difference.

Is it just me or are there quite a few new concepts in this question/exercise? This is really tough for a newbie to get my head around. Maybe I’m just a bit dim.

You’re very kind to spend your time helping me - I do appreciate it very much.

6

the new concept is recursion, functions and how to sum stuff are from the beginning of the curriculum

no, arr[n-1] is not a running total, is just a number from the array,
If you want to consider something “a running total”, that’s the function call.

Really, try to write on paper how the values change line by line.
It is the best way to understand what’s going on.

7

If you’re having trouble visualizing it:

Say you have [1,2,3], and n = 3

Your solution’s execution callstack might look like this:

sum([1,2,3], 3) // Kicks off recursion
      + [1,2,3][2] // n = 3
    + [1,2,3][1] // n = 2
  + [1,2,3][0] // n = 1
0 // Stop | n <= 0 is true

Reads the same as

((((0) + 1) + 2) + 3)

What I get out from this is that you should not return n if n <= 0 because n only acts as an index and it may be negative, so if you return any other number than 0 your sum is invalidated. You should return 0 here instead of n.

Another thing, people don’t go arround passing the length of an array of numbers to a function which sole purpose in life is to sum an array of numbers. You should create a function that extracts the length of the array and passes it to the function that has the n paramater.

Warning: Don’t read any further if you’re not comfortable with some of these terms: tail call recursion, parameter, default parameter, optimization, ES6, haskell, functional programming.

The recursive solution you posted although technically correct, it’s flawed in the sense that having the “n” parameter means you’re accomplishing the same thing as a regular loop solution and you’re not taking advantage of tail-call optimization which is by the way not yet implemented in JavaScript anyway.

You could take advantage of JS’s default parameters introduced in ES6 to simulate an accumulation loop using tail-call recursion:

function sum(xs, total = 0) {
  if (xs.length === 0) {
    return total;
  }

  return sum(xs.slice(1), total + xs[0]);
}

Which would visualize as:

sum([1, 2, 3], 0)
sum([2, 3], 1)
sum([3], 3)
sum([], 6)
6 // Because [] has length 0
// thus recursion stops

or using a helper function to simulate a for loop:

function _sum(xs, i) {
  if (i < 0) {
    return 0;
  }

  return xs[i] + sum(xs, i - 1);
}

function sum(xs) {
  return _sum(xs, xs.length - 1);
}

Which visualizes as:

_sum([1, 2, 3])
sum([1, 2, 3], 3) // Kicks off recursion:
[1,2,3][2] + // i = 2, sends 1 to next call
             [1,2,3][1] + // i = 1, ** 0 **
                          [1,2,3][0] + // i = 0, ** - 1 **
                                       0 // i = -1 | stop
// Which can be represented as
3 + (2 + (1 + (0))) ) = 6
//             ^
//             |
//             +---> Where recursion stopped

In functional languages where the primary looping mechanism is recursion, this function becomes more explicit and mathematical:

sum [] = 0
sum (first:rest) = first + (sum rest)

Here, you can see clearly that the base case is the empty list, its sum is 0.
And the sum of an array is, recursively, the first element + the sum of the rest.

3 Likes