I have no idea what recursion is/ok, wtf just happened?

I am working on Replace Loops with Recursion. I first had this

function sum(arr, n) {
  // Only change code below this line
if (n <= 0) {
  return 1;
} else {
  return sum(arr, n-1) + arr[n-1];
}
  // Only change code above this line
}

Then I changed the first return after if (n<=0) to “return 0”, and it works. Why exactly? I do not understand why this worked. I mean, it’s nice to stumble onto the answer, but I should probably understand why it worked. I was seriously going to post here asking for help bc I couldn’t get it to work, but I still am not sure why it does now. Does anyone else do this? Try something that works, and you have no idea why?

Btw, I basically just copied the code from the example, and modified it to be addition rather than multiplication, but I still don’t think I understand what’s happening. I couldn’t understand what was happening with the example provided.

1 Like

Yep, I used to not get how recursions work
I asked this question to which I got a few good answers. Though I cant say I have a complete understanding of it now, I did get a better idea of what it is/how it works.

You had the right intuition, consider now what happens in function, what result would be giving function if for n <= 0 it would return 1.

function sum(arr, n) {
  // Only change code below this line
  if (n <= 0) {
    return 1;
  } else {
    return sum(arr, n-1) + arr[n-1]; 
  }
  // Only change code above this line
}

For example, we want sum of the first 0 elements:
sum([2, 3, 4], 0)
as n <= 0, this would return 1. That wouldn’t be right.

Let’s consider sum of the first 1 element:
sum([2, 3, 4], 1)

n <= 0 for 1 is false, so we follow the code in else:
return sum([2, 3, 4], n-1) + [2, 3, 4][n-1]

As n - 1 = 1 - 1 = 0, that’s actually:
return sum([2, 3, 4], 0) + [2, 3, 4][0]

[2, 3, 4][0] -> 2, and sum([2, 3, 4], 0) we had considered before, knowing it returns 1.

Finally then it’s 2 + 1 = 3, as a sum of the first 1 element. Yep, definitely that doesn’t look right. For all those reasons if for n <= 0 would be returned 0 the result would be correct.

It’s not always possible to know if something will work. This is normal, if you haven’t solved such problem yet, how can you be sure how to do that? However with each not successful try, there can be more information what will not work.

It’s good that you want to learn why. Analyzing why something is wrong, or right may give more insights for the future.

2 Likes

this video helped me understand what is going on mush better:
(jumping to the more relevant section)

and knowing what a call stack is.

But because we are doing addition, if you returned 1, you would eventually be adding 1 to whatever was the last number in the passed array at arr[n-1] when we hit the base case, then eventually its going to add up the rest of those arr[n-1] numbers as well. And because the test is just asking to add up the first n numbers in the array you would always have the correct answer+1 basically.

But since you are returning 0 as the base case, it is adding 0 + arr[n-1] when it hits the base case, which would just = whatever arr[n-1] was, then adds the rest of the previous arr[n-1]'s in the stack together.

and if we where doing multiplication and returned 0, it would end up being 0 no matter what numbers where in arr[n-1] because 0*anynumber=0. So in that case it would mathematically make sense for the return to be 1, like in the example.

1 Like

This doesn’t make sense to me. Could you maybe explain why the code that passed does work? Maybe I’m not smart enough to understand this.

1 Like

I think I’m in the same mindset as the OP on this problem, I do not understand how sum([2, 3, 4], 0) is returning a 1 and how [2, 3, 4][0] is returning 2.

Edit: Okay I completely overlooked sum([2, 3, 4], 0), because n=0 (sum(arr, n)) it returns 1, but I’m still confused on how you get 2 from [2,3,4][0].

Edit 2: Is [2,3,4][0] = 2 because the 0 element in the array is 2, and would [2,3,4][1] = 3?

Edit 3: It clicked for me. Some of the ways the code was written out in explanations in the post made it incredibly confusing because I wasn’t 100% sure what I was looking at.

Anyone looking for a very clear explanation of how this works look here

Different ways of explaining works different for different people. It’s the matter of finding the right way.

Let’s look, at the correct answer then:

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
}

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

