使用递归求幂 [英] Finding Power Using Recursion

问题描述

在 Python 3 中

In Python 3

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

我没有考虑极端情况(指数 <= 0)

I haven't considered corner cases ( exponent <= 0)

为什么我们不使用上面编写的代码代替使用 分治法，这段代码看起来更简单易懂吗?无论如何，这段代码的效率会降低吗?

Why don't we use the above-written code in-place of code computed using Divide and Conquer Technique, this code looks more simple and easy to understand? Is this code less efficient by any means?

推荐答案

这些是使用代码计算 2^8 所采取的步骤:

These are the steps taken for calculating 2^8 with your code:

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

这些是使用分治法计算 2^8 所采取的步骤:

These are the steps taken for calculating 2^8 with divide and conquer:

power(2,8)=
power(2,4)**2=
power(2,2)**2**2=
power(2,1)**2**2**2=

如您所见，您的方法需要 O(n) 步，而分治法需要 O(lg(n)) 步，速度明显更快.

As you can see your method takes O(n) steps while divide and conquer takes O(lg(n)) steps which is significantly faster.

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

Using recursion for such problems is never a good idea if you are concerned with speed since as you can see iterative approach(tail recursion in functional languages) is usually much faster, in this example it's twice as fast as you can see in the benchmarks, as for the divide and conquer approach, you should always use that unless you are working with powers of less than ~22.

以下是一些基准:

代码:

def r_power(base, exponent):  # recursive credits to OP
    if exponent == 1:
        return base
    return base * r_power(base, exponent - 1)


def lindc_power(x, y):  # linear divide and conquer, credits to Smitha Dinesh Semwal
    if y == 0:
        return 1
    elif int(y % 2) == 0:
        return lindc_power(x, int(y / 2)) * lindc_power(x, int(y / 2))
    else:
        return x * lindc_power(x, int(y / 2)) * lindc_power(x, int(y / 2))


def lgdc_power(x, y):  # logarithmic divide and conquer
    if y == 0:
        return 1
    elif int(y % 2) == 0:
        return lgdc_power(x, int(y / 2)) ** 2
    else:
        return x * lgdc_power(x, int(y / 2)) ** 2


def i_power(base, exponent):  # iterative, credits to Yugandhar Chaudhari
    acc = 1
    while True:
        if exponent == 0:
            return acc
        base, exponent, acc = base, exponent - 1, acc * base

结果:

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

我的最大递归深度是 3000.

My maximum recursion depth is 3000.

这篇关于使用递归求幂的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！