Recursion returning 0 or 1?

JavaScript
1

Tell us what’s happening:

So this is the first topic I’ve struggled with in hours of study on the site, and I feel it may be due to the brief explanation given regarding “return 0” or “return 1” in this activity.

In prior examples, exiting a function by typing “return “hello world!”” would return an answer of “hello world!”. But now we are returning 0, however the sum is somehow returning with it. This is confusing.

Why does return 0 return more than the number 0? It somehow includes the sum of the work done as well. Where is the final step that says “take the 0 and then add on all the previous work done”? To me, return 0 should just send back a 0.

What’s going on?

Thanks in advance.

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([2, 3, 4, 5], 3))

Your browser information:

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

Challenge: Replace Loops using Recursion

Link to the challenge:

2

Welcome to the wonderful world of recursion :slight_smile: If you’ve never encountered it before it can be a little hard to grasp at first. You are not alone.

I think the best way to learn this is to write it out on paper with a simple example. Try the following:

sum([1,2], 2);

The first time through the function n>0 so you will do the else statement:

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

Do you understand what just happened above? The function isn’t returning just a value. It is returning a call to itself with different parameters passed in and adding the return value of that function call to a value. In that return statement you have another call to the function:

sum([1,2], 1)

This also hits the else statement, so it returns:

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

But remember, this return is part of the original return statement above. So placing it back into the original return statement we now have:

return sum([1,2], 0) + 1 + 2

Once you can make sense of this then I think you can do the next step.

3

Functions resolve to a value. So if n is 0,

sum([2, 3, 4, 5], 0)

The first condition is true, and the function resolves to 0. What if n was 1?

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

In this case, the second condition is true. So, if you remember that if n is 0, the value returned is 0, then it returns:

sum(arr, 1-1) + [2,3,4,5][1-1]

Which is

sum([2,3,4,5], 0) + [2,3,4,5][0]

Which is

0 + 2

What if n was 2?

sum([2,3,4,5], 2-1) + [2,3,4,5][2-1]

Which is

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

Which is

sum([2,3,4,5], 1 - 1) + [2,3,4,5][1 - 1] + 3

Which is

0 + 2 + 3

So then what if n was 3? You end up with

sum([2,3,4,5], 0) + [2,3,4,5][1 - 1] + [2,3,4,5][2 - 1] + [2,3,4,5][3 - 1]

Which is

0 + 2 + 3 + 4

So if this was a loop:

function sum(arr, n) {
  output = 0

  for (let i = n; i > 0; n--) {
    output += arr[i - 1]
  }

  return output
}

If n is 0, then i is set to 0. 0 is not greater than 0, so loop ends, return 0.

If n is 3, then i is set to 3. 3 is greater than 0, add arr[3 - 1] (4).

i is set to 2. 2 is greater than 0. Add `arr[2 - 1] (4 + 3, so 7).

i is set to 1. 1 is greater than 0. Add `arr[1 - 1] (7 + 2, so 9).

i is set to 0. 0 is not greater than 0, loop ends, return 9

4

Recursive functions call themselves until some end condition occurs, then returns repeatedly (once for each time it was called). So while the innermost call might return 0 or 1, the next one out might return that result, plus its own.

I wrote a decent blog post, might help: https://portfoliostuff-parenttobias.codeanyapp.com/2020/01/29/recursion-all-the-way-down/

5

Oh I think I just got it. I was thinking of “return 0” as an complete exit but in a way, it sends that as a final part of the sum to all the previous work.

So console.log(sum([2, 3, 4, 5], 3)) is working through a little like this…

(4 +, 3 +, 2 +,) 0 which gives the 9. I guess you see it differently with more experience.

1 Like
6

Thank you all. I think I got it in my reply to bbsmooth.

1 Like