How does your recursion work? (Call stack exceeded)


  • 0
    D

    Here is my code (tried c# and JS, this is JS):

    var isPalindrome = function(head) {
        if(head === null)
            return true;
        var listLength = CountList(head)/2;
        var isPalindrome = PalindromeTest(head, 0);
        if (isPalindrome === null)
            return true;
        return false;
    }
    
    function CountList(head)
    {
        var count = 0;
        while(head !== null)
        {
            count++;
            head = head.next;
        }
        return count;
    }
    
    var listLength;
    function PalindromeTest(head, step)
    {
        if (head === null)
            return new ListNode(0);
        var rightHead;
        if (step === listLength)
            return head.next;
        else
            rightHead = PalindromeTest(head.next, step+1);
        if (rightHead === null)
            return new ListNode(0);
        if (head.val === rightHead.val)
            return rightHead.next;
        else
            return new ListNode(0);
    }
    

    It works until it hits the unit test with 50 000 members. The recursion should be called 25 000 times and it crashes at step 13760.
    For regular sizes this should be linear time, and i think it should work..

    The recursion basically goes down to length/2, then starts returning the next members to the corresponding previous ones. It will eventually hit null when it gets to the last member, or it will return an 0 List node if the list is not a palindrome.


  • 0
    S

    Hi,

    I guess it implicitly forbids the recursion approach by setting up the time limit or memory limit. Palindrome doesn't require to remember previous comparisons ( as long as it matched). This means that a stack-like implementation may be unnecessary. Though stack is a very natural way to think. I agree with your explanation, too.

    So double iterators (one in front and one in back) on the data should be enough to work. Hope it helps.


  • 0

    @dbrunovic Please try again, I have increased the stack size limit to allow recursion version to pass the judge.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.