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?
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.
dc_power is linear (this is notated explicitly in the webpage linked from the question) because it does two recursive calls instead of one. There is no wonder that it is not faster.@functools.lru_cache for that.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))
