CODEWITHSUNDEEP
pythonrecursion
PyM
PyM

Reputation: 63

Finding Power Using Recursion

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?

Upvotes: 5

Views: 1645

Answers (2)

yukashima huksay
yukashima huksay

Reputation: 6238

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.

Upvotes: 4

Yugandhar Chaudhari
Yugandhar Chaudhari

Reputation: 3964

Yes this could be less efficient if it is not tail recursive. Recursion creates stack frames for a too large number you can go out of memory. Right way would be expressing it using tail recursion. You just need to use a variable to store the result acc here it will evaluate the result in a variable instead of making recursive function calls 

def power2(base,exponent,acc):
    if exponent == 0:
        return acc
    return power2(base,exponent-1,acc*base)

print(power2(10,2,1)) #start acc from 1 initially

But python is not tail optimized so this is the way to use tail optimization here 

def power2(base,exponent,acc):
    while True:
        if exponent == 0:
            return acc
        base,exponent,acc = base,exponent-1,acc*base

print(power2(10,100,1))

Upvotes: 0

Related Questions