How does this recursion work?

JavaScript
1

I understand recursive functions generally and have written them myself to solve problems, but this one confused me. On each call, the function returns 1 + sumAll([first + 1, last]) but what is the value of sumAll([first + 1, last])? Since all it does is check for a condition and if the condition is not reached, it repeats the above operation.

function sumAll(arr) {
  const [first, last] = [...arr].sort((a, b) => a - b);
  return first !== last
    ? first + sumAll([first + 1, last])
    : first;
}

sumAll([1, 4]);
2

careful, it returns first + sumAll(...)

it’s the sum all of numbers between first+1 and last

3

Thanks, yes I meant 1 in this example in particular. Can you point me to the line of code that gets the sum of numbers between first + 1 and last? I just don’t see it.

4

the function here

remember it’s a recursive function!
what happens if you have
sumAll([4, 4])?
it returns 4 because of

what happens to sumAll([3, 4])?

it returns 7 because of

3 and 4 are not equal, so this expression is executed

which if we put the numbers in is 3 + sumAll([4, 4])
we know what the function call returns as we did it above, so it becomes 3 + 4 which is 7

and so on

5

I still don’t understand. On the second call, the function returns 1 + sumAll([2, 4]), but isn’t the result of sumAll([2, 4]) just 2 + sumAll([3, 4]), then 3 + 4 on next call which gives 7, and that is not the correct answer, because it should give 10. I wrote a recursive function that makes more sense to me and it passes the test, but I would still like to understand the one above.

function sumAll(arr, stop = 0, [first, last] = [...arr].sort((a, b) => a - b), [copyFirst, copyLast] = [...arr].sort((a, b) => a - b), acc = copyFirst) {
  if (stop === copyLast - copyFirst) {
      return first
  } else {
      acc++
      first = first + acc
      stop += 1
      console.log(first)
      return sumAll(arr, stop, [first, last], [copyFirst, copyLast], acc)
  }
   
}

console.log(sumAll([1, 4]));
6

You are missing the rest of the recursion

7 is the result of sumAll([3, 4]), so this is 2 + 7

And then this

7

Could you please write it all out, like what it does on each call and what the result is? I’m just having a hard time visualizing this.

9

https://pythontutor.com/visualize.html#mode=edit

1 Like
10

I tried that. I don’t understand why the value of sumAll([3, 4]) is 7. As far as I understand the function never returns a number unless first === last so wouldn’t the result of sumAll([3, 4]) be 3 + 4? 3 being first and 4 being the result of sumAll([4, 4])

11

Sure, the result of sumAll([3, 4]) is 7, but that isn’t the result of sumAll([2, 4])

12

Wait I just confused myself. I just said I didn’t understand why sumAll([3, 4]) is 7 and then went ahead and said it would equal 7. I need to step back for a minute here lol

13

1st call: 1 + sumAll([2, 4]) which gives
2nd call: 2 + sumAll([3, 4]) which gives
3rd call: 3 + sumAll([4, 4])
Am I wrong here?

14

You’re missing the other half. Where does the 3 + sumAll([4, 4]) go?

15

it uses a ternary expression, do you know how it works?

16

What do you mean? Could you illustrate?

17

Yes, I know how it works

18

Did you try using this?

The solution is your original post is terse. Are you familiar with ternaries? This is the code written less tersely.

function sumAll(arr) {
  const [first, last] = [...arr].sort((a, b) => a - b);
  if (first !== last) {
    // recursive case
    return first + sumAll([first + 1, last]);
  } else {
    // base case
    return first;
  }
}

sumAll([1, 4]);

Here:

 first + sumAll([first + 1, last]);

you are calling the function. That function call has to complete before the current function call can return a result.

Here you are accumulating all of the data down into a single function call:

return sumAll(arr, stop, [first, last], [copyFirst, copyLast], acc)

but that sort of dodges the bits about function calls, scope, and return values that can make recursion tricky. It’s those bits that seem to be confusing you the most about the solution in the first post.

I seriously recommend pasting the code in and running this step by step with this link on pythontutor.com or with this link that skips the sorting

19

I really appreciate your help but the issue is not the ternary statement, I understand those completely and use them myself, it’s the recursive case in that function that I don’t get. I tried running it on python tutor but I still don’t get it. Thanks for your time though.

20

The function call sumAll([1, 4]) returns 1 + sumAll([2, 4]), right? But what is sumAll([2, 4])?

The function call sumAll([2, 4]) returns 2 + sumAll([3, 4]), right? But what is sumAll([3, 4])?

The function call sumAll([3, 4]) returns 3 + sumAll([4, 4]), right? But what is sumAll([4, 4])?

The function call sumAll([4, 4]) returns 4.

Therefore, the function call sumAll([3, 4]) returns 3 + 4 === 7, right?

Therefore, the function call sumAll([2, 4]) returns 2 + 7 === 9, right?

Therefore, the function call sumAll([1, 4]) returns 1 + 9 === 10, right?

This is the exact set of steps presented by pythontutor, converted to words. You cn also create something similar by using console.log() inside of the function.

1 Like
21

Just to try and give you one more analogy for how it works (hopefully without causing more confusion). You remember order of operations from algebra class all those years ago? The way I was taught was PEMDAS (parentheses, exponents, multiplication, division, addition, subtraction). Parentheses take the most precedence, so you need to solve the chunks within parentheses first.

In terms of a math equation, the call to sumAll([1, 4]) looks like this:

1 + (2 + (3 + (4)))

Following order of operations we need to start from the innermost parentheses (the recursive calls in this analogy):

// 4 is just 4
1 + (2 + (3 + 4))

// 3 + 4 is 7
1 + (2 + 7)

// 2 + 7 is 9
1 + 9

10

In terms of English this could be phrased as

The sum of integers from 1 to 4 is equal to
1 plus the sum of integers from 2 to 4, is equal to
1 plus 2 plus the sum of integers from 3 to 4, is equal to
1 plus 2 plus 3 plus the sum of integers from 4 to 4, is equal to
1 plus 2 plus 3 plus 4… so 10

2 Likes