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

Question

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)

FYI, your `po` function isn't tail recursive to begin with, so whether or not Python includes optimizations for tail recursion is irrelevant. — Brian61354270, Jul 16 '23 at 18:25
Python has recursion but not tail recursion - https://stackoverflow.com/questions/33923/what-is-tail-recursion — rasjani, Jul 16 '23 at 18:28
Since the two codes a fairly different, in the first case you probably simply have an infinite recursion because of a missing base case, or at least *too much* recursion, which you don't have in the other case…!? — deceze, Jul 16 '23 at 18:29
@rasjani Python has tail recursion if you write tail recursive code, it just might not *optimise* tail recursive code. — deceze, Jul 16 '23 at 18:31

score 1 · Accepted Answer · answered Jul 16 '23 at 18:31

1

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.

answered Jul 16 '23 at 18:31

Tom Karzes

22,815
2
22
41

ops yes!! thank you! – Noobie Jul 16 '23 at 18:58

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

1 Answers1