Power function with recursion - java

Question

Here's the working recursive power function alternative to Math.Pow class:

public class Powers {
    public static long pow(long x, long p) {
        if (p == 0) {
            return 1;
        }
        if (p % 2 == 0) {
            long a = pow(x, (p / 2));
            return a * a; //This line
        } else {
            long a = pow(x, ((p - 1) / 2));
            return x * a * a; //This line
        }
    }
}

If I try to be clever and use as much recursion as possible by changing the lines mentioned above to return pow(a, 2) and return x * pow(a, 2), I get a stack overflow error. I get that it should cause considerably more calls to pow, but I don't think it should loop like it appears to. Can anyone explain me through this? Thanks

Answer 1

Doing this you will get the following sequence of calls:

pow(a, 2) -> pow(a, 1) -> pow(a, 0) -> pow(1, 2) -> pow(1, 1) -> pow(1, 0) -> pow(1, 2) -> ...

Answer 2

You should either debug this with some IDE, or simply add some expression in the beginning of the method:

public static long pow(long x, long p) {
    System.out.println ("x = " + x + ", p = " + p);
    ...

Then, read the output, it will contain the sequence of calls of pow