Maximum recursion depth exceeded in python
<p>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.</p>

<pre><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
</code></pre>

<p>You should use <code>n // 2</code> instead of <code>n / 2</code>:</p>

<pre><code>&gt;&gt;&gt; 5 // 2
2
&gt;&gt;&gt; 5 / 2
2.5
</code></pre>

<p>(At least in python3)</p>

<p>The problem is that once you end up with floats it takes quite a while before you end up at <code>0</code> by dividing by <code>2</code>:</p>

<pre><code>&gt;&gt;&gt; from itertools import count
&gt;&gt;&gt; n = 5
&gt;&gt;&gt; for i in count():
...     n /= 2
...     if n == 0:
...         break
... 
&gt;&gt;&gt; i
1076
</code></pre>

<p>So as you can see you would need more than 1000 recursive calls to reach <code>0</code> from <code>5</code>, and that's above the default recursion limit. Besides: that algorithm is meant to be run with integer numbers.</p>

<hr>

<p>This said I'd write that function as something like:</p>

<pre><code>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
</code></pre>

<p>Which produces:</p>

<pre><code>&gt;&gt;&gt; fast_power(2, 7)
128
&gt;&gt;&gt; fast_power(3, 7)
2187
&gt;&gt;&gt; fast_power(13, 793)
22755080661651301134628922146701289018723006552429644877562239367125245900453849234455323305726135714456994505688015462580473825073733493280791059868764599730367896428134533515091867511617127882942739592792838327544860344501784014930389049910558877662640122357152582905314163703803827192606896583114428235695115603966134132126414026659477774724471137498587452807465366378927445362356200526278861707511302663034996964296170951925219431414726359869227380059895627848341129113432175217372073248096983111394024987891966713095153672274972773169033889294808595643958156933979639791684384157282173718024930353085371267915606772545626201802945545406048262062221518066352534122215300640672237064641040065334712571485001684857748001990405649808379706945473443683240715198330842716984731885709953720968428395490414067791229792734370523603401019458798402338043728152982948501103056283713360751853
</code></pre>

python function recursion