Determining if a number is prime with recursion

Question

I am currently writing a function that uses recursion to see if a number is prime, and here is what I have so far:

My declaration is

bool isPrime(int num, int divisor = 2);

bool isPrime(int num, int divisor){
    if (num == 1){
        return true;
    }
    else{
        if (num%divisor == 0){
            return false;
        }
        else{
            if (divisor == num){
                return false;
            }
        return isPrime(num, divisor++);
        }
    }
}

I'm new to C++, so I'm not sure if that's how you set a parameter to start at a certain number. But when I run this function, visual studios crashes on me. Any ideas?

Why do you need recursion here at all? And at least you will need either `while`, either recursion, not both. — Petr, Apr 24 '15 at 09:15
You are right, let me try and solve this without a while loop then — Tyler, Apr 24 '15 at 09:16
@Petr: While I'm doing this, is my syntax for setting the divisor correct? — Tyler, Apr 24 '15 at 09:19
1 is not prime. The smallest prime number is 2. And the only number your function thinks is prime is 1. — molbdnilo, Apr 24 '15 at 09:23
@Tyler, for passing it as a function parameter in `isPrime(num, divisor++)`? The syntax itself is correct, but is does not do what you want. It passes the _unicreased_ value of `divisor` to `isPrime`, and only then increases the value of `divisor`. I guess you want to first increase, and then pass, which is `isPrime(num, ++divisor)`. Though I still think that recursion is a definitely unsuitable here. — Petr, Apr 24 '15 at 09:25
divisor++ is the problem - I think you get infinite recursion at divisor = 2. You could work this out for yourself by putting a std::cout << divisor << "\n" in the function, and I highly recommend this approach to debugging recursion. — Andy Newman, Apr 24 '15 at 09:27
@Petr Yes, you are right. Can you briefly explain to me what ++divisor does? — Tyler, Apr 24 '15 at 09:30
@Tyler, I'd better suggest you obtaining a good book or other source to learn C++. — Petr, Apr 24 '15 at 09:59

score 0 · Accepted Answer · edited May 23 '17 at 12:06

0

You have updated the question, let me suggest you a cleaner version of the code, you do not need so many nested loops.

My fixes are described in the comments. For the second fix, please see here.

bool isPrime(int num, int divisor)
{
    if (num == 1)
    {
        return true;
    }
    else if (num%divisor == 0)
    {
        return true; // <- if we are here the number is prime
    }
    else if (divisor == num)
    {
        return false;
    }

    return isPrime(num, ++divisor); // <- you want to augment divisor BEFORE giving it to the function

}

Additionally, the call should not be bool isPrime(int num, int divisor = 2); but rather

bool result = isPrime(num, 2);

This is the answer to the question as originally posted:

Your problem is here:

(num%divisor == 0) && (divisor == num)

you do not need

(divisor == num)

you already have

while (divisor != num)

edited May 23 '17 at 12:06

Community

1
1

answered Apr 24 '15 at 09:17

Federico

1,092
3
16
36

Or even better drop the second condition at all, as it is not needed. – Petr Apr 24 '15 at 09:19
I've updated the question now. Please take a look. Also, visual studios seems to crash if the user enters odd numbers. Is there any reason why this is happening? – Tyler Apr 24 '15 at 09:23
@Federico For my declaration `bool isPrime(int num, int divisor = 2);`, is the syntax correct? Also, this function recognizes every number as a prime number now – Tyler Apr 24 '15 at 09:40
@Tyler no, you need `bool result = isPrime(num, 2);` adding it to the answer. – Federico Apr 24 '15 at 10:34

score 0 · Answer 2 · answered Apr 24 '15 at 09:30

There are unnecessary lines in your code. For example, you have a while loop that will always reach a return statement on the first iteration.

You should make you function simpler. Here an example doing what you seek.

bool isPrime(int num) {
    return isPrimeRec(num, 2);
}

bool isPrimeRec(int num, int div) {
    if ( num == div || num == 1 )
        return true;
    else if ( num % div == 0 )
        return false;
    else
        return isPrime(num, div+1);
}

In this example, you first check if this iteration is sufficient to find the answer. If not, you increment the divisor and apply the operation recursively. I have also used two different functions to simplify how you set the parameter. Avoiding nested loops and conditions will help you review your code.

This is an example of functional programming and tail recursion.

Determining if a number is prime with recursion

2 Answers2