Finding Power Using Recursion

Question

In Python 3

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

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?

Answer 1

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)=

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=

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

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.

Here are some benchmarks:

The codes:

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

The results:

|---------------------------------------------------------------------|
| 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        |
|---------------------------------------------------------------------|

My maximum recursion depth is 3000.