50. Pow(x, n)

Implement pow(x, n), which calculates x raised to the power n (xn).

Example 1:

Input: 2.00000, 10
Output: 1024.00000
Example 2:

Input: 2.10000, 3
Output: 9.26100
Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

二分递归思想：最容易想到的是这个方法。注意一下幂次奇偶性。
不论我们返回时候如何，我们执行第一步，先设立Base Case:
if n == 0: return 1
完了以后，我们要对大问题进行拆分，也就是不断的对b的值折半
拆分：half = self.myPow(x, n // 2)
当拆分到了最小的问题，满足base case n == 0 的时候，我们则进行返回，返回时候有三种可能

Function的三种可能性：
当b为偶数的时候，比如 2 ^ 100，拆分的时候就变成 (2 ^ 50) (2 ^ 50)
当b为基数的时候，比如 2 ^ 25，拆分的时候就变成 (2 ^12) (2 ^ 12) * 2
当b为负数的时候，返回 1.0 / self.myPow(a, -b)

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if n < 0:
            return 1/self.tool( x , -n)
        return self.tool(x,n)

    def tool(self,x,n):
        if n == 0:
            return 1
        t = n // 2
        res = self.myPow(x , t)
        print(res)
        if n % 2 == 0:
            return res * res
        return res * res * x