Writing a program in C that uses recursion to determine if a number is prime or not. Getting a stack overflow error at high numbers

Question

Writing a program in C that uses recursion to determine if a number is prime or not. It works until you try it with a prime number above 9431. Anything higher than that gets a stack overflow error. I was wondering if there was some way to fix this.

I haven't really tried anything other than see at which number it fails at, which varies each time.

//Remove scanf error
#define _CRT_SECURE_NO_WARNINGS

//Preprocessor directives
#include<stdio.h>
#include<stdlib.h>

//Recursion function
int PrimeCheck(int choice, int i)
{
    //Check if integer i is reduced to 1
    if (i == 1)
    {
        return 0;
    }
    else
    {
        //Check to see if number choice is divisible by value i
        if (choice % i == 0)
        {
            return 1;
        }

        //Call the function again but reduce the second variable by 1
        else
        {
            return PrimeCheck(choice, i - 1);
        }
    }
}//End PrimeCheck function

//Main function
main()
{
    //Assign needed variables
    int choice, num;

    //ask for user input
    printf("Please enter a number between 2 and %i:", INT_MAX);
    scanf("%i", &choice);

    //Check for numbers outside the range
    if (choice < 2 || choice > INT_MAX)
    {
        printf("Please try again and enter a valid number.\n");
        system("pause");
        return 0;
    }

    //Call the PrimeCheck "looping" function
    num = PrimeCheck(choice, choice / 2);

    //Display result for the user
    if (num == 0)
    {
        printf("%i is a prime number.\n", choice);
    }

    else
    {
        printf("%i is NOT a prime number.\n", choice);
    }

    system("pause");
}//End main

The output should be "____ is a prime number" or "____ is NOT a prime number" The actual output above 9431 is a stack overflow error.

Answer 1

One help, reduce tests.

PrimeCheck(choice, choice / 2); iterates about choice/2 times when only sqrt(choice) times needed.

Instead of starting at choice/2

PrimeCheck(choice, sqrt(choice));

Better code would avoid small rounding error and integer truncation with

PrimeCheck(choice, lround(sqrt(choice)));

or if you have access to an integer square root function:

PrimeCheck(choice, isqrt(choice));

For 9431, this will reduce stack depth by about a factor of 50 - and speeds the program.

---

Speed performance tip. Rather than iterate from choice / 2 or sqrt(choice) down to 1. Go up from 2 to sqrt(choice). Non-primes will be detected much faster.

---

Sample

#include <stdbool.h>
#include <stdio.h>

bool isprimeR_helper(unsigned test, unsigned x) {
  // test values too large, we are done
  if (test > x/test ) {
    return true;
  }
  if (x%test == 0) {
    return false; // composite
  }
  return isprimeR_helper(test + 2, x);
}

bool isprimeR(unsigned x) {
  // Handle small values
  if (x <= 3) {
    return x >= 2;
  }
  // Handle other even values
  if (x %2 == 0) {
    return false;
  }
  return isprimeR_helper(3, x);
}

int main(void) {
  for (unsigned i = 0; i < 50000; i++) {
    if (isprimeR(i)) {
      printf(" %u", i);
    }
  }
  printf("\n");
}

Output

2 3 5 7 11 13 17 19 ... 49991 49993 49999

---

Implementations notes

Do not use if (test*test > x). Use test > x/test

• test*test may overflow. x/test will not.

• Good compilers will see nearby x/test and x%test and compute both effectively as one operation. So if code has x%test, the cost of x/test if often negligible.