为什么递归函数前往双向链表不起作用？

我刚刚完成edX入门课程MIT 6.00.1x的新手;以下是关于该课程期末考试的问题（现已结束，所以我可以寻求帮助）。让为什么递归函数前往双向链表不起作用？

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

被用来创建一个双向链表。假设node是出现在双向链表中的类DLLNode的实例。然后node.getBefore()返回列表中的前一个node，除了它返回None，如果node位于列表的前面并且没有前导。

我已经写了递归功能

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())

，我想在一个双向链表返回的第一个节点，给出的参数列表中的一个已知的节点nodeInList。

我的问题：firstInList到达正确的第一个节点，通过无论所使用的特定nodeInList其印刷的第一个节点的货物证明。但是无论何时nodeInList是而不是链接列表中的第一个节点，返回值firstInList(node)原来是None而不是所需的第一个节点。这一结论是基于以下几点：如果，例如，该列表的第一个节点node1有货1，随后是node2与货物2，然后firstInList(node2) == None计算为True但firstInList(node2) == node1评估为False。呼叫firstInList(node2).getCargo()将返回一个错误信息

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

另一个基准是firstInList(node1) == node1评估为True;至少，这是我所期望的。

这表明firstnode发现没有以我想象的方式返回递归调用链。 任何人都可以解释为什么？

（请不要建议我使用迭代而不是递归。我知道该怎么做。我想了解的Python 2.7的行为的代码写的。）

来源

2015-03-12 Greg Grunberg

[递归函数调用中返回语句的原因]的可能重复（http://programmers.stackexchange.com/questions/201765/reason-for-return-statement-in-recursive-function-call） – 2015-03-12 08:20:45

好的话看起来你并不是递归的结果，所以函数会在所有情况下退化，但简单地返回默认的未初始化值。

最后一行应该是：

return firstInList(nodeInList.getBefore())

来源

2015-03-12 05:58:28

您的答案是我考虑的事情，但它并没有真正回答所问的问题。到达列表的“firstnode”是递归的基本情况，并且函数_does_到达该基本情况，如通过打印出“firstnode.cargo”的正确值来证明的那样。那么_why_不是一个简单的'return firstnode'指令就足够了吗？ – 2015-03-12 07:19:35

@GregGrunberg因为'return'只从当前函数调用（堆栈帧）中返回。如果你不使用返回值，那么它将被丢弃。但是调用它的函数**必须返回一些东西。如果你没有明确说出什么，它只会根据语言（平台）返回一些值。它在python中返回'None'，它在C \ C++中返回一些垃圾，或者它只是不会用更严格的规则编译。您还可以阅读以下文章 - http://programmers.stackexchange.com/questions/201765/reason-for-return-statement-in-recursive-function-call。 – 2015-03-12 08:19:29

请在代码中添加更改，以供将来参考，因为您的回答是正确的，但没有说明如何解决它 – holroy 2015-03-13 23:25:47

非常感谢弥敦道Tuggy。起初我误解你在说什么，但事实上你是对的。

我firstInList功能完美地工作，一旦我改变了最后一行

firstInList(nodeInList.getBefore())

阅读

return firstInList(nodeInList.getBefore()) .

鉴于小时，我已经花了担心这个荒谬的数字，我认为这是一个我不可能在将来做出错误类型。或者如果我这样做，我将能够自己发现问题。

来源

2015-03-13 06:21:58

为什么递归函数前往双向链表不起作用？

回答

相关问题