I am trying to make power function by recursion. But I got run time error like Maximum recursion depth exceeded. I will appreciate any help!! Here is my code.
def fast_power(a,n):
if(n==0):
return 1
else:
if(n%2==0):
return fast_power(fast_power(a,n/2),2)
else:
return fast_power(fast_power(a,n/2),2)*a
You should use n // 2 instead of n / 2:
>>> 5 // 2
2
>>> 5 / 2
2.5
(At least in python3)
The problem is that once you end up with floats it takes quite a while before you end up at 0 by dividing by 2:
>>> from itertools import count
>>> n = 5
>>> for i in count():
... n /= 2
... if n == 0:
... break
...
>>> i
1076
So as you can see you would need more than 1000 recursive calls to reach 0 from 5, and that's above the default recursion limit. Besides: that algorithm is meant to be run with integer numbers.
This said I'd write that function as something like:
def fast_power(a, n):
if n == 0:
return 1
tmp = fast_power(a, n//2)
tmp *= tmp
return a*tmp if n%2 else tmp
Which produces:
>>> fast_power(2, 7)
128
>>> fast_power(3, 7)
2187
>>> fast_power(13, 793)
22755080661651301134628922146701289018723006552429644877562239367125245900453849234455323305726135714456994505688015462580473825073733493280791059868764599730367896428134533515091867511617127882942739592792838327544860344501784014930389049910558877662640122357152582905314163703803827192606896583114428235695115603966134132126414026659477774724471137498587452807465366378927445362356200526278861707511302663034996964296170951925219431414726359869227380059895627848341129113432175217372073248096983111394024987891966713095153672274972773169033889294808595643958156933979639791684384157282173718024930353085371267915606772545626201802945545406048262062221518066352534122215300640672237064641040065334712571485001684857748001990405649808379706945473443683240715198330842716984731885709953720968428395490414067791229792734370523603401019458798402338043728152982948501103056283713360751853
I believe @Bakuriu's explanation of the problem is incomplete. Not his reimplementation, but his explanation of your bug(s). You might convince yourself of this by replacing / with // in your original code and try:
fast_power(2, 2)
it still exceeds the stack. Try expanding the stack ten fold:
sys.setrecursionlimit(10000)
it still exceeds the stack. The reason is you also have an infinte loop:
if (n % 2 == 0):
return fast_power(..., 2)
Since 2 % 2 == 0, this simply keeps recursing forever. Adding another base case:
if n == 2:
return a * a
fixes the problem. A complete solution:
def fast_power(a, n):
if n == 0:
return 1
# if n == 1:
# return a
if n == 2:
return a * a
if n % 2 == 0:
return fast_power(fast_power(a, n // 2), 2)
return a * fast_power(fast_power(a, n // 2), 2)
x^2n == (x^n)^2. However the^2could be replaced by a multiplication:x = fast_power(a, n//2); return x*x/to divide, as shown in my answer. The algorithm should only use integers and thus it should use integer division//and not/.