4

我正在研究 Downey 的 How To Think Like a Computer Scientist，我对他的Linked List的 print_backward() 函数有疑问。

首先，这是 Downey 在 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

为了打印链表，我们使用了 Downey 的另一个函数。

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”吗？

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

4

7 回答 7

2

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

这并非巧合。

这两个函数都会递归，直到到达列表的末尾。不同之处在于打印是在此过程中还是之后进行。

函数调用使用堆栈，这是一种后进先出数据结构，可记住在进行函数调用时计算机执行代码的位置。以一种顺序放入堆栈的内容以相反的顺序取出。因此，递归以与原始调用相反的顺序“展开”。打印发生在展开过程中，即在每个递归调用完成之后。

于 2012-07-19T21:29:57.077 回答
2 
def print_backward(list):
     if list == None : return
     print_backward(list.next)
     print list,

调用“list.next”作为 print_backward 的值不会简单地给你“b c”吗？

不; 想象一下当 a->b->c 被传递给 print_backward 时会发生什么：

"[bc]" 被传递给 print_backward，然后 "a" 被打印出来。但是在打印“a”之前，“print_backward”会调用自身。所以：

  • [ abc ] 不是 None，所以 b->c 被传递给 print_backward
    • [ bc ] 被传递给 print_backward
      • [ c] 被传递给 print_backward
      • 没有传递给 print_backward
        • 返回
      • 然后打印“c”
    • 然后打印“b”
  • 然后打印“a”
  • 退出。
于 2012-07-19T21:21:49.617 回答
1

有时我发现更容易将递归视为仅构建要按特定顺序进行的调用列表。随着函数的继续，它会建立一堆调用，直到最终到达基本情况。基本情况是不需要进一步分解程序的情况；在这个函数中，基本情况是没有要打印的内容，在这种情况下，我们不做任何事情就离开return。

当我们展开函数调用的递归堆栈时，很酷的事情通常发生在返回的路上。目前，print_backward已在列表的每个元素上调用，它现在将“展开”，首先完成最近的调用，最后完成较早的调用。这意味着print_backward在最后一个元素上调用 created 的“实例”是第一个完成的，因此最后一个元素是第一个要打印的元素，然后是倒数第二个、倒数第三个等。 , 直到原始函数最终退出。

看一下发生的事情的这种表示：

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

于 2012-07-19T21:29:54.317 回答
1

如果列表不是无，它调用 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'
于 2012-07-19T21:20:34.493 回答
0

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

于 2012-07-19T21:14:49.900 回答
0

不，有两种递归：

  1. 尾递归：如果函数返回后除了返回它的值之外什么都不做。函数调用不堆叠。
  2. 首先找到基本情况的递归（在这种情况下，null，然后向后处理列表）。每个函数调用都被压入堆栈，以供以后处理。在您的示例中，该函数被堆叠为'a'->'b'->'c'->null，然后当堆栈被弹出时，作者通过向后打印表明：`if null return: print 'c' -> print 'b' -> print 'a'

在您的情况下，作者仅演示了一个不同的递归概念，并使用它来向后打印列表。

于 2012-07-19T21:16:26.587 回答
0

您的节点如下所示：

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):) 总是一个好主意，因为这使它成为一个新型类。

于 2012-07-19T21:16:47.170 回答