Power function using recursion

Question

I have to write a power method in Java. It receives two ints and it doesn't matter if they are positive or negative numbers. It should have complexity of O(logN). It also must use recursion. My current code gets two numbers but the result I keep outputting is zero, and I can't figure out why.

import java.util.Scanner;

public class Powers {

    public static void main(String[] args) {
        float a;
        float n;
        float res;

        Scanner in = new Scanner(System.in);
        System.out.print("Enter int a ");
        a = in.nextFloat();

        System.out.print("Enter int n ");
        n = in.nextFloat();

        res = powers.pow(a, n);

        System.out.print(res);
    }

    public static float pow(float a, float n) {
        float result = 0;

        if (n == 0) {
            return 1;
        } else if (n < 0) {
            result = result * pow(a, n + 1);
        } else if (n > 0) {
            result = result * pow(a, n - 1);
        }

        return result;
    }
}

Answer 1

Let's start with some math facts:

• For a positive n, aⁿ = a⨯a⨯…⨯a n times
• For a negative n, aⁿ = ⅟a⁻ⁿ = ⅟(a⨯a⨯…⨯a). This means a cannot be zero.
• For n = 0, aⁿ = 1, even if a is zero or negative.

So let's start from the positive n case, and work from there.

Since we want our solution to be recursive, we have to find a way to define aⁿ based on a smaller n, and work from there. The usual way people think of recursion is to try to find a solution for n-1, and work from there.

And indeed, since it's mathematically true that aⁿ = a⨯(aⁿ⁻¹), the naive approach would be very similar to what you created:

public static int pow( int a, int n) {
    if ( n == 0 ) {
        return 1;
    }
    return ( a * pow(a,n-1));
}

However, the complexity of this is O(n). Why? Because For n=0 it doesn't do any multiplications. For n=1, it does one multiplication. For n=2, it calls pow(a,1) which we know is one multiplication, and multiplies it once, so we have two multiplications. There is one multiplication in every recursion step, and there are n steps. So It's O(n).

In order to make this O(log n), we need every step to be applied to a fraction of n rather than just n-1. Here again, there is a math fact that can help us: a^n₁+n₂ = a^n₁⨯a^n₂.

This means that we can calculate aⁿ as a^n/2⨯a^n/2.

But what happens if n is odd? something like a⁹ will be a^4.5⨯a^4.5. But we are talking about integer powers here. Handling fractions is a whole different thing. Luckily, we can just formulate that as a⨯a⁴⨯a⁴.

So, for an even number use a^n/2⨯a^n/2, and for an odd number, use a⨯ a^n/2⨯a^n/2 (integer division, giving us 9/2 = 4).

public static int pow( int a, int n) {
    if ( n == 0 ) {
        return 1;
    }
    if ( n % 2 == 1 ) {
        // Odd n
        return a * pow( a, n/2 ) * pow(a, n/2 );
    } else {
        // Even n
        return pow( a, n/2 ) * pow( a, n/2 );
    }
}

This actually gives us the right results (for a positive n, that is). But in fact, the complexity here is, again, O(n) rather than O(log n). Why? Because we're calculating the powers twice. Meaning that we actually call it 4 times at the next level, 8 times at the next level, and so on. The number of recursion steps is exponential, so this cancels out with the supposed saving that we did by dividing n by two.

But in fact, only a small correction is needed:

public static int pow( int a, int n) {
    if ( n == 0 ) {
        return 1;
    }
    int powerOfHalfN = pow( a, n/2 );
    if ( n % 2 == 1 ) {
        // Odd n
        return a * powerOfHalfN * powerOfHalfN;
    } else {
        // Even n
        return powerOfHalfN * powerOfHalfN;
    }
}

In this version, we are calling the recursion only once. So we get from, say, a power of 64, very quickly through 32, 16, 8, 4, 2, 1 and done. Only one or two multiplications at each step, and there are only six steps. This is O(log n).

The conclusion from all this is:

1. To get an O(log n), we need recursion that works on a fraction of n at each step rather than just n - 1 or n - anything.
2. But the fraction is only part of the story. We need to be careful not to call the recursion more than once, because using several recursive calls in one step creates exponential complexity that cancels out with using a fraction of n.

Finally, we are ready to take care of the negative numbers. We simply have to get the reciprocal ⅟a⁻ⁿ. There are two important things to notice:

• Don't allow division by zero. That is, if you got a=0, you should not perform the calculation. In Java, we throw an exception in such a case. The most appropriate ready-made exception is IllegalArgumentException. It's a RuntimeException, so you don't need to add a throws clause to your method. It would be good if you either caught it or prevented such a situation from happening, in your main method when you read in the arguments.
• You can't return an integer anymore (in fact, we should have used long, because we run into integer overflow for pretty low powers with int) - because the result may be fractional.

So we define the method so that it returns double. Which means we also have to fix the type of powerOfHalfN. And here is the result:

public static double pow(int a, int n) {
    if (n == 0) {
        return 1.0;
    }
    if (n < 0) {
        // Negative power.
        if (a == 0) {
            throw new IllegalArgumentException(
                    "It's impossible to raise 0 to the power of a negative number");
        }
        return 1 / pow(a, -n);
    } else {
        // Positive power

        double powerOfHalfN = pow(a, n / 2);
        if (n % 2 == 1) {
            // Odd n
            return a * powerOfHalfN * powerOfHalfN;
        } else {
            // Even n
            return powerOfHalfN * powerOfHalfN;
        }
    }
}

Note that the part that handles a negative n is only used in the top level of the recursion. Once we call pow() recursively, it's always with positive numbers and the sign doesn't change until it reaches 0.

That should be an adequate solution to your exercise. However, personally I don't like the if there at the end, so here is another version. Can you tell why this is doing the same?

public static double pow(int a, int n) {
    if (n == 0) {
        return 1.0;
    }
    if (n < 0) {
        // Negative power.
        if (a == 0) {
            throw new IllegalArgumentException(
                    "It's impossible to raise 0 to the power of a negative number");
        }
        return 1 / pow(a, -n);
    } else {
        // Positive power
        double powerOfHalfN = pow(a, n / 2);
        double[] factor = { 1, a };
        return factor[n % 2] * powerOfHalfN * powerOfHalfN;
    }
}