Java: Find out if a number is prime recursively

I’m writing a function that returns true if a number is prime, and false otherwise

Here is my current code:

    public static boolean checkPrime(int n, int currDivisor){
        if(n < 2){
            return true;
        }
        if(currDivisor == (n/2)){
            return true;
        }
        else if(n % currDivisor == 0 ){
            return false;           
        }
        else{
            return checkPrime(n, currDivisor + 1);
        }
    }

    public static void main(String[] args){
        System.out.println(checkPrime(23352, 2));
    }

It works for a lot of test cases except numbers like “1000000007” where I get an Out of memory error. How could I tweak this code to be more efficient space-wise?

Answer

The first problem I see is that your program is it’s buggy. It seems to think that 0, 1, & 4 are primes and that 3 isn’t. The second problem I see is that it’s wasting stack frames not properly dealing with simple cases before recursing. Here’s my rework of your code:

public static boolean checkPrime(int n) {
    return checkPrime1(n, 3);
}

public static boolean checkPrime1(int n, int currDivisor) {
    if (n < 2) {
        return false;
    }

    if (n % 2 == 0) {
        return (n == 2);
    }

    if (currDivisor * currDivisor > n) {
        return true;
    }

    if (n % currDivisor == 0) {
        return false;
    }

    return checkPrime1(n, currDivisor + 2);
}

As far as handling:

System.out.println(checkPrime(1000000007));

You’ll still get an java.lang.StackOverflowError but that’s not the end of the story. Most languages make decisions of how much memory to allocate to specific purposes. It’s the rare language like Perl that will reallocate memory to whatever resource is demanding it most and not make assumptions about how a program should behave.

You can change the amount of memory allocated to Java’s stack — calling java with the -Xss2m argument allocates sufficient extra stack to let you test 1000000007 (true, by the way.)

If you change the three int declarations above to long, you’ll be able to test numbers like 2547487897L or larger as long as you expand the stack (-Xss4m in this case.)

I’m not saying that this is a good problem for recursion, it isn’t. But if you’re going to use recursion, use it wisely. It’s poor recursion that’s gives recursion a bad name. There are inefficient recursive Fibonnaci algorithms (usually doubly recursive) and efficient (singly recursive) ones. Recursive code usually works best with recursive data.

Some languages, not yet Java consistently, can optimize the above code as a tail recursion and make it effectively iterative performance.