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>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 <code>/</code> with <code>//</code> in your original code and try:</p>

<pre><code>fast_power(2, 2)
</code></pre>

<p>it still exceeds the stack.  Try expanding the stack ten fold:</p>

<pre><code>sys.setrecursionlimit(10000)
</code></pre>

<p>it still exceeds the stack. The reason is you also have an infinte loop:</p>

<pre><code>if (n % 2 == 0):
    return fast_power(..., 2)
</code></pre>

<p>Since 2 % 2 == 0, this simply keeps recursing forever.  Adding another base case:</p>

<pre><code>if n == 2:
    return a * a
</code></pre>

<p>fixes the problem.  A complete solution:</p>

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

python function recursion