[每日一题]50.powx-n（递归）

1.感觉这是一道递归题。

主要就是分别对它的几种情况进行处理。
然后再就是每次都将数据分成两个部分进行pow( x*x, n//2)即可减少运算次数。时间复杂度是logN。

• 第一种情况: n是负数，那就在递归的时候传回 1/x 即可。
• 第二种情况: n是奇数，那就对它进行一次校正，传递pow( x, n-1)*x

powx-n.png

链接：
https://leetcode.com/problems/powx-n/

解题思路就是：递归呗。
这里有个特别好的解释递归的图。我列出来。
先就是执行递归（入栈），然后到达门限值的时候，一个个解出（出栈）。

递归.png

2.题解：

class Solution(object):
    def myPow(self, x, n):
        # 出栈
        if not n:
            return 1
        # 小于0时，返回1/x
        if n < 0:
            return 1/self.myPow(x, -n)
        # 奇数时，校正
        if n % 2:
            return self.myPow(x, n-1) * x
        self.myPow(x*x, n // 2)

3.完整代码

查看链接：
https://github.com/Wind0ranger/LeetcodeLearn/blob/master/6-Recursive/50-powx-n.py