How to calculate and print first N Prime Numbers Using Recursion

Question

I wrote the following recursive code but the outcome is strange. Please Help to find the error in my C code.

For example if I take the value of n as 10 then the output should be 2,3,5,7,11,13,17,19,23,29 but with to my code the output is 2 3 5 7 9 11 13 15 17 19

Ahh! I tried for a long time but couldn't find the problem. Here is my recursive C code:

void primeNumbers (int n)
{
    if (n == 0)  
        return;

    static int i = 2;
    
    if (isPrime(i))      
    {
        printf("%d ", i);
        i++;                
        primeNumbers(n - 1);
    }
    else 
    {
        i++;
        primeNumbers(n);
    }
}

The function to check Number is Prime or not:

bool isPrime(int n)
{
    // edge case, not a base case
    if (n <= 1)
        return false;

    static int i = 2; 
    
    if (i > n / 2) 
        return true;
    
    if (n % i == 0) 
        return false;
    
    i++;
    return isPrime(n); // call again with i+1 value
}

Output: [if N is 10]

2 3 5 7 9 11 13 15 17 19

if I take the value of n as 10 then the output should be 2,3,5,7,11,13,17,19,23,29 but with to my code the output is 2 3 5 7 9 11 13 15 17 19.

[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) Hint: don't use static variables. Thank me later. — n. m. could be an AI, Jul 10 '23 at 07:21
The logic in `isPrime` is obviously wrong as `9` isn't a prime. — Support Ukraine, Jul 10 '23 at 07:47
As indicated above, the use of `static` is your problem. (NB: using recursion here is really artificial -- it provides no benefit, only downsides) — trincot, Jul 10 '23 at 07:48
Sometimes you say that your output is "2 3 5 7 9 11 13 15 17 19". Sometimes you say that your output is "2,3,5,7,9,11,13,17,19" (which is wrong). Please edit. — Support Ukraine, Jul 10 '23 at 07:51

chqrlie · Accepted Answer · 2023-07-11T07:08:47.783

The problem is you use a static variable i for the divisor that never gets reset to 2 for the next number to test.

Here is an alternative recursive implementation of isPrime:

bool testPrime(int n, int div) {
    if (n / div < div)
        return true;
    else
    if (n % div == 0)
        return false;
    else
        return testPrime(n, div + 1);
}

bool isPrime(int n) {
    return n >= 2 && testPrime(n, 2);
}

The recursive function can be simplified as a single expression:

bool testPrime(int n, int div) {
    return (n / div < div) || (n % div != 0 && testPrime(n, div + 1));
}

The enumerating function is also incorrect for the same reason: static variable i is never reset to 2 so the function would only work once, and you call it recursively with n - 1 after testing and printing i so it stops enumerating half way.

The same approach can be taken for primeNumbers() to convert a loop into recursive calls:

void printPrimes(int p, int n) {
    if (n > 0) {
        if (isPrime(p)) {
            printf("%d ", p);
            printPrimes(p + 1, n - 1);
        } else {
            printPrimes(p + 1, n);
        }
    }
}

void primeNumbers(int n) {
    printPrimes(2, n);
    printf("\n");
}

Thanks, but according to your primeNumbers( ) function in range of N prime numbers will be printed but i said to print N terms of prime numbers. if n is 5 then- 2, 3, 5, 7, and 11. — Rana, Jul 11 '23 at 05:48

How to calculate and print first N Prime Numbers Using Recursion

1 Answers1