题目描述：实现Pow(x, n), 计算x的n次幂。
    说明：

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

    思考：本方法考察点：1、如何减少计算复杂度(x = x x)；2、n为负数如何处理；
    *方法    ：分别存在递归和迭代两种方法；

    一、递归：

    1. class Solution{
    2. public:
    3.     double Pow(double x, int n){
    4.         if (n == 0)
    5.             return 1.0;
    6.             // n < 0
    7.         if (n < 0)
    8.            return 1. / Pow(x, -n);     
    9.         double half_pow = Pow(x, n/2);
    10.         // n为奇数：xn = xn/2 * xn/2 * x;
    11.         // n为偶数：xn = xn/2 * xn/2
    12.         if (n & 1)
    13.             return half_pow * half_pow * x;
    14.         return half_pow * half_pow;
    15.     }
    16. }

    二、迭代：

    class Solution{
public:
    double Pow(double x, int n){
    double answer = 1.0;
    if (n == 0)
        return answer;
    for(int i = n; i != 0; i /= 2){
        if (i & 1)
            answer *= x;
        x *= x;
    }
    return n > 0 ?  answer : 1 / answer;
}

    总结：本题考察，二分法减少运算量以及正负幂的处理。