CODEWITHSUNDEEP
javarecursion
Charles
Charles

Reputation: 13

Trouble following recursive code

Just trying to understand how this code works. Say the integer is 4, I understand that 4 is checked against the base case and then the method calls itself again this time with the integer 3 and then same pattern occurs until the integer is 1. My question is how is the summation part being done? What would be the final result? 

public int sum(int num)
{
   int result;
   if (num == 1)
      result = 1;
   else
      result = num + sum(num-1);
   return result;
}

Upvotes: 0

Views: 50

Answers (3)

GhostCat
GhostCat

Reputation: 140457

It happens here:

result = num + sum(num-1);

together with

return result;

Iteration n calls sum() again (triggering iteration n+1). The result of n+1 is returned; and added to n; giving the result of n-1 (because of the later return statement).

And for the record: I did not include the final solution in my answer; as you can figure that easily by yourself; either by running that code; or by using a pen and a piece of paper to "run" this code "manually".

Upvotes: 1

nhouser9
nhouser9

Reputation: 6780

As I think you realize based on your post, the magic happens here: result = num + sum(num-1); Think of it as a chain of method calls. Logically, the whole process could be represented like this:

sum(4);

evaluates to

4 + sum(3);

which evaluates to

4 + 3 + sum(2);

which evaluates to

4 + 3 + 2 + sum(1);

which evaluates to

4 + 3 + 2 + 1

which is equal to

10

Upvotes: 2

xandermonkey
xandermonkey

Reputation: 4412

The summation happens as the recursive calls return back up the stack. See here:

             sum(4)   # The initial function call
               |
          |---------------|
          | 4 + sum(4-1)  |     # num + recursive call
                  |
              |---------------|
              | 3 + sum(3-1)  |  # the next num + the next recursive call
                      |
                  |---------------|
                  | 2 + sum(2-1)  |
                          |
                        |---|
                        | 1 |    # Base case num == 1

If you populate each recursive sum(...) call with the value below it, what do you get? The sums added up. That's where the addition occurs.

Trace this and find out what the value should be for yourself. Or, run the code.

Upvotes: 1

Related Questions