# Recursion

• 11-05-2012
Sorinx
Recursion
Trying to make a program that returns a set of prime numbers that equal an even integer between 700 and 1200. Supposed to define START as 700 and FINISH as 1100. Basically I'm stuck because it's not working at all.

Code:

```#include<stdio.h> int numPrime(int num); int goldBach(); int main() { goldBach(); } int goldBach(void) { int i, j, k, l=700, m=1100, ans;   for(i=l; i<=m; i++){       for(j=i; j>2; j--){                 ans=numPrime(j);           if(ans!=0){                             k=j-l;                 ans=numPrime(k);                   }if(ans!=0){                                           if( i == (j + k)){                         printf("%d = %d + %d\n", i, j, k);                       }                 }             }         }        }     int numPrime(int num) {         static int i=2; /* i initialized as static because it has to remain stored as +1 in recursive call, took me awhile to realize why it was freezing */         if(i<=num){ /* if 2 is less than number and number/i has 0 remainder then return 0 else add 1 to i and call the function again. */         if(num%i==0)             return 0;                     else{                     i++;             numPrime(num);     }     }         i=2;         return 1; }```
• 11-05-2012
christop
The i variable is not reset to 2 every time numPrime is called from goldBach. It is set to 2 only when the program starts, or when you explicitly set it to 2 in your own code.
• 11-05-2012
Sorinx
Yeah I forgot to set the static 2 to 2 again in the function. I fixed that. Still not giving me the correct numbers not sure what's wrong.
• 11-05-2012
anduril462
Don't use recursion to implement numPrime. A for loop is a much better approach. For larger numbers, recursion will likely blow out your stack and your program may crash. If you have to use global or static local variables to make your recursive solution work, it's probably not something you should do recursively.

Also, there are a couple simple speedups you can do to your basic isPrime check:
1. Instead checking divisors < num, just check divisors <= sqrt(num). Don't calculate sqrt(num) in the loop though, it's slow. Calculate it once and store the result in a temporary variable. Use the temp variable in your loop condition.
2. Check for divisibility by 2 explicitly, then start your loop at 3 and increment i by 2 each iteration.

There are much more efficient ways to check for primality, but your implementation is the simplest to code and most intuitive, so stick with that for now.
• 11-05-2012
Sorinx
Quote:

Originally Posted by anduril462
Don't use recursion to implement numPrime. A for loop is a much better approach. For larger numbers, recursion will likely blow out your stack and your program may crash. If you have to use global or static local variables to make your recursive solution work, it's probably not something you should do recursively.

Also, there are a couple simple speedups you can do to your basic isPrime check:
1. Instead checking divisors < num, just check divisors <= sqrt(num). Don't calculate sqrt(num) in the loop though, it's slow. Calculate it once and store the result in a temporary variable. Use the temp variable in your loop condition.
2. Check for divisibility by 2 explicitly, then start your loop at 3 and increment i by 2 each iteration.

There are much more efficient ways to check for primality, but your implementation is the simplest to code and most intuitive, so stick with that for now.

I have to use recursion or I wouldn't have done this in the first place. I'm not really looking for speed optimization, as there are only so many numbers that are going to be calculated. More looking for the output to be correct lol thank you though
• 11-06-2012
AndiPersti
Quote:

Originally Posted by Sorinx
Yeah I forgot to set the static 2 to 2 again in the function. I fixed that. Still not giving me the correct numbers not sure what's wrong.

Your understanding of recursion is wrong. All these nested functions calls will finally return back to where you started and thus numPrime() will return 1 to main() for every odd number and 0 for every even number.

I think you have forgotten that all these function calls return to the caller and not directly to main().

Bye, Andreas
• 11-09-2012
Sorinx
Lol I guess I have no idea how recursion works! Anyways I made a small error in my return values not in my understanding of how recursion works thank you. Finished code, hopefully it can help someone out in the future.

Code:

```#include<stdio.h> int numPrime(int num); //declare function prototypes int goldBach(); int main() { goldBach();//function call } int goldBach(void) //function definition { int i, j, k, l=700, m=1100, ans; //variable declarations   for(i=l; i<=m; i+=2){// for loop for how many iterations so between 700 and 1100       for(j=i; j>2; j--){  //nested for to find the first prime number                 ans=numPrime(j);//function call to check if j is prime           if(ans!=0){//if j is prime then k= i-j. then check if k is prime. if k is prime and K is greater than 2. print out the variables. break to outter loop                             k=i-j;                 ans=numPrime(k);                   }if(ans!=0 && k>2){                                           if( i == (j + k)){                         printf("%d = %d + %d\n", i, j, k);                         break;                     }                 }             }         }        }     int numPrime(int num) {         static int i=2; /* i initialized as static because it has to remain stored as +1 in recursive call*/         /* if 2 is equal to number/ return 1/ if num% i has 0 remainder then return 0 else add 1 to i and call the function again. else return i. reset i to 2 */         if(i==num)         return 1;         if(num%i==0)             return 0;                     else{                 if(i<num){             i++;             numPrime(num);             }else             return 1;     }     i=2;     }```