递归函数，最终打印语句

Question

我正在自学 Python，使用如何像计算机科学家一样思考。我正在学习"Nodes and Linked Lists"。这个递归函数让我很困惑。 明确地说，代码工作正常。我在问，怎么可能是最下面的最后一行代码（print list,）被执行了？

我的问题是关于这个递归函数：

def print_backward (list):
    if list == None: return  #shouldn't the code terminate when this is satisfied?
    print_backward(list.next)
    print list, #seems like the function would terminate before this line 
                #ever gets called

谁能给我解释一下，最后一行print head,是什么时候执行的？阅读这段代码，我会认为我们在评估每个节点后循环回到函数的顶部，然后当我们到达第 3 个也是最后一个节点时，终止语句 if list == None: return 将得到满足，然后代码将退出循环，永远不会到达最底部的打印语句。显然这并没有发生，因为正在调用打印语句。

我问是因为我觉得如果我不了解代码的工作原理就不是在真正学习！如果有人可以解释代码如何到达最终打印语句（并且它到达那里），我将非常感激。我希望我问这个没有违反规则。谢谢！

顺便说一句，我正在打印一个链接列表，货物是 [1,2,3]。向后打印，所以 [3,2,1] 下面是更多上下文的代码。

class Node:
    def __init__(self, cargo = None, next = None):
        self.cargo = cargo
        self.next = next

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

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


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

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

node1.next = node2
node2.next = node3
node3.next = None

print_backward(node1)

输出为：

==== RESTART: /Users/Desktop/Programming Career/Untitled.py ====

3 2 1

Answer 1

让我们逐个节点分析代码在做什么

print_backward 用 node1
是node1 == Nonenone？不，所以我们继续
我们分配head = node1
我们分配 tail = node1.next 与 tail = node2
我们称print_backward(tail)与print_backward(node2)相同
1. print_backward 用 node2
2. 是node2 == Nonenone？不，所以我们继续
3. 我们分配head = node2
4. 我们分配 tail = node2.next 与 tail = node3
5. 我们称print_backward(tail)与print_backward(node3)相同
  1. print_backward 用 node3
  2. 是node3 == Nonenone？不，所以我们继续
  3. 我们分配head = node3
  4. 我们分配 tail = node3.next 与 tail = None
  5. 我们称print_backward(tail)与print_backward(None)相同
    1. print_backward 用 None
    2. 是None == Nonenone？是的，所以我们 return
  6. print head, 被调用，与 print node3, 相同（打印“3”）
6. print head, 被调用，与 print node2, 相同（打印“2”）
print head, 被调用，与 print node1, 相同（打印“1”）

总输出是，“3 2 1”！

Answer 2

递归并不意味着跳转到函数的顶部；这意味着在函数中调用相同的函数。

我认为一个更简单的例子更明显：

def count(number): if number <= 0: return count(number-1) print(number)

当我们调用count(3)时，该函数将打印数字 1 到 3。为什么？因为这是发生的事情：

count(3) 被调用。

number是3，不小于等于0，所以我们不return.

我们称count(3-1)：

count(2) 被调用。

number是2，不小于等于0，所以我们不return.

我们称count(2-1)：

count(1) 被调用。

number为1，不小于等于0，所以我们不return.

我们称count(1-1)：

count(0) 被调用。

number为0，等于0，所以我们return到上一级

我们print1.

我们print2.

我们print3.

递归函数，最终打印语句

Recursive function, final print statement

python

linked-list

nodes

tail-recursion