C - "Stack Overflow" error when checking for prime numbers-CodePudding

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.

EDIT: 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!

CodePudding user response：

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.

CodePudding user response：

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.