Reducing recursive calls on pow recursion method?

Had a question on how to reduce the amount of recursive calls on a self implementation of the pow method. Here is what I wrote, can this be improved?

public static int pow(double a, int b) {
    boolean isNegative = false;

    if(b < 0) {
        isNegative = true;
    }

    if(b == 开发者_JAVA百科0) {
        return 1;
    } 
    else if(b == 1) {
        return (isNegative ? (1 / b) : b);
    }

    return (isNegative ? ((1 / b) * (1 / b) * pow(a, b + 2)) : (b * b * pow(a, b - 2)));
}

---

Yes, it can be improved.

Think about it this way:

• If b is even, then a^b = a^(b/2) * a^(b/2).
• If b is odd, then a^b = a^(b/2) * a^(b/2) * a (where / means integer division).

Code (brain-compiled, coffee hasn't kicked in yet, etc.):

public static double pow(double a, int b) {
    if (b < 0)
        return 1 / pow(a, -b);
    if (b == 0)
        return 1;
    double halfPow = pow(a, b/2);
    if (b % 2 == 0)
        return halfPow * halfPow;
    else
        return halfPow * halfPow * a;
}

This gives you O(log b) recursive calls, as opposed to O(n) in your solution.

---

Have a look at memoization.

---

EDIT: Fundamentally, you've got three problems:

• The code doesn't work (as of the edit, it now completely ignores a)
• The code is too complicated
• The code is recursing more than you want it to

Trying to fix the third of these without fixing the first is pointless.

Your first port of call should be some unit tests. They will prove very quickly that your code is currently broken, and give you some confidence that when you've fixed it, you can then change it and know whether or not you've broken anything.

Then you should aim to simplify it. For example, you could easily start your method with:

if (b < 0)
{
    return 1 / pow(a, -b);
}

... then you don't need to worry about negative values of b any more.

Finally you can look at what you've got left and try to turn a recursive solution into an iterative solution.