python - 尝试理解生成器的递归运行

Question

我试图弄清楚如何将此代码的运行绘制到递归树上，因为我不太确定它是如何运行的，即使在调试时也是如此。每个 yield 的作用是什么？为什么我需要它们？

我尝试创建一棵树，将每次运行递归地连接到下一次运行，但我不知道在头部为“c”的yield.data后面是什么

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


def get_reverse_iterator(head):
    if head.next:
        for datum in get_reverse_iterator(head.next):
            yield datum
    yield head.data


lst = Node('a', Node('b', Node('c')))
for x in get_reverse_iterator(lst):
    print(x)

结果应该是:C乙一个

Answer 1

要理解它是如何工作的，您需要了解递归的基本思想。假设我们处理的不是一个生成器；而是一个生成器。我们只是希望在给定头节点的情况下反向打印列表的所有节点。我们调用函数 print_reverse 将节点作为参数传递。如果节点的 next 字段为空，我们只打印该字段的 data 值。但如果next不为空，则它指向在打印当前节点之前必须打印的节点。因此，我们再次递归调用 print_reverse 来首先打印该节点。当 print_reverse 返回时，我们现在可以打印当前节点。当然，当我们递归调用print_reverse来打印下一个节点时，它可能会发现它指向的还有另一个节点必须首先打印，我们将调用print_reverse再次递归。所以我们有:

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


def print_reverse(head):
    if head.next:
        print_reverse(head.next)
    print(head.data)


lst = Node('a', Node('b', Node('c')))
print_reverse(lst)

必须先理解上面的代码，然后才能理解生成器问题。我们希望创建一个生成值的生成器函数，而不是创建一个打印节点的data字段的函数print_reverse。因此，重命名该函数并用 yield 语句替换 print 函数，用 yield from 语句替换递归调用是有意义的:

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


def get_reverse_iterator(head):
    if head.next:
        #print_reverse(head.next)
        yield from get_reverse_iterator(head.next)
    #print(head.data)
    yield head.data

lst = Node('a', Node('b', Node('c')))

现在我们可以使用生成器，如下所示:

for x in get_reverse_iterator(lst):
    print(x)

或者:

l = [x in get_reverse_iterator(lst)]

但是使用递归来避免创建多个生成器对象的替代方法是:

def get_reverse_iterator(head):
    stack = []
    while head.next:
        stack.append(head)
        head = head.next
    yield head.data
    while len(stack):
        head = stack.pop()
        yield head.data