题目: Pow(x, n)

分析

递归法

Pow(x, n) 可以分为如下几种情况考虑：

当 n 为 0 的时候，$x^{0}=1$ ;

当 n 为 1 的时候，$x^{1}=x$ ;

当 n 为大于2的偶数的时候，$x^{n}=x^{\frac {n}{2}}*x^{\frac {n}{2}}$ ;

当 n 为奇数的时候，$x^{n}=x^{\frac {n-1}{2}}*x^{\frac {n-1}{2}}*x$；

当 n 小于 0 的时候，$x^{n}={\frac {1}{x^{-n}}}$，因为-2³¹转为正数2³¹的时候会出现数组越界，可以用 $x^{n}={\frac {1}{x^{-n-1}*x}}$ 来表示。

题解

public class Solution{
    public double solute(double x,int n){
        if (n == 0){
            return 1;
        }
        
        if (n < 0){
           return 1.0 / (pow(x,-n-1) * x);
        }
    
        if (n % 2 == 0){
            return solute(x, n / 2) * solute(x, n / 2);
        }
        
        if (n % 2 == 1){
            return solute(x, n / 2) * solute(x, n / 2) * x;
        }
    }
}