递归求幂

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)。评价是这样的：

quick_power(1234, 2)
quick_power(quick_power(1234, 1), 2)
quick_power(1234 * quick_power(1234, 0), 2)
quick_power(1234 * 1, 2)
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

扩展上面的内容：

正如您可能知道的那样，递归算法具有递归情况和基本情况（返回确定结果而不是另一个递归）...

对于这种情况，您涵盖了基本情况 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) 递归）来提高效率。

递归求幂

Recursive Exponentiation

python

recursion

exponentiation