Results 1 to 8 of 8
Thread: Remove recursion
 11152009, 06:03 PM #1Member
 Join Date
 Nov 2009
 Posts
 3
 Rep Power
 0
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(xp)}) , 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]=xp; } // 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; } }
 11152009, 06:27 PM #2Member
 Join Date
 Nov 2009
 Posts
 23
 Rep Power
 0
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.

Usually a recursion causing a stack overflow is due to an inadequate or absent stopping condition.
 11152009, 06:35 PM #4Member
 Join Date
 Nov 2009
 Posts
 23
 Rep Power
 0
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. }
 11152009, 06:44 PM #5Member
 Join Date
 Nov 2009
 Posts
 3
 Rep Power
 0
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?
 11152009, 07:11 PM #6Member
 Join Date
 Nov 2009
 Posts
 23
 Rep Power
 0
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.
 11152009, 07:57 PM #7Member
 Join Date
 Nov 2009
 Posts
 3
 Rep Power
 0
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))...
 11152009, 10:24 PM #8Member
 Join Date
 Nov 2009
 Posts
 23
 Rep Power
 0
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);
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

Recursion
By jachandru in forum New To JavaReplies: 1Last Post: 01242009, 12:52 PM 
Recursion help
By rjg_2186 in forum New To JavaReplies: 1Last Post: 01022009, 08:03 AM 
Help With Recursion
By andrew777 in forum New To JavaReplies: 1Last Post: 03292008, 12:51 PM 
recursion
By kdeighan in forum New To JavaReplies: 3Last Post: 01252008, 09:48 PM 
Recursion
By bozovilla in forum Advanced JavaReplies: 3Last Post: 01072008, 04:53 PM
Bookmarks