pythonrecursiontail-recursion

# If python don't have tail recurssion in it, then why my code on leetcode is working differently for different recursions?

As per the link tail recursion is not present in python. I was working on leetcode problem where two inputs are given, number and its power. The power can be negative also. I need to find out exponent using recursion.

This was my code which was not getting accepted:

``````class Solution(object):
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
def po(x,n):
if n ==1:
return x
if n== 2:
return x * x

if n % 2==0:
return po(x * x, n//2)
else:
return x * po(x * x,(n-1)//2)

p = po(x,abs(n))

if n < 0:
return float(1)/p
else:
return p
``````

For the above code I received error:

``````RuntimeError: maximum recursion depth exceeded
return po(x * x, n//2)
Line 15 in po (Solution.py)
return po(x * x, n//2)
Line 15 in po (Solution.py)
.
.
.
.
``````

But for this code, it worked properly:

``````class Solution(object):
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
def po(x,n):
if n ==0:
return 1
if n < 0:
return 1.0/po(x,-1*n)

if n % 2==0:
return po(x * x, n//2)
else:
return x * po(x * x,(n-1) // 2)

return po(x,n)
``````

Solution

• Tail recursion isn't the issue.

In the original code, if `n` is `0`, it will just keep recursing without end, until it reaches the maximum recursion limit. It goes past the checks for `1` and `2`, and then, since `0` is even, it does `return po(x * x, n//2)`. Since `n//2` is also `0`, it never ends. You just need to add a check for `n` equal to `0`.