How do I avoid the recursion limit in Mathematica?

[ramsey2879]

I wrote code where you input a prime, P > 3, and the next prime is the output. However it involves using a recursive formula with the number of recursive steps being in the order of P and using the Mod operator. Thus P must be below 255. How can I avoid this. Follows is my code:

prime = 127 (* can be any prime >3 and < 255 *)
c = prime + 2;
While[True,
d = c-prime + 1;
Clear[g];
g[0] = 0; g[1] = 1; g[x_] := g[x] = Mod[(d g[x-1] - g[x-2]),c];
If[g[c-1]==0,(If[g[c]==1,prime = c;Break[]])];
If[g[c+1]==0,(If[g[c+2]==1,prime = c; Break[]])];
c+=2];prime

 

[jim mcnamara]

I have been hesitant to say much here, because I know so very little.

[$RecursionLimit = 10^3 ]

raises the recursion limit.

http://reference.wolfram.com/mathematica/ref/$RecursionLimit.html

 

[ramsey2879]

I have been hesitant to say much here, because I know so very little.

[$RecursionLimit = 10^3 ]

raises the recursion limit.

http://reference.wolfram.com/mathematica/ref/$RecursionLimit.html

Thanks for the link. I was able to exceed the limit of 255 and found that if prime 317 is the input, then imy code gives nextprime is 323 when in fact the next prime is 331. So I have more work cut out for me. You can avoid the recursion limit with any code if you use:
Block[{$RecursionLimit=Infinity},CODE]

 

[jim mcnamara]

Since you mentioned your algorithm, consider sieving. Which you sort of seem to be doing. For the magnitude of numbers you seem to be using the Sieve of Eratothenes is super simple and effective (for people programming in C on 32bit machines, for example) up to INT_MAX. Solved most the Project Euler problems, then-existing, a long time ago, on a P4 box. Try 'em sometime. Some were a lot fun. Anyway, many involved primes. The box I had could create a list of primes up to UINT_MAX in less than 10ms. Here is the stripped down S of E algorithm if you are interested. Mathematica has prime generation already. Look up "Prime"

#define true 1
#define false 0

static unsigned int *primes=NULL;
void esieve(const size_t limit)
{
   unsigned int i=0;
   unsigned int j=0;
   int sq=(int)sqrt(limit);
   primes=calloc( (limit + 1),  sizeof(int) ); // set array to true
   
   for(i=2; i<=sq; i++)
   {
      if(primes[i]==true)
         for(j=i+i; j< limit; j+=i)
            primes[j]=false;
   }
}

unsigned int nextprime(unsigned int val)
{
   val++;
   while(primes[val]==false) 
     val++;
   return val;  
}

int isprime(unsigned int val)
{
    return primes[val];
}

 

[Bill Simpson]

You can avoid the recursion limit with any code if you use:
Block[{$RecursionLimit=Infinity},CODE]

That is perhaps only true if you have infinite, or large, amounts of memory to keep track of finite, but large, or even infinitely deep recursion.

Since it looks like you are only keeping track of fairly small integer values for each level of recursion, you might think about whether it would be possible to "simulate" recursion in your program by just having a list (table) of values and your code would then do the calculations and steps needed to update the values in the table for each iteration of your code.

This might take up substantially less memory than trying to save the state of the function and do "real recursion." It might also get you to think carefully about how the program actually works as you try to make these changes and understanding the behavior of a program almost always seems like a good idea.