递归求幂

Question

我想写一个递归计算指数的小程序，我有点卡住了。这是一项家庭作业，我们被要求有一个基本案例，当指数是一个奇数，当指数是偶数时。到目前为止，我有这个：

def quick_power(x,n): 
    if n == 0: 
     return 1 
    elif n % 2 != 0: 
     return x * quick_power(x, n-1) 
    elif n % 2 == 0: 
     return quick_power(quick_power(x, n//2), 2) 

而且我知道n％2 == 0的行不是它应该是。任何帮助表示赞赏。谢谢。

Answer 1

假设我们正在评估quick_power(1234, 2)。评价是这样的：

1. quick_power(1234, 2)
2. quick_power(quick_power(1234, 1), 2)
3. quick_power(1234 * quick_power(1234, 0), 2)
4. quick_power(1234 * 1, 2)
5. quick_power(1234, 2)

...你可以看到，它最终开始评估回到了起点，所以你最终得到无限递归。在没有给你解决方案的情况下，我建议你思考一下：如果我们有一个常量指数（这里是2），你有没有一种方法可以计算出来，而不必递归呢？

Answer 2

def quick_power(x,n) 

if n == 0: 
    return 1 
elif n % 2 == 0: 
    return quick_power(x * x, n/2) 
else: 
    return x * quick_power(x * x, (n - 1)/2) 

Answer 3

扩展在什么上面：

递归算法递归情况下ANS基地例（其中返回一个明确的结果，而不是另一种递归的），你可能知道......

对于在这种情况下，您涵盖了基本情况n = 0和n = 1。但是从@ icktoofay的回复中，还有另一个基本案例，n = 2。

所以，你的代码可以写成：

def quick_power(x,n): 
    if n == 0: 
     return 1 
    elif n == 1: 
     return x 
    elif n == 2: 
     return x * x 
    elif n % 2 != 0: 
     return x * quick_power(x, n-1) 
    elif n % 2 == 0: 
     return quick_power(x,n//2) * quick_power(x,n//2) 

最后一行应该是通过减少递归的最大深度（到log2（n）的递归），顺便更有效。