遞歸節點

我想在本課中瞭解如何讀取下面的函數printBackward。當我輸入printBackward(node1)並且我的輸出是3,2,1時，它是怎樣的呢？這是它應該做的。我只是不明白爲什麼。請參閱下面我如何理解它，並請學校我在那裏我看到它錯了...遞歸節點

class Node: 
    def __init__(self, cargo = None, next = None): # optional parameters. cargo and the link(next) are set to None. 
     self.cargo = cargo 
     self.next = next 

    def __str__(self): 
     return str(self.cargo) 


node1 = Node(1) 
node2 = Node(2) 
node3 = Node(3) 
node1.next = node2 
node2.next = node3 

# Exercise 
def printList(node): 

    print "[", 
    while node: 
     print node, 
     node = node.next 
     if node != None: 
      print ",", 
    print "]", 
    print 


def printBackward(list): 
    if list == None: return 
    head = list  
    tail = list.next 
    printBackward(tail) 
    print head,

所以我們可以說... printBackward(node1)首先，if list應該被忽略，因爲節點1包含到節點的引用，以便我們繼續前進到head = list這是node1。 tail = list.next我認爲它是node1.next = node2，所以tail = node2。然後我們到達printBackward(tail)這是node2。那時候會發生什麼？我們是否再一次這樣做？我看到這會上升到node3，那個時候會返回None。我們什麼時候去print head, ???我們在進入print head,之前進行遞歸調用？請教我，因爲我想了解在課程中給我的例子。謝謝！

來源

2011-10-12 G.G

對於在調用printBackward(node3)時發生的一切，您是正確的。發生什麼事是每次你進行遞歸調用printBackward()時，你都會深入調用堆棧。在遞歸停止調用printBackward()之前，最終的print實際上並沒有被調用，然後展開。每當它返回，那麼print被調用，這就是爲什麼你得到倒序。 print發生在調用堆棧的展開過程中。當你到達node3，tail變成None，並且下一個printBackwards()的呼叫是馬上返回，並開始打印。

printBackward(node1) 
    printBackward(node2) 
     printBackward(node3) 
      printBackward(None) 
     print node3 
    print node2 
print node1

也是一個小紙條，你遮蔽了幾個內置Python名（list和next）。

來源

2011-10-12 00:48:46 jdi

所以當我們調用printBackward（node3）時，如果列表THEN等於None，對吧？那麼它不會沒有任何回報？我可能在看這個明顯的例子，但是我沒有看到這個代碼是如何設置的，以便開始向後打印，因爲我們已經到達了一個包含None的節點3，這看起來是程序的結尾？ –

注意到您實際上對這些代碼的返回值感興趣。你只需調用printBackward（）。當它返回時，它僅從該特定呼叫返回。如果它結束了，它也會返回None。無論哪種方式，該調用每次都返回None，只是當它離開函數 – jdi

時，我遇到的問題是，它正在存儲node1和node2，因爲我們碰到了node3並將其打印出來。所以它在沒有印刷的情況下建立起來，直到我們到達一個沒有任何進一步的列表爲止，因此它印刷了建立在這一點上的內容？它是如何知道以3,2,1而不是1,2,3開始的？ –

遞歸調用函數本身。所以讓我們看看printBackward函數的調用順序。

printBackward(node1) 
| 
+-> printBackward(node2) 
     | 
     +-> printBackward(node3) 
      | 
      +-> printBackward(None) 
      print node3 
    print node2 
print node1

正如你所看到的，printBackward1被稱爲與節點1作爲參數。在打印node1之前，它將控制流賦予printBackward（node2）。當printBackward（node2）完成時，它會打印node1。

來源

2011-10-12 00:52:45 Melug

回答

相關問題