1. Member
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(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. Member
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.

3. Member
Join Date
Nov 2009
Posts
23
Rep Power
0
Originally Posted by Fubarable
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.
}```

4. Member
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?

5. Member
Join Date
Nov 2009
Posts
23
Rep Power
0
Originally Posted by ama03630
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.

6. Member
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))...

7. Member
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);```
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.