递归节点

Question

我试图在我的课程中了解如何阅读下面名为 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，即node1。 tail = list.next 我将其视为node1.next = node2，因此tail = node2。然后我们到达printBackward(tail)，即node2。到那时，会发生什么？我们要重新做一遍吗？我看到这会上升到node3，此时将返回 None 。我们什么时候到达打印头？？？我们在到达打印头之前就进行了递归调用，？请教育我，因为我正在尝试理解课程中提供给我的示例。谢谢！

Answer 1

您对调用 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）。

Answer 2

递归就是调用函数本身。那么让我们看看 printBackward 函数的调用顺序。

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

如您所见， printBackward1 是用 node1 作为参数调用的。在打印node1之前，它将控制流交给printBackward(node2)。当 printBackward(node2) 完成时，它会打印 node1。