At first we consider n == 3, it’s not <= 0, so we need to consider code from else:
sum([2, 3, 4, 5], 3)sum([2, 3, 4, 5], 3 - 1) + arr[3 - 1]sum([2, 3, 4, 5], 2) + arr[2]
We know what is arr[2], but sum([2, 3, 4, 5], 2) no, for that we need to go recursively deeper to find that value.

sum([2, 3, 4, 5], 2)sum([2, 3, 4, 5], 2 - 1) + arr[2 - 1]sum([2, 3, 4, 5], 1) + arr[1]
Similarly in here, we know what arr[1] is, but sum([2, 3, 4, 5], 1), another step deeper then.

sum([2, 3, 4, 5], 1)sum([2, 3, 4, 5], 1 - 1) + arr[1 - 1]sum([2, 3, 4, 5], 0) + arr[0]
Once again arr[0] is known, sum([2, 3, 4, 5], 0) not yet.

sum([2, 3, 4, 5], 0)0
At this point we finally reach the base case n <= 0, for which returned is 0. We use it to back and step-by-step get returned value from each recursive call.

sum([2, 3, 4, 5], 1)sum([2, 3, 4, 5], 0) + arr[0]0 + 22
sum([2, 3, 4, 5], 2)sum([2, 3, 4, 5], 1) + arr[1]2 + 35
sum([2, 3, 4, 5], 3)sum([2, 3, 4, 5], 2) + arr[2]5 + 49

1 Like

Yes, [2, 3, 4][0] == 2. This can be looked as arr1[0] if arr1 = [2, 3, 4].

I’m going to try to explain what’s happening. The brackets are telling us we are selecting the number in that slot in the array. So, for arr[n-1], if n is 3, we are grabbing the number in slot 2, which is actually the third number in the sequence, because the array starts counting slots with 0. So, this is actually why we need the [n-1] at all, simply because arrays start at 0? For example, I have an array [5, 9, 12]. I want to add all the numbers, but because the array starts counting slots at 0, to select the number 12, I need to tell it to pull the number in slot 2 of the array. Is that right? The sum(arr, n-1) is telling the code we need to go back to the array again, and the arr[n-1] is actually selecting the number I requested, translating it for the array so it knows it’s selecting the number in the second slot. So, if the code is saying if n==3, then we take the sum(arr, n-1), which we don’t know yet, and adding it to slot arr[n-1], which would be slot 2, or the third number in the array? At the end, when n finally becomes 1, arr[n-1] selects the first number in the array, and the if statement (n<=0) stops the loop. Am I getting this? I really hope so, if not, I’m so lost

Example case:

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

(our call 1) sum([5,7,12,4,6,9], 3)
         arr         n

So we get an array (arr) of numbers and a number(n), the number in this case representing that we only want the first three numbers in the array, and we want those numbers added together.

We could write this with a loop another way, but obviously that’s not the point, we are learning recursion. So rather then make a loop we make a function that will return another function, until it hits a base case, the base case being very important, otherwise it would just keep going like a loop without an end and fill the call stack.

So our base case is if (n<=0). Less then n because if we tossed it a negative number the function would keep going because we are eventually going to be subtracting from the value of n later in our function and would not stop. And equal because if we go to far back n will hit negative numbers, and since we are using the value of n to grab from the array we are going to have an “undefined” in there, which will break our math.

Since we are doing addition we want our base case to return 0, because eventually this is the number that is going to be returned at the end of this long line of functions being made and added to the stack, and it is going to be added to all our other array numbers. And remember in this case we only want the first three numbers added together (5,7,12), not all three numbers +1.

Then after that we have an else. This is the part where we return our function with our array ([5,7,12,4,6,9]) and n-1 (3-1) + a number from the array at arr[n-1] (12). This will eventually give us our base case, but also gives us our numbers in the array to add together.

so return sum([5,7,12,4,6,9], 2) + 12 (our call 2)

is n <= 0? nope lets do our else.

return sum([5,7,12,4,6,9], 1) + 7 (our call 3)

is n <= 0? nope lets do our else.

