实现 pow(x, n) ，即计算 x 的 n 次幂函数。

示例 1:

输入: 2.00000, 10
输出: 1024.00000

示例 2:

输入: 2.10000, 3
输出: 9.26100

示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

• -100.0 < x < 100.0
• n 是 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1] 。

思路：

分奇数偶数情况，递归求解。暂且不考虑n为负情况：

n为偶数   x^n=x^(n/2) * x^(n/2)

n为奇数   x^n=x^(n/2) * x^(n/2) * x

public double myPow(double x, int n) {
		if (n >= 0)
			return helper(x, n);
		else
			return 1 / helper(x, -n);
	}
	// 求x的n次 n为正数
	private double helper(double x, int n) {
		if (n == 0)
			return 1;
		double halfRes = helper(x, n / 2);
		if (n % 2==0) { //偶数
			return halfRes*halfRes;
		}else {  //奇数个的话还得乘以一个
			return halfRes*halfRes*x;
		}
	}