写在前面
年前嘛，就是各种涣散的状态。在拖完地板之后，想想还是补上今天的题解吧~ 感谢小佳扬推荐的题目，默默的复习了一把递归~
第一题
50. Pow(x, n) 难度：中等
实现 pow(x, n)，即计算 x 的 n 次幂函数。
我的解题代码：
class Solution:
def myPow(self, x, n):
“””
:type x: float
:type n: int
:rtype: float
“””
if not n:
return 1
if n < 0 :
return 1 / self.myPow(x, -n)
if n % 2:
return x * self.myPow(x, n-1)
return self.myPow(x*x, n/2)
参考了部分评论区的题解。效率上还是可以的，复杂度在 N(logn) 左右。
我的解题思路：一开始的时候小佳扬说是坑，我还在想不就是循环么。后来她说要考虑怎么降低复杂度，否则会超时，就开始认真的思考了。
因为是 n 次幂，如果直接循环，复杂度就是 O(n) 了。
n 次幂可以拆解为 n /2n2 的方式。
考虑 n 为偶数和奇数的情况，判断余数后进行计算即可。
每次拆解 n /2，最后最小的单位应该为 x *x。
因为每一轮都为前一轮的解的 2 次方，所以用递归。
总结：递归还是比较绕的，前提是要找到每一次循环的出口，否则极容易变成死循环。马上放假了~ 统计学 + 算法 + 数据结构还是会常伴左右的~ 最近还加上了托福的单词，因为受到了单词量统计的刺激，我居然现在知晓的单词量只有 3k 了，要抓紧背起来了~
自律使我快乐~