If python don't have tail recursion in it, then why my code on leetcode is working differently for different 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
– Brian61354270, Commented Jul 16, 2023 at 18:25
Python has recursion but not tail recursion - stackoverflow.com/questions/33923/what-is-tail-recursion — rasjani
– rasjani, Commented Jul 16, 2023 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
– deceze ♦, Commented Jul 16, 2023 at 18:29
@rasjani Python has tail recursion if you write tail recursive code, it just might not optimise tail recursive code. — deceze
– deceze ♦, Commented Jul 16, 2023 at 18:31

Tom Karzes · Accepted Answer · 2023-07-16 18:31:11Z

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, 2023 at 18:31

Tom Karzes

24.3k3 gold badges28 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

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

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related