时间戳

首页 > 解决方案 > 试图理解生成器的递归运行

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

问题描述

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

我尝试创建一个有点树，将每个运行递归地连接到下一个运行，但我不知道 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 a

标签： pythongeneratoryield

解决方案

要了解它是如何工作的，您需要了解递归的基本概念。假设我们不是在处理生成器；我们只想在给定头节点的情况下反向打印列表的所有节点。我们调用函数print_reverse传递节点作为参数。如果节点的下一个字段为空，我们只需打印该字段的数据值。但是如果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)

在理解生成器问题之前，必须理解上面的代码。我们不希望创建一个打印节点数据字段的函数print_reverse ，而是希望创建一个生成该值的生成器函数。因此，重命名函数并将 print 函数替换为语句并将递归调用替换为语句是有意义的：yieldyield 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

推荐阅读