Results 1 to 8 of 8
  1. #1
    ama03630 is offline Member
    Join Date
    Nov 2009
    Posts
    3
    Rep Power
    0

    Question Remove recursion

    This code compiles but gives me a StackOverFlow exception when I try to run it. I think I should remove the recursion, but can't think of any obvious solutions. Any suggestions?

    Java Code:
    /* Grundy function is defined as follows:
    	G(x) = mex ({G(x-p)}) , where p = {1}U{primes}, and mex stands 	   for MinimumExcluded natural number. That is, the least such natural number not in the set.
    This program finds the Grundy values of the 1 pile subtraction game, where a legal move consists of removing 1 or a prime.
    */ 
    import java.*;
    import java.util.*;
    public class nimprime	 
    {
    	public static void main(String args[]) 
    	{
    		for (int i=0; i<=90; i++)
    		{
    			System.out.printf("G(%d) = %d", i, G(i));
    			System.out.println();
    		}
    	}
    	/* recursive method to find Grundy values. I want to remove the recursion*/		
    	public static int G(int x) 
    	{
    		if (x==0)
    		{
    			return 0; //define G(0)=0.
    		}
    		else 
    		{
    	 
    			int size = 0;
    			// determine number of possible moves
    			for (int i=0; i<=x; i++)
    			{
    				if (isPrime(i))
    					size++;
    			}
    			int[] Garray = new int[size];
    			int[] values = new int[size];
    			/* fill values array with positions that are legal to 			   move to*/
    			for (int j=0; j<values.length; j++)
    			{
    				int p=j;
    				while (!isPrime(p))
    				{
    					p++;
    				}
    				values[j]=x-p;
    			}	
    			// fill Garray with Grundy values of those positions
    			for (int k=0; k<Garray.length; k++)
    			{
    				Garray[k]=G(values[k]); /* REMOVE THIS */
    			}
    			// Find mex
    			return mex(Garray);
    		}
    	}
    
    	// Method to determine if a number is 1 or prime
    	public static boolean isPrime(int x) 
    	{
    		boolean prime = true;
    		int num=0;
    		for (int i=2; i<x; i++)
    		{
    			num=x%i;
    			if (num==0)
    			{
    				prime = false;
    			}
    		}
    		return prime;
    	}
    	// Method to find MinimumExluded 
    	public static int mex(int[] values) 
    	{
    		int min=50000; //arbitrarily large number
    		int mex;
    		boolean duplicate = true;
    		
    		for(int i=0; i<values.length; i++)
    		{
    			if (values[i]<min)
    				min = values[i];
    		}	
    		if (min!=0)
    		{
    			mex = 0;
    		}
    		else
    		{
    			mex = min +1;
    		}
    		while (duplicate)
    		{
    			for(int k=0; k<values.length; k++)
    			{
    				if (mex==values[k])
    					mex++;
    			}
    			duplicate=false;
    			for(int m=0; m<values.length; m++)
    			{
    				if (mex==values[m])
    					duplicate = true;
    			}
    		}
    		return mex;
    	}
    }

  2. #2
    fgm1 is offline Member
    Join Date
    Nov 2009
    Posts
    23
    Rep Power
    0

    Default

    Interesting question. removing the recursion sounds like a drastic step. I'd start by tweaking the iteration loop in my main method. Find out the threshold value of the loop value i that causes the overflow.

    I'd also have a look at the array declarations in your recursive method. I can't say for sure this is the problem, but it might be. All those arrays might be using a lot of memory.

  3. #3
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,315
    Blog Entries
    1
    Rep Power
    26

  4. #4
    fgm1 is offline Member
    Join Date
    Nov 2009
    Posts
    23
    Rep Power
    0

    Default

    Quote Originally Posted by Fubarable View Post
    Usually a recursion causing a stack overflow is due to an inadequate or absent stopping condition.
    Good point. You might well be on the right track.

    The stop condition as shown below looks fine, it's another thing altogether to ensure that the value that gets passed in the recursion call is being reduced properly so that the stop condition is reached.

    Java Code:
    if (x==0)
        {
            return 0; //define G(0)=0.
        }

  5. #5
    ama03630 is offline Member
    Join Date
    Nov 2009
    Posts
    3
    Rep Power
    0

    Default

    Reducing the iteration loop in the main method to i<=1 causes the Stack Overflow. Does this neccessarilly mean that the value passed in to the recusion call is not getting reduced to 0 - the stopping condition?

  6. #6
    fgm1 is offline Member
    Join Date
    Nov 2009
    Posts
    23
    Rep Power
    0

    Default

    Quote Originally Posted by ama03630 View Post
    Reducing the iteration loop in the main method to i<=1 causes the Stack Overflow. Does this neccessarilly mean that the value passed in to the recusion call is not getting reduced to 0 - the stopping condition?
    Yes, based on your test, it certainly suggests the value being passed is not converging towards the stop condition. It's not at all clear to me from the recursion code how this is actually happening, but it is certainly a good possibility.

    I am not familiar with Grundy numbers, but you tell us. Is your stop condition correct as Fubarable suggested it might not be? What is supposed to happen to x. Do you have any idea how many times the function is called recursively? Any idea what kind of values are being passed? Try to come up with a strategy to track the information, That should give you some clues.

  7. #7
    ama03630 is offline Member
    Join Date
    Nov 2009
    Posts
    3
    Rep Power
    0

    Default

    The stop condition is correct, as I am defining G(0)=mex({}):= 0. The number of recursion calls is related to the number of primes + 1 between 0 and x. Some examples of how the information should flow:
    G(0)=mex({})=0
    G(1)=mex(G(0))=mex(mex{})=mex(0)=1
    G(2)=mex(G(1) , G(0))=mex(mex(G(0)), mex({}))=mex(mex(mex({}), 0)=mex(mex(0),0)=mex(1,0)=2
    G(3)=mex(G(2),G(1),G(0))...

  8. #8
    fgm1 is offline Member
    Join Date
    Nov 2009
    Posts
    23
    Rep Power
    0

    Default

    OK, well I suppose the problem is in the following code...

    Java Code:
    // fill Garray with Grundy values of those positions
    for (int k=0; k<Garray.length; k++)
    {
        Garray[k]=G(values[k]); /* REMOVE THIS */
    }
    // Find mex
    return mex(Garray);
    Most of my experience in recursion is with algorithms for searching decisin trees, such as minmax & alphabeta. In those situations, the stop conditions is based on a simple integer that is decremented at each recursive call. So there is no way for the value not to converge to the stop condition.

    I can't say the same for values[k]. It is some pretty complex code that goes into the determination of values[k], and it is my guess that this might not be the appropriate value to pass.

    You might consider a main method that, instead of a loop, consists of a single call to G. e.g. simple G(1);

    Then you might have a stop condition such is if( x==90 ) return 0;

    then your recursion call within the G method might be G(x+1)

    I'm just winging it here, of course the involves a total redesign. Since you are dealing with primes you might even have more then one recursive method.

    Do you see what I mean? Do you think you could make something like that work. It has the advantage of simplifying your recursion call thus making it easier to determine whether or not you have conversion to the stop condition.

Similar Threads

  1. Recursion
    By jachandru in forum New To Java
    Replies: 1
    Last Post: 01-24-2009, 01:52 PM
  2. Recursion help
    By rjg_2186 in forum New To Java
    Replies: 1
    Last Post: 01-02-2009, 09:03 AM
  3. Help With Recursion
    By andrew777 in forum New To Java
    Replies: 1
    Last Post: 03-29-2008, 01:51 PM
  4. recursion
    By kdeighan in forum New To Java
    Replies: 3
    Last Post: 01-25-2008, 10:48 PM
  5. Recursion
    By bozovilla in forum Advanced Java
    Replies: 3
    Last Post: 01-07-2008, 05:53 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
  •