Recursive "Power Of" function

Question

We are given an assignment to solve a recursive function that can calculate the power of a number using the following rules (took a snapshot):

https://i.sstatic.net/bphmY.png

I cant seem to figure out to do this as I have been trying for the past 4 hours. My attempt:

public static double power(double x, int n) {   
    if(n == 0) {
        return 1;
    }
    //    x^n = ( x^n/2 )^ 2  if n > 0 and n is even
    if(n % 2 == 0) {
        double value = ((x * power(x, n/2)) * x);
        return value;
    } else {
        double value = x * ((x * power(x, n/2)) * x);
        return value;       
    }
}

I believe I am doing wrong when I am multiplying x with the recursive function whereas I should be multiplying by x (power Of = x * x * .... x(n))...

I also can see that in this statement:

 double value = ((x * power(x, n/2)) * x);

It is wrong because I am not squaring the value but just multiplying it with x. I think I need to store it in a variable first, then do something like value * value to square the end result - but that just gives me a huge number.

Any help is appreciated, thanks.

Answer 1

The problem is in this statement:

if(n % 2 == 0) {
        double value = ((x * power(x, n/2)) * x);
        return value;

It is both syntactically (the brackets don't match) as semantically (deeper recursion, incorrect).

It should be replaced with:

if(n % 2 == 0) {
        double value = power(x*x, n/2);
        return value;

The reason is that:

x^(2*k) = (x^2)^k

Which is almost literally what is implemented in the code. Because we know n is even, there is a k = n/2, such that the above equation holds.

The same with the odd case:

else {
        double value = x * power(x*x, n/2);
        return value;

This because:

x^(2*k+1) = x*x^(2*k) (version of @rgettman)

With k = (n-1)/2, which can be further optimized to:

x^(2*k+1) = x*x^(2*k)=x*(x^2)^k (our version)

You can further optimize this as:

public static double power(double x, int n) {   
    if(n == 0) {
        return 1;
    }
    double xb = x*x;
    if((n&0x01) == 0x00) {
        return power(xb,n>>>0x01);
    } else {
        return x*power(xb,n>>>0x01);
    }
}

Or, you could transform the recursive aspect into a while algorithm (since it is mainly tail-recursion:

public static double power(double x, int n) {
    double s = 1.0d;
    while(n != 0) {
        if((n&0x01) != 0x00) {
            s *= x;
        }
        n >>>= 0x01;
        x *= x;
    }
    return s;
}

Performance:

three different versions were implemented. This jdoodle shows benchmark tests. With:

• power1 the version of @rgettman;
• power2 the proposed recursive version in this answer; and
• power3 the non-recursion version.

In case one sets L to 10'000'000 (thus calculating all power from 0 up to L), one run results in:

           L = 10M           L=20M
power1: 1s 630 018 699     3s 276 492 791
power2: 1s 396 461 817     2s 944 427 704
power3: 0s 803 645 986     2s 453 738 241

Don't take the numbers after the comma very seriously. Although Java measures in nano-seconds, these numbers are extremely inaccurate and have more to do with side-events (like OS calls, cache-faults,...) than with the real program runtime.

Answer 2

You need to understand how recursion works internally. Logic is simple is to store the function calls and returned values in a stack. When the method termination condition is reached, pop out the values and return from method.

You need simply this:

public static double power(double x, int n) {   
    if(n == 0) {
        return 1;
    } else {
        double value = (x * power(x, (n-1)));
        return value;
    }
}

Answer 3

In your "even" case, you can calculate it with the recursive call, passing n/2 as you've done. But you need to multiply the result with itself to square it.

double value = power(x, n/2);
value *= value;
return value;

In your "odd" case, you can multiply x by the recursive call of the exponent minus 1.

double value = x * (power(x, n - 1));
return value;