python - 递归求幂

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)，有没有一种方法可以计算它而不必递归地进行？