Search code examples
pythonrecursiontail-recursion

If python don't have tail recursion 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.