In this post I would be discussing recursive primality test. I have already discussed iterative primality test in my earlier post Prime time. Note that recursive methods are always more expensive in terms of performance and memory usage. Recursion’s only advantage is that some algorithms can be expressed more elegantly using recursive techniques. The Java program for the recursive primality test is as follows:

class RecursivePrimalityTest{
    private static boolean isPrimeRecursive( int n, int divisor ){
        if( divisor > (n/2) ) return true;
        else if( n % divisor == 0 ) return false;
        else return isPrimeRecursive( n , divisor + 2 );
    }
    public static boolean isPrimeRecursive( int n ){
        if( n < 2 ) return false;
        else if( n == 2 ) return true;
        else if( n % 2 == 0 ) return false;
        else return isPrimeRecursive( n, 3 );
    }
    public static void main(String args[]){
        System.out.println("Test cases for primality");
        System.out.println("-1\t:"+isPrimeRecursive(-1));
        System.out.println("1\t:"+isPrimeRecursive(1));
        System.out.println("2\t:"+isPrimeRecursive(2));
        System.out.println("3\t:"+isPrimeRecursive(3));
        System.out.println("4\t:"+isPrimeRecursive(4));
        System.out.println("15\t:"+isPrimeRecursive(15));
        System.out.println("113\t:"+isPrimeRecursive(113));
    }
}

Notice that the function isPrimeRecursive( ) is overloaded. User would invoke the public isPrimeRecursive( ) with only one integer argument to test for a prime number. The one argument public function would then perform some basic tests to quickly arrive at the result for some special cases, if applicable. Special cases are as follows:

1. Numbers less than two are not prime.
2. Two is the only even prime number.
3. Even numbers other than two are not prime.

If the above special cases are not applicable, then the private recursive function isPrimeRecursive( ) function with two integer arguments would be invoked. The first value of divisor would be 3. If n is divisible by the divisor, n can’t be prime and false would be returned. If n is more than half of n, there won’t be any factors of n and hence the number is prime, so true is returned. We are starting with the divisor 3, we will keep on trying with higher divisors in increments of two because prime numbers other than two are not even and hence there is no point in dividing by even number.

As usual, the main function has purposely been kept to minimum and its expected that students will write appropriate input/output statements as per the requirement.