50. Pow(x, n)

不难但是很经典的题目。迭代法需要在二进制找规律；递归则比较容易看出来。（2^n为步长，从右向左观察）

// 找规律，迭代法
func solve(x float64, n int) float64 {
    var result float64 = 1
    for ;n>0;x*=x{
        if n%2 == 1{
            result *= x
        }
        n = n>>1
    }
    return result
}

// 递归法
// func solve(x float64, n int) float64{
//     if n == 0{
//         return 1
//     }
//     result := solve(x, n>>1)
//     if n % 2 == 1{
//         return result*result*x
//     }else{
//         return result*result
//     }
// }

func myPow(x float64, n int) float64 {

    if n>=0{
        return solve(x, n)
    }else{
        return 1/solve(x, -n)
    }

}