使用递归查找能力

Question

在Python 3中

def power(base,exponent):
    if exponent == 1:
        return base
    return base * power(base, exponent - 1)

我没有考虑过极端情况（指数<= 0）

为什么我们不使用上面编写的代码代替使用分而治之技术计算的代码，该代码看起来更简单易懂？这段代码效率是否低下？

Answer 1

以下是使用代码计算 2^8 所采取的步骤：

\n\n

power(2,8)=\n2*power(2,7)=\n2*2*power(2,6)=\n2*2*2*power(2,5)=\n2*2*2*2*power(2,4)=\n2*2*2*2*2*power(2,3)=\n2*2*2*2*2*2*power(2,2)=\n2*2*2*2*2*2*2*power(2,1)=\n

\n\n

以下是通过分治法计算 2^8 所采取的步骤：

\n\n

power(2,8)=\npower(2,4)**2=\npower(2,2)**2**2=\npower(2,1)**2**2**2=\n

\n\n

正如您所看到的，您的方法需要 O(n) 步骤，而分而治之需要 O(lg(n)) 步骤，这要快得多。

\n\n

如果您关心速度，那么使用递归来解决此类问题从来都不是一个好主意，因为正如您所看到的，迭代方法（函数式语言中的尾递归）通常要快得多，在本示例中，它的速度是基准测试中看到的速度的两倍，至于分而治之的方法，你应该始终使用它，除非你使用的幂小于~22。

\n\n

以下是一些基准：

\n\n

代码：

\n\n

def r_power(base, exponent):  # recursive credits to OP\n    if exponent == 1:\n        return base\n    return base * r_power(base, exponent - 1)\n\n\ndef lindc_power(x, y):  # linear divide and conquer, credits to Smitha Dinesh Semwal\n    if y == 0:\n        return 1\n    elif int(y % 2) == 0:\n        return lindc_power(x, int(y / 2)) * lindc_power(x, int(y / 2))\n    else:\n        return x * lindc_power(x, int(y / 2)) * lindc_power(x, int(y / 2))\n\n\ndef lgdc_power(x, y):  # logarithmic divide and conquer\n    if y == 0:\n        return 1\n    elif int(y % 2) == 0:\n        return lgdc_power(x, int(y / 2)) ** 2\n    else:\n        return x * lgdc_power(x, int(y / 2)) ** 2\n\n\ndef i_power(base, exponent):  # iterative, credits to Yugandhar Chaudhari\n    acc = 1\n    while True:\n        if exponent == 0:\n            return acc\n        base, exponent, acc = base, exponent - 1, acc * base\n

\n\n

结果：

\n\n

|---------------------------------------------------------------------|\n| base | power   | recursive | iterative | linear dc | logarithmic dc |\n|---------------------------------------------------------------------|\n| 2    | 10      | 1.27 \xc2\xb5s   | 746 ns    | 8.99 \xc2\xb5s   | 2.33 \xc2\xb5s        |\n| 2    | 22      | 2.96 \xc2\xb5s   | 1.58 \xc2\xb5s   | 18.6 \xc2\xb5s   | 2.95 \xc2\xb5s        |\n| 2    | 100     | 15.1 \xc2\xb5s   | 8.31 \xc2\xb5s   | 75.3 \xc2\xb5s   | 4.14 \xc2\xb5s        |\n| 2    | 500     | 96.7 \xc2\xb5s   | 48.9 \xc2\xb5s   | 312 \xc2\xb5s    | 5.69 \xc2\xb5s        |\n| 2    | 1000    | 424 \xc2\xb5s    | 178 \xc2\xb5s    | 1.3 ms    | 6.58 \xc2\xb5s        |\n| 2    | 1500    | 201 \xc2\xb5s    | 108 \xc2\xb5s    | 620 \xc2\xb5s    | 7.89 \xc2\xb5s        |\n| 2    | 2000    | 435 \xc2\xb5s    | 242 \xc2\xb5s    | 1.23 ms   | 8.15 \xc2\xb5s        |\n| 2    | 3000    | error     | 409 \xc2\xb5s    | 2.49 ms   | 10.3 \xc2\xb5s        |\n| 2    | 6000    | error     | 1.13 ms   | 5.01 ms   | 17.6 \xc2\xb5s        |\n| 2    | 10000   | error     | 2.64 ms   | 9.84 ms   | 25.2 \xc2\xb5s        |\n| 2    | 20000   | error     | 8.74 ms   | 19.9 ms   | 45.7 \xc2\xb5s        |\n| 2    | 100000  | error     | 161 ms    | 82.4 ms   | 249 \xc2\xb5s         |\n| 2    | 200000  | error     | 626 ms    | 159 ms    | 532 \xc2\xb5s         |\n| 2    | 1000000 | error     | 15 s      | 651 ms    | 3.23 ms        |\n|---------------------------------------------------------------------|\n\n

\n\n

我的最大递归深度是 3000。

\n