Clash Royale CLAN TAG#URR8PPP

Recursive sum method

I don't understand how the outcome of the following code is 6, when called as sum(3). Can someone please explain?

6

sum(3)

public int sum(int number)
if (number == 1)
return number;
else
return number + sum(number - 1);




3 + 2 + 1 == 6

5 Answers
5

Think about it this way: if I told you the sum of the previous number, could you tell me the sum of the current number? If I told you that sum(4) = 10, what's sum(5)? Well, clearly sum(5) = 5 + sum(4) = 5 + 10 = 15.

sum

number

sum

number

sum(4) = 10

sum(5)

sum(5) = 5 + sum(4) = 5 + 10 = 15

Here's another challenge: based on that, can you calculate sum(7)? Well, clearly sum(7) = 7 + sum(6) = 7 + 6 + sum(5) = 7 + 6 + 15 = 28 - the fact that we already "know" the value of sum(5) means that we can directly substitute it in (at least for the purpose of our hand-calculation).

sum(7)

sum(7) = 7 + sum(6) = 7 + 6 + sum(5) = 7 + 6 + 15 = 28

sum(5)

There you have it: if I give you an arbitrary number somewhere in the sequence, you know how later values in the sequence are related to it. You can then use that to generate more values. It just so happens that whoever wrote this originally gave us the first value in the sequence: sum(1) = 1. This (at least theoretically) allows us to generate the sum for any natural number.* (See caveat below).

sum(1) = 1

Incidentally, the following for loop is basically equivalent:

for

public static int forSum(int number)

int ret = 0;

for (int i = number; i >= 1; i--)

ret += i;


return ret;



I'd encourage you to step through this with your favorite debugger to convince yourself that that's the case.

Incidentally, the following may be helpful: What is a debugger and how can it help me diagnose problems?

* Caveat: In reality, we can't actually use this to generate the sum of any natural number because we'll eventually run into one of a couple of problems:

*

int

We still, however, have a mathematical specification of what the solution is: sum(10^20) = 10^20 + sum(10^20 - 1) - we just don't have the time to compute it.

sum(10^20) = 10^20 + sum(10^20 - 1)

It's called recursion

If you will debug this code you will see something like:

step0: sum(3)
step1: 3 + sum(2)
step2: 3 + 2 + sum(1)
step3: 3 + 2 + 1


The method sums up all values up to the given argument. The argument is 3, the result is thus 6 = 3 + 2 + 1.

3

6 = 3 + 2 + 1

Therefore, the method uses recursion. That is, the method calls itself. It exploits the property that

sum(n) = n + sum(n - 1)


for any integer n.

Let's first take a look at an equivalent method that don't uses recursion:

public static int sum(int number)
int result = 0;
for (int i = number; i >= 1; i--)
result += i;

return result;



Called with 3 the method has three iterations. It adds 3 to result, then 2 and finally 1, resulting in 6.

3

3

result

2

1

6

Your recursive method does a similar thing. It takes 3 and adds the result of sum(2) = 2 + 1 to it. sum(2) is computed with the same technique, it takes 2 and adds sum(1) = 1 to it. sum(1) itself does not trigger another computation since it does not call sum again, take a look at your code:

3

sum(2) = 2 + 1

sum(2)

2

sum(1) = 1

sum(1)

sum

if (number == 1)
return number;


Again, let's take a look at the code:

return number + sum(number - 1);


So calling with 3 yields 3 + sum(3 - 1), which is 3 + sum(2). In order to compute this, the method sum must be called again, with the argument 2. Calling with 2 yields 2 + sum(1). In order to compute this, the method is called with 1. The call returns 1.

3

3 + sum(3 - 1)

3 + sum(2)

sum

2

2

2 + sum(1)

1

1

Substituting everything back yields:

sum(3) = 3 + sum(2)
= 3 + (2 + sum(1))
= 3 + (2 + (1))
= 6


This is a recursive method that outputs n+(n-1)+...+1. Thus, sum(3) outputs 3+2+1=6.

sum(3)

3+2+1=6

When you call the sum method with argument 3. The call becomes 3 + sum (2). second calls become 2+sum(1), this second calls returns 1. so the expression 2+ sum(1) returns 3 and first call 3+sum(2) will return 6.

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.