试图理解生成器的递归运行

Question

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

我试过创建一个有点像树的树，它递归地连接每个运行它的下一个，但我不知道下面是什么 yield.data 头是 'c'

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 b 一个

Answer 1

每当您将方法作为生成器调用时（例如 for x in get_reverse_iterator()），python 开始逐行执行该方法。每当它碰到 yield 时，它就会停止并 returns。当它在 for 循环的下一次迭代中被要求提供 next() 值时，它会继续执行。

这看起来像一个相当简单的 linked-list-traversal 惯用语，其中列表的每个元素包含的数据本身就是一个列表（或其他一些可迭代的值，如字符串）：

list[0].data = [1, 2, 3, 4]
list[1].data = [5, 6, 7, 8]
...
list[9].data = [37, 38, 39, 40]

那么此处代码所做的就是将sub-lists从主列表的后面打印到主列表的前面。输出应如下所示：

37 38 39 40 33 34 35 36 ... 5 6 7 8 [1, 2, 3, 4]

当您查看代码的执行方式时，这一点就很明显了。我会用文字重写它：

func get_reverse_iterator(head) {
    if head isn't the last element of the list, then
        call this function on the next element of the list (head.next)
        for every element in the return value of that,
            yield that element
    yield this element's data

'base case' 是列表的最后一个元素，没有 .next。因此它的可迭代的 data 返回到 second-to-last 元素。 second-to-last 元素依次生成该数据的每个元素，然后 returns 它自己的数据到 third-to-last 元素。 third-to-last 元素依次生成该数据的每个元素，依此类推，直到最后到达列表的第一个元素。到目前为止，每个 yield 语句都递归地将一个元素向上传递到链中，因此第一个元素的内部 for 循环到目前为止已经产生了 36 个值。最后，列表中所有后面的元素都完成了值传递，因此第一个元素到达函数的最后一个语句并产生自己的数据。

但是没有什么可以捕获生成的数据并按单个元素解析它，因此它首先被打印为 list。或者，至少，这是我上面给出的例子。

在你的情况下，它更直接，因为当你迭代 string 时，每个项目仍然是 string。但在较小的范围内也是一样的：

get_reverse_iterator()在lst
根节点（我称之为NodeA）有一个.next
get_reverse_iterator() 在下一个节点上被调用，我称之为 NodeB
NodeB 有一个 .next
get_reverse_iterator() 在下一个节点上被调用，我称之为 NodeC
NodeC 没有 .next
get_reverse_iterator(NodeC) 跳过 for 循环并产生 NodeC.data，即 'c'`
get_reverse_iterator(NodeB) 在 for 循环中捕获 'c' 并产生它
get_reverse_iterator(NodeA) 在 for 循环中捕获 'c' 并产生它
'c' 被分配给 x，并被打印出来。
发生外循环的下一次迭代，执行returns到get_reverse_iterator(NodeB)
for 循环结束，因为get_reverse_iterator(NodeC) 已经停止生成东西
get_reverse_iterator(NodeB)结束for循环，退出if块，最后产生NodeB.data，即'b'
get_reverse_iterator(NodeA) 在 for 循环中捕获 'b' 并产生它
'b' 被分配给 x，并打印出来。
外循环的下一次迭代发生，执行returns到get_reverse_iterator(NodeA)
for 循环结束，因为get_reverse_iterator(NodeC) 已经停止生成东西
get_reverse_iterator(NodeA)结束for循环，退出if块，最后产生NodeA.data，即'a'
'a' 被分配给 x，并打印出来
外部 for 循环结束，因为 get_reverse_iterator(NodeA) 已经停止产生东西。

Answer 2

要了解它的工作原理，您需要了解递归的基本概念。假设我们不是在处理发电机；我们只希望在给定头节点的情况下反向打印列表的所有节点。我们调用函数 print_reverse 将节点作为参数传递。如果节点的 next 字段为空，我们只打印字段的 data 值。但是如果 next 不为空，则指向一个必须打印的节点，然后才能打印当前节点。所以我们再次递归调用 print_reverse 来首先打印那个节点。当 print_reverse returns 我们现在可以打印当前节点。当然，当我们递归调用 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)

理解生成器问题之前必须先理解上面的代码。我们不想创建一个函数 print_reverse 来打印节点的 data 字段，而是希望创建一个生成器函数产生的价值。因此，重命名函数并用 yield 语句替换打印函数并用 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

试图理解生成器的递归运行

trying to understand recursive run of generators

python

yield

generator

试图理解生成器的递归 运行

trying to understand recursive run of generators

python

yield

generator

试图理解生成器的递归运行