此功能为什么向后打印链接列表？

Question

我正在通过唐尼的如何像计算机科学家一样思考，我对Linked List有一个关于他的print_backward（）函数的问题。

首先，这里唐尼在Python实现链表：

class Node: 
    #initialize with cargo (stores the value of the node) 
    #and the link. These are set to None initially. 
    def __init__(self, cargo = None, next = None): 
     self.cargo = cargo 
     self.next = next 

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

我们给这个类中的下列货物和链接值：

#cargo 
node1 = Node('a') 
node2 = Node('b') 
node3 = Node('c') 
#link them 
node1.next = node2 
node2.next = node3 

要打印的链表，我们用另一种唐尼的职能。

def printList(node): 
    while node: 
     print node, 
     node = node.next 

>>>printList(node1) 
>>>a b c 

所有非常简单。但我不明白如何在以下函数中的递归调用允许向后打印链表。

def print_backward(list): 
    if list == None : return 
    print_backward(list.next) 
    print list, 

>>>print_backward(node1) 
>>>c b a 

不会调用“list.next”作为print_backward的值只是给你“b c”？

注意：下面几个人指出，这个函数设计的很糟糕，因为给定任何列表，我们不能表明它总是会达到基本情况。唐尼在同一章的后面也指出了这个问题。

Answer 1

在正向打印版本中，它会在进行递归调用之前打印每个节点。在后向打印版本中，它在之后打印每个节点进行递归调用。

这不是巧合。

这两个函数都会递归到列表末尾。不同之处在于在此过程中还是之后发生打印。

函数调用使用栈，后进先出的数据结构，它记住了函数调用时计算机执行代码的位置。以一种顺序放入堆栈的内容以相反顺序排列。因此，递归按照原始调用的相反顺序“解开”。打印发生在退绕过程期间，即在每次递归调用完成之后。

Answer 2

它使用递归。它一直“拉”到最后，然后在每次调用返回时打印每个元素。由于第一个打印是最近被打印的，所以它向后打印列表。

Answer 3

号有2种递归：

1. 尾递归：如果有什么不同之处返回其值的函数返回后做。函数调用不会堆叠。
2. 递归首先找到基本案例（在这种情况下，null，然后向后处理列表）。每个函数调用都被推入堆栈中，以供后续处理。在你的例子中，函数被堆叠为'a'->'b'->'c'->null，然后当堆栈弹出时，作者显示反向打印：`如果null返回：打印'c' - >打印'b' - >打印'a'

就你而言，作者只演示了递归的不同概念，并用它向后打印列表。

Answer 4

你的节点是这个样子：

node1 node2 node3 
'a' => 'b' => 'c' => None 

在第一次调用print_backward，变量list具有价值'a'，以print_backward招一个进一步向下行后续调用。请注意，他们没有任何打印任何东西，直到你打到警卫（None）在哪个时间，事情得到打印从前到后作为print_backward收到节点'c'必须返回之前print_backward那接收节点'b'可以打印（因为打印语句在函数调用之后）等等。

虽然我认识到这是别人的代码，但在这里有几件事是不好的做法 - 最好我现在告诉你，而你在学习，而不是在以后。首先，不要使用list作为变量名称，因为它是python中内置函数/类型的名称。第二，平等测试if obj == None最好由if obj is None完成，最后，让你的类继承object（class node(object):），这是一个好主意，因为它使它成为一种新风格的类。

Answer 5

如果list不是None，它会调用print_backward，然后打印列表的第一个成员。展开，这实际上是发生了什么。您可以看到，当电话开始返回时，会打印'c'，然后'b'，然后'a'。

它看起来在实际打印列表一样，它打印的第一个节点

print_backward(list='a','b','c') 
    print_backward(list='b','c') 
    print_backward(list='c') 
     print_backward(list=None) 
     list is None, so return 
     print 'c' 
    print 'b','c' 
    print 'a','b','c' 

Answer 6

def print_backward(list): 
    if list == None : return 
    print_backward(list.next) 
    print list, 

会不会叫“list.next”为print_backward的价值简单地给你“BC” ？

否;图片当a-> b-> c传递给print_backward时发生了什么：

“[b c]”被传递给print_backward，然后打印出“a”。 但打印“a”之前的“print_backward”会自行调用。所以：

• [ABC]不是无，那么B->Ç被传递给print_backward
  • [BC]传递给print_backward
    • [C]被传递到print_backward
    • 无被传递到print_backward
      • 返回
    • 然后“C “打印
  • 然后 ”b“ 被印刷
• 然后 ”a“ 被印刷
• 退出。

Answer 7

有时我觉得将递归看作仅仅构造一个按特定顺序调用的列表更容易。随着函数的继续，它会建立一堆调用，直到它最终到达基本情况。基本情况是不需要进一步分解程序的情况;在这个函数中，基本情况是什么时候什么都不打印，在这种情况下，我们只是在return之前不做任何事情。

很酷的东西通常发生在我们展开函数调用的递归堆栈的路上。目前，print_backward已在列表中的每个元素上调用，并且现在将“展开”，先完成最近的调用，然后再调用最近的调用。这意味着当您在最后一个元素上调用print_backward时创建的“实例”是第一个要完成的元素，因此最后一个元素是第一个要打印的元素，接着是倒数第二个，倒数第三个等等。直到原来的函数最终退出。

在发生了什么这表示请看：

print_backward(node1)   #first call to print_backward 
    print_backward(node2)  #calls itself on next node 
     print_backward(node3) #calls itself on next node 
      print_backward(None) #calls itself on None. We can now start unwinding as this is the base case: 
     print Node3    #now the third invocation finishes... 
    print Node2     #and the second... 
print Node1      #and the first. 

虽然功能首先是在较早的元素调用时，实际打印该元素来递归调用之后的部分，所以不会实际执行直到递归调用完成。在这种情况下，这意味着print list部分将不会执行，直到所有后面的元素都先打印完（按相反顺序），这样就可以向后打印列表元素。 ：D