# Having trouble tracing this recursion method. Can't find the problem.

• 04-11-2011, 04:18 AM
Having trouble tracing this recursion method. Can't find the problem.
I'm working on an assignment and I'm just stumped. I'm getting a stack overflow so I think I'm sending it off to infinity somewhere but I can't for the life of me figure out where. Can anyone see the problem with it?

The assignment was,

Quote:

Modify the method that calculates the sum of the integers between 1 and N. Have the new version match the following recursive definition: The sum of 1 to N is the sum of 1 to (N/2) plus the sum of (N/2+1) to N.

The original method looks like this:

Code:

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

And what I've got is this:

Code:

```import java.util.Scanner; public class SumDiv2 {                 public static int sum(int num, int stop){                                 int result;                                 if(num == stop)                         result = stop;                 else                         result = (num + sum(num-1, (num+stop)/2+1)) + ((num+stop)/2 + sum((num+stop)/2-1, stop));                                 return result;                 }                 public static void main(String args[]){                                 Scanner s = new Scanner(System.in);                                 int n = 0;                                 System.out.println("Enter an ingeger greater than 0: ");                 n = s.nextInt();                                 System.out.println("The sum of the " + n + " integers is " + sum(n));                         }                 public static int sum(int num){                                 return sum(num, 0);                         }         }```
• 04-11-2011, 04:55 AM
ra4king
Your logic is wrong in the sum(int,int) method. Try looking over it again. I suggest starting with a simple number like 3 and actually draw it out on a piece of paper what the method calls and values are.
• 04-11-2011, 04:55 AM
Junky
Why have you introduced "stop" and a second method?
• 04-12-2011, 06:44 AM
I could have simply made a direct call from the main to the sum(int, int) but I was trying to remain as close to the original as possible so I included the interim step. Not sure if you were asking why the additional int is needed but if so, it's to tell the method which section to work on summing. Otherwise, both sides would sum all numbers up to 0, leading to a larger end result than the correct answer.

I ended up with

Code:

```public static int sum(int start, int stop){                                 int result;                                 if(start == stop)                         result = start;                 else if(start < stop)                         result = 0;                 else{                                                 result = start + sum(start-1, ((start+stop)/2)+1);                         result += (start+stop)/2 + sum(((start+stop)/2)-1, stop);                                         }                 return result;                 }```
for my answer. It gives the correct answer but it seems very inefficient. Can anyone suggest a more efficient implementation (still using recursion)?

This is beyond the assignment but I'm just curious.