python - 递归节点

我试图在我的课程中理解如何阅读下面的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应该被忽略，因为node1包含对node2的引用，所以我们移动到head = list节点1。tail = list.next我把它看作node1.next=node2所以tail=node2。然后我们得到printBackward(tail)节点2。在那一点上，会发生什么？我们是不是又重复了一遍？我看到这个上升到第3点，在那一点上不会返回任何。我们什么时候到print head,？?? 我们在到达print head,之前进行递归调用？请教育我，因为我正在努力理解的例子，给我在我的教训。谢谢！

最佳答案

您对调用printBackward(node3)之前发生的所有事情都是正确的。现在的情况是，每次到达递归printBackward()调用时，都会深入到调用堆栈中。最后的print实际上不会被调用，直到递归停止调用printBackward()，然后展开。当它每次返回时，就会调用print，这就是为什么您会得到倒序。print发生在调用堆栈展开期间。
当您到达node3时，tail变为None，下一次调用printBackwards()就是立即返回的内容，打印开始。

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

还有一点需要注意的是，您正在隐藏一些内置的python名称（list和next）。