Recursion and addition problem explained?

My question is about the math that is happening in the recursive case. I don’t understand what mathematical problem is happening in sum(arr, n - 1) + arr[n - 1];

If there’s an array of [2, 3, 4, 5], how is this all being added to n to then result in just 1 number? Why isn’t it an array of numbers?

  **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/92.0.4515.131 Safari/537.36

Challenge: Replace Loops using Recursion

Link to the challenge:

So recursion can be a very confusing topic. A function that calls itself, repeatedly? Doesn’t seem right somehow. But let’s see what we can do here.

First, defining recursion (not an official one, simply a definition in my own words): repeatedly performing some task until something tells us to stop. In a more formal definition, a recursive function is a function that repeatedly calls itself on some dataset, until some exit condition is met.

In this case, we have a dataset: [2,3,4,5]. We want to act on some part of that dataset, until some exit condition happens. What is that exit condition? The if statement: if(n<=0). When that happens, we stop repeating the function call, and start returning stuff.

Let’s say we call your sum function like this: sum([2,3,4,5], 3). We are setting its internal arguments like so: arr=[2,3,4,5] and n=3. So we create an executed function “scope” (think of it as a box containing the variables and evaluations for this particular function call).

Within that “box”, our n is greater than 0, so we fall into the else side of the statement. So we’ll be returning something, but what? We’ll be making another function scope (another box) within the current one, like so sum([2,3,4,5], 2), which will return some value eventually, and adding that to arr[2], which is 4 in that outermost function scope.

Now, we’ve got two nested “boxes”. The outermost box can be identified by n===3, and the next one in is exactly the same except that n===2. Well, 2 is still greater than zero - so we again fall into that else branch, and create another function scope (another darn box!). We’re going to call the function sum([2,3,4,5], 1), add that to arr[1] (which is 3), and return that.

So at this point, we’ve “nested” three boxes:

- sum() with arr===[2,3,4,5] and n===3, which contains
  - sum() with arr===[2,3,4,5] and n===2, which contains
    - sum() with arr===[2,3,4,5] and n===1, which **still** isn't n<=0!

So our innermost “box” (again, function scope) needs to call sum([2,3,4,5], 0) and add that to arr[0], which is 2. Our function has now called itself four times, and created four nested function boxes. But hey! n is now less than or equal to zero!

This is key: we have reached our exit condition. When n<=0, we stop calling the function (we stop creating nested boxes), and we simply return 0. Where are we returning that 0 to? To the next box out.

That next box (the one with n===1) takes in that 0, and adds the thing found at arr[0] to it. arr[0]===2, so we are adding 0+2, and returning the result. Returning it where? To the next outward function call.

There, n===2, and we take that returned 2 from our nested box, and add it to arr[1], which is 3 - so this box is returning 2+3… to the thing that called it. Our outermost box.

That outermost box (which still sees n===3) catches the 5 and adds arr[2] to it. arr[2]===4, so we’re going to return 4+5. And where does that get returned? Back to whatever called the function originally. Each time, the function is returning some value to the place that called it. In this case, we’re at the outermost box, so we’re returning that 9 to our console.log() or our test or whatever called the function originally.

Let’s try a visual:

sum([2,3,4,5], 3)
  = sum([2,3,4,5], 2) + 4
    = { sum([2,3,4,5], 1) + 3 } + 4
      = { { sum([2,3,4,5], 0) + 2} + 3 } + 4
           // here, we've reached the innermost level.
           // we're going to return 0 and start unwrapping our nesting!
            = { { { 0 } + 2 } + 3 } + 4
       = { { 0 + 2 } + 3 } + 4
    = { 2+3 } + 4
= 9

Our final return value = 9

That nested math thing might look scary, but what’s happening is that each pair of { } shows a “scope”. It’s the nested function call again! Each one of those will evaluate, from the innermost first. Each call is indented to indicate the “nesting”, until we reach that innermost level, and then we return its evaluation (0), and then we work our way back out (by following the return statements. From the comment above down, we’re simply passing back the result to the innermost {...} each time, evaluating that, and passing it along.

Recursion is confusing, and until you really start using it a lot, it will continue to be confusing. the more you use it, the less confusing it should get… but it never seems normal to me. Feels like trying to look inside my own head with my own eyeballs.

3 Likes

Remember that in recurssion, there are two cases to be aware of. The base case and recursive case.
if (num <=0) means the execution of the code stops once n = 0. So we are basically counting down from whatever n was to 0. Let’s say n = 9. We count from 9 all the way to 0, where the recursive function stops calling itself.

Now the recursive case is the function calling itself repeatedly until the base case tells it to stop, which is sum(arr, n-1) + arr[n-1], so it takes the shape of sum(arr, 9 - 1 = 8) + arr[9 - 1 = 8]. arr[9 - 1 = 8] is the accumulator, so we add to it. So we are basically taking the last element in the array, then add to it the next element to the left of it.

I have written on this a little more extensively here

Your recursion in that blog post is based on an accumulator parameter with a default value instead of being based on return values, so I don’t think it is actually very applicable here.

1 Like

Thank you for your response

My issue is the array and recall…

In your visual, why does the n in sum([2,3,4,5], n) go down and not up? If the arr[n-1] begins with arr[3-1] that would be 2 which is referring to the number 4 in the array. So then, isn’t n = 4? So shouldn’t your visual rather be:
= sum([2,3,4,5], 2) + 4 = { sum([2,3,4,5], 3) + 5 } + 4 = { { sum([2,3,4,5], 4) + BUT THIS WOULD BE NULL Then?} + 3 } + 4

Why are the numbers decreasing?

Is that true, because this problem is driving me insane and doesn’t match the videos that I’m watching

Don’t lose track, n represents an index in the array, not the value at that index position.

So you ask why we are counting down here , and that’s a valid question. Given an array of some length, we are being asked to perform some action on the first N items in that array.

We could simply count up, starting from 0 until our index reaches N - but that would require we pass more information on each recursion. We would still need to pass the array itself, and the index position for the current iteration… But we’d also need to pass that N value to determine if we meet the exit condition.

But we always know the first item’s index.

So the only value we change in our parameters each time is the index itself. The array remains the same, we simply keep calling our recursive function until we reach the point where we know we’ve reached the index for the beginning of the array, and then we start passing array values back.

Each successive recursive call is a closure in itself, containing a reference to the same array but a different value for n. So as our recursively-nested function unwinds, it uses the unique index to return the value of another item in the array.

1 Like

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.