Why this recursive function never terminates?


  • 0
    N

    The code below is used to connect nodes in a list in a way that each node's next attribute will point to the following node in the list, but the function never terminates. What's wrong with my code?

    def connect_level(alist):
        def aux(h, t):
            if len(t) == 0:
                h.next = None
                return
            else:
                h, t = alist[0], alist[1:]
                h.next = t[0]
                aux(h, list(t[1:]))
        if len(alist) == 0:
            return
        else:
            h, t = alist[0], alist[1:]
            aux(h, t)
    
    # this caused an error
    connect_level([TreeNode(1), TreeNode(2), TreeNode(3)])

  • 0
    S

    Can you add some comments explaining what's supposed to be happening? I don't use python, but I can see that when aux calls itself h never changes. How does this relate to the problem of connecting nodes in a tree?


  • 0
    N

    My solution is to solve the problem level by level, and what this function does is that given a list of nodes in the same level, connect each node to its right neighbor. The aux is a recursive function, which accepts two parameters, head( a single node) and tail (rest part of the list). The terminate condition for the recursion is when the tail is empty. The second parameter's size is reducing by one each time you make a recursive call.


  • 0
    S

    Ah, ok. That method violates the problem spec by using log(n) space rather than constant space, but that won't stop it from connecting the nodes.

    I actually meant add comments in the code, but I guess just saying "comments" was vague. Oops.

    I still don't understand what the aux is for, how how it's meant to work. If I were going to connect nodes from a list I would do something like this (sorry if it's not valid python):

    def connect_level(alist):
      for i in range( 0, alist.length-2 ):
        alist[i].next = alist[i+1]

    Note that setting alist[n-1].next = None is unnecessary because all of the next pointers start out as None.


  • 0
    N

    Yes, that's a much simpler implementation. :-) I guess I just want to practice how to write recursive function in Python.


  • 0
    S

    It never terminates because in the aux function, the else block sets both h and t from alist.

    Every time it gets to that block it recurses with h=alist[0], t=alist[2:].

    Any time aux is called with alist.length>2, it will infinite loop.

    For the condition len(t)==0 to be met, it would have to recurse with h and t set from the previous h and t rather than from alist.


Log in to reply
 

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