return sum([5,7,12,4,6,9], 0) + 5 (our call 4)

is n <= 0? yes! lets finally do the if and return 0

Now is the part that can get even more confusing. Remember all those functions we made before? They where waiting for an answer, our base case.

so call 4 is getting a return, our 0. So think of sum([5,7,12,4,6,9], 0) now as equaling 0.

So sum([5,7,12,4,6,9], 0) + 5 is now just 0 + 5. What is 0+5? 5. Remember our call 3? it was waiting on call 4 to finish. So you can think of call 4 now returning 5. what was our call 3? sum([5,7,12,4,6,9], 1) + 7. So now think of sum([5,7,12,4,6,9], 1) as just being 5. and remember our +7 in there? what is 5+7?

I could repeat myself for the last one, but you probably get the idea. It keeps going backwards from that point, turning the past functions into numbers and adding them to our array numbers.

And even though we only called sum once, it made a bunch of other ones for us, which then toss back there answers all the way to the original (call 1) with the answer of 24.

I can’t tell, was something in my explanation wrong? I have no idea if you’re trying to correct me, or just explaining it. This is just adding to my confusion. Also, reading the words “call 4” “call 3” was confusing, perhaps iteration is a better word. Is that what you mean when you say “call 3”? It’s the third iteration of the recursion?

You’re getting it. Your explanation above was sound.


To add another way to think about it, I’m gonna write it like an algebraic equation. At each step we’ll simplify the equation.

Let arr be [1, 2, 3]

sum(arr, 3) is equal to sum(arr, 2) + 3 (according to the return value)

sum(arr, 2) + 3 is equal to sum(arr, 1) + 2 + 3

sum(arr, 1) + 2 + 3 is equal to sum(arr, 0) + 1 + 2 + 3

sum(arr, 0) + 1 + 2 + 3 is equal to 0 + 1 + 2 + 3

0 + 1 + 2 + 3 is equal to 6

Therefore sum(arr, 3) is equal to 6.

1 Like

Sorry i was just explaining it and intended to say it looks like you got it, but i was in a little rush and forgot to put that in there, my bad :sweat_smile:. But yeah like colinthorton posted in a better way.

The “call” was just referring to when you type sum([1,2,3],1) you are “calling” the sum function, at least as far as my understanding of the terminology. But i could be wrong, im still learning. But i also just googled it and see a stackoverflow post talking about the difference of a “call” and “invoking” so it might be better to say invoking? idk

either way sorry for confusing you more! :sweat:

seriously man, i’m confused as it is, please don’t make it worse. I have enough trouble figuring this out. I appreciate that you’re trying to help, but sometimes people will write something and I’m like “I have no idea what you just said. I must be stupid because that makes no sense.” I’m currently planning on doing a coding bootcamp, Tech Elevator, in May. I’m trying to get through the prework, and a lot of it is on this website. I have no idea if I can actually do this, I have such a hard time, I don’t know if I’m smart enough.

I’ll explain it in a simple way.
You will understand if you read patiently.

You need to find a key you kept in a box long time ago.
You open a box to find out that there is another box inside it. When you open that one, you find yet another one it in.
This repeats x number of times. You dont know which one has the key.

Lets write a program for this.

function openBox(box){
    if(box.hasKey()){
        return box;
   } else{
       openBox(box.open());
    }
}

As you can see, this function keeps on opening the box till the key is found.

function openBox(box){
    if(box.hasKey()){
        return box;
   }

What the above code does is → if the box has the key , it will return the value of the box containing the key and the code stops executing.

else{
       openBox(box.open());
    }
}

Else, the function keeps opening the next box until the value in the if() block is satisfied, that is, till the key is found
As you can see, the function calls itself, but it changes its value passed into it each time. In this case , the functions tells itself to open the next box.

This is exactly what recursions do ! They keep on executing until the value passed into the if() block is satisfied. Otherwise, in the else block it will call the function but with a modified value so that it can check if the modified value can pass the code in the if statement.

I spent a lot of time writing this.
Hope this helped.

This article is great: How to Understand Recursion in JavaScript