"Stack Overflow" error when checking for prime numbers

Question

I was taking a look at the following C Program exercise I found online which is an example on how to check for prime numbers using a recursive method, but when I tried it on my Visual Studios 2019 compiler, I found that certain numbers will simply cause a "Stack Overflow" error.

The exercise requires recursion instead of loops which is why I'm facing a stack overflow.

//c program to check whether a number is prime or not using recursive function
#include<stdio.h>
#include <stdlib.h>

int is_prime_number(int num, int i)   //Function Definition
{
    if(num < 2)
    {
       printf("\n Enter numbers greater than 1");
       exit(0);
    }
    if (i == 1)
    {
      return 1;
    }
    else
    {
      if (num % i == 0)
      {
         return 0;
      }
      else
      {
         return is_prime_number(num, i-1);
      }
    }
}

//Driver Code
int main()
{
   int n, flag; //Declare the variables
                       
   printf("Enter a number: \n"); // Ask the user for an input
   scanf("%d",&n);       
              
   flag = is_prime_number(n, n / 2);   //Function Call

   if (flag == 1)             //Print whether prime or not
   {
      printf("%d is a prime number\n", n);
   }
   else
   {
      printf("%d is not a prime number\n", n);
   }
   
   return 0;
}

For example a number like 77 or 120 will come back as not prime numbers, and numbers like 11 and 127 come back as prime numbers; however, when using big numbers like 23479823 a "Stack Overflow" error occurs and the program freezes. I also tried an even bigger number within INT_MAX of 2147483646 and it successfully came back as not prime.

Would greatly appreciate any clues on why this is occurring!

It is cool to ask a question about "stack overflow" here on SO. But, really, you should be more critical when finding code on the internet. This is an awful implementation of a prime number checker: the recursion does not serve any purpose, parameter check is in the recursive function, it checks too many divisors in the wrong order (from least probable to most probable), ... — nielsen
– nielsen, Commented Jan 16, 2022 at 21:17
Whether or not a stack overflow occurs depends on the number of divisor candidates to be checked. Hence an even number as 2147483646 will only require 1 iteration while an odd number like 23479823 will require at least n/6 iterations (=n/2-n/3 since n/3 is the next candidate that may be a divisor). — nielsen
– nielsen, Commented Jan 16, 2022 at 21:26

Chris Dodd · Accepted Answer · 2022-01-16 20:55:00Z

2

You've written your program such that to test each additional possible factor, you make a recursive call. This (potentially) requires a stack frame, so will quickly run out of stack space if it needs to check many factors.

Most compilers these days will do tail call optimization, so make sure you have optimization turned on (-O or /O depending on the compiler) and it may work. However, there is no guarantee that tail-call optimization will be done, so you can't reliably write heavily recursive code like this in C safely. You need to use a loop instead.

answered Jan 16, 2022 at 20:55

Chris Dodd

127k14 gold badges150 silver badges243 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

0___________ · Accepted Answer · 2022-01-16 21:05:31Z

2

The number is 23479823. The function will call itself more than 11 million times. Every call will need another stack frame. How much it will be depends on the implementation, optimization etc but it will be more than 24MB. Stack is much smaller on Windows (I do not remember now exactly - but I think is about 1MB.). Because you need much more - you overflow it

You can lucky of course if the compiler will optimize the recursion out - but as you see it does not happen in your case.

edited Jan 16, 2022 at 21:05

answered Jan 16, 2022 at 20:55

0___________

71.6k4 gold badges41 silver badges94 bronze badges

Collectives™ on Stack Overflow

"Stack Overflow" error when checking for prime numbers

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related