CODEWITHSUNDEEP
pythondata-structuresrecursion
Greg Grunberg
Greg Grunberg

Reputation: 121

Why does recursive function for travelling to front of doubly linked list not work?

I am a novice who has just finished edX's introductory course MIT 6.00.1x; the following is related to a problem on that course's final exam (now concluded, so I can seek help). Let 

def class DLLNode(object):
    def __init__(self, name):
        self.cargo = cargo
        self.before = None
        self.after = None
    def setBefore(self, before):  self.before = before
    def setAfter(self, after):    self.after = after
    def getBefore(self):          return self.before
    def getAfter(self):           return self.after
    def getCargo(self):           return self.cargo

be used to create a doubly linked list. Suppose node is an instance of class DLLNode that appears in a doubly linked list. Then node.getBefore() returns that node's immediate predecessor in the list, except that it returns None if node is at the front of the list and so has no predecessor.

I have written a recursive function

def firstInList(nodeInList):
    """ Prints out the cargo carried by the first node in that doubly linked list
    of which nodeInList is a part.  Returns that first node. """

    if nodeInList.getBefore() == None:
        firstnode = nodeInList
        print firstnode.getCargo()
        return firstnode
    # nodeInList.getBefore() is not None, so nodeInList has an immediate predecessor 
    # on which firstInList can be be called.
    firstInList(nodeInList.getBefore())

that I wish to return the first node in a doubly linked list, given as argument a known node nodeInList in the list.

My problem: firstInList arrives at the correct first node, as evidenced by its printing the first node's cargo regardless of the specific nodeInList used. But whenever nodeInList is not the first node in the linked list, the return value of firstInList(node) turns out to be None rather than the desired first node. This conclusion is based on the following: If, for example, the list's first node node1 has cargo 1 and is followed by node2 with cargo 2, then firstInList(node2) == None evaluates as True but firstInList(node2) == node1 evaluates as False. A call firstInList(node2).getCargo() will return an error message

Attribute Error: 'NoneType' object has no attribute 'getCargo'

Another datum is that firstInList(node1) == node1 evaluates as True; that, at least, is as I would expect.

This suggests the firstnode found is not being returned back up the chain of recursive calls in the way I have imagined. Can anyone explain why?

(Please do not suggest that I use iteration instead of recursion. I know how to do that. I am trying to understand Python 2.7's behavior for the code as written.)

Upvotes: 2

Views: 211

Answers (2)

Nathan Tuggy
Nathan Tuggy

Reputation: 2244

Well, it would appear that you're not returning the result of the recursion, so the function will in all cases but the degenerate simply return the default uninitialized value.

The last line should be:

return firstInList(nodeInList.getBefore())

Upvotes: 3

Greg Grunberg
Greg Grunberg

Reputation: 121

Many thanks to Nathan Tuggy. At first I misunderstood what you were saying, but in fact you were correct.

My firstInList function worked perfectly once I changed the last line

firstInList(nodeInList.getBefore())

to read

return firstInList(nodeInList.getBefore()) .

Given the ridiculous number of hours I've spent worrying about this, I think this is a type of mistake I'm not likely to make in the future. Or if I do, I'll be able to discover the problem myself.

Upvotes: 0

Related Questions