【例5.4】若算法pow(x，n)用于计算xn（n为大于1的整数）。完成以下任务： 1.采用递归方法设计pow(x，n)算法。 2.问执行pow(x，5)发生几次递归调用？求pow(x,n)对应的算法复杂度是多少？使用Java代码解决

【例5.4】要设计一个递归方法来计算幂运算`pow(x, n)`，我们可以将大问题分解成小问题。当`n`是一个正整数时，可以将其表示为二进制形式，例如5等于101（二进制），这意味着我们可以在每次递归中将`x`平方并将指数减半，直到指数变成1。

**递归设计**：

public class Power {
    public static double pow(double x, int n) {
        if (n == 1) // 基本情况，n为1时直接返回x
            return x;
        else if (n % 2 == 0) { // 如果n偶数，先对半处理
            double halfResult = pow(x, n / 2); // 递归调用pow(x, n/2)
            return halfResult * halfResult; // 再平方
        } else { // 如果n奇数，先平方再处理剩余的一次
            double halfResult = pow(x, n / 2);
            return x * halfResult * halfResult; // 即 x * pow(x, n/2)^2
        }
    }
}

**递归调用次数**：
对于`pow(x, 5)`，因为5的二进制为101，所以会进行3次递归调用：第一次是`pow(x, 2)`，第二次是`pow(x, 1)`，第三次是原函数`pow(x, 1)`。

**时间复杂度**：
由于每次递归都将问题规模缩小一半，因此该算法的时间复杂度是O(log n)，这是由于每个递归层级的时间复杂度都是O(1)，总共需要log base 2 of n次。