Results 1 to 4 of 4
  1. #1
    TheNadz is offline Member
    Join Date
    Nov 2010
    Posts
    9
    Rep Power
    0

    Default 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,

    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:

    Java 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:

    Java 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);
    		
    	}
    	
    }

  2. #2
    ra4king's Avatar
    ra4king is offline Senior Member
    Join Date
    Apr 2011
    Location
    Atlanta, Georgia, US
    Posts
    396
    Rep Power
    4

    Default

    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.

  3. #3
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,784
    Rep Power
    7

    Default

    Why have you introduced "stop" and a second method?

  4. #4
    TheNadz is offline Member
    Join Date
    Nov 2010
    Posts
    9
    Rep Power
    0

    Default

    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

    Java 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.

Similar Threads

  1. Turning Recursion Method into Iterative method
    By mattakuevan in forum New To Java
    Replies: 9
    Last Post: 06-15-2010, 06:46 AM
  2. Replies: 1
    Last Post: 03-17-2010, 05:25 AM
  3. My first recursion method: the number e
    By Lil_Aziz1 in forum Reviews / Advertising
    Replies: 1
    Last Post: 01-23-2010, 10:28 PM
  4. implement binary search method using recursion?
    By chopo1980 in forum New To Java
    Replies: 1
    Last Post: 12-12-2009, 03:58 PM
  5. Trouble with method
    By BlueJ2008 in forum New To Java
    Replies: 2
    Last Post: 10-19-2008, 09:05 PM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •