Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

If python don't have tail recurssion in it, then why my code on leetcode is working differently for diffirent 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:

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

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.

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading