Thread: Recursion

  1. #1
    Registered User
    Join Date
    Oct 2012
    Posts
    126

    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;
    }
    Last edited by Sorinx; 11-05-2012 at 06:38 PM.

  2. #2
    Registered User
    Join Date
    May 2012
    Location
    Arizona, USA
    Posts
    945
    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.

  3. #3
    Registered User
    Join Date
    Oct 2012
    Posts
    126
    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.
    Last edited by Sorinx; 11-05-2012 at 06:39 PM.

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    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.

  5. #5
    Registered User
    Join Date
    Oct 2012
    Posts
    126
    Quote Originally Posted by anduril462 View Post
    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

  6. #6
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    Quote Originally Posted by Sorinx View Post
    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

  7. #7
    Registered User
    Join Date
    Oct 2012
    Posts
    126
    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;
        }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Recursion - Sum
    By gqchynaboy in forum C++ Programming
    Replies: 10
    Last Post: 09-14-2005, 06:47 AM
  2. ::please help with recursion::
    By daioyayubi in forum C++ Programming
    Replies: 4
    Last Post: 08-17-2005, 01:41 AM
  3. recursion!!!
    By samirself in forum C Programming
    Replies: 3
    Last Post: 07-16-2005, 03:05 PM
  4. Recursion
    By Lionmane in forum C Programming
    Replies: 11
    Last Post: 06-04-2005, 12:00 AM
  5. How would I do this using recursion?
    By Josephus_1 in forum C++ Programming
    Replies: 4
    Last Post: 12-19-2002, 08:32 PM