递归：x的n次幂

50. Pow(x, n)

这个递归也非常有意思，同样是有点难以理解，我们求$x^n$其实可以递归成两种情况
x n = { ( x n 2 ) 2 n%2==0 x ∗ ( x n 2 ) 2 n%2==1 x^n=

xn={(x2n​)2x∗(x2n​)2​n%2==0n%2==1​
转化成递归函数的形式就是
p o w ( x , n ) = { p o w ( x , n / / 2 ) 2 n%2==0 x ∗ p o w ( x , n / / 2 ) 2 n%2==1 pow(x,n)=

{pow(x,n//2)2n\%2==0x∗pow(x,n//2)2n\%2==1" role="presentation" style="position: relative;">{pow(x,n//2)2x∗pow(x,n//2)2n\%2==0n\%2==1$$\{\begin{array}{ll}pow(x,n//2{)}^2& \text{n\%2==0}\\ x\ast pow(x,n//2{)}^2& \text{n\%2==1}\end{array}$$

pow(x,n)={pow(x,n//2)2x∗pow(x,n//2)2​n%2==0n%2==1​

你问我怎么求解$pow(x,n//2)$我也不知道，反正就是根据这个递归公式不断递归就可以求解出来了。我也不知道怎么求$pow(x,n)$，但是如果我求出了$pow(x,n//2)$我就可以求出$pow(x,n)$了，如和求求解$pow(x,n//2)$呢？我只要求解出$pow(x,n//4)$就可以了，这样问题最后就会缩减到n=1也就是停止条件上，然后递归再进行返回，我们操作这个返回结果即可。

class Solution:
    def myPow(self, x: float, n: int) -> float:

        def dfs(x,n):
            if n == 0:
                return 1
            y = dfs(x, n//2)
            if n % 2 == 0:
                return y * y
            else:
                return x * y * y
        
        if n < 0:
            x = 1 / x
            n = -n

        r = dfs(x,n)
        return r
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18