爲什麼遞歸函數前往雙向鏈表不起作用？

我剛剛完成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

爲什麼遞歸函數前往雙向鏈表不起作用？

回答

相關問題