Python 具有递归调用的生成器

Question

我正在尝试使用预序深度优先搜索生成树中的节点。父节点可以有任意数量的子节点，子节点存储在列表中。

我认为这段代码可以工作，但似乎 for 循环正在遍历每个子级，而没有真正进入递归调用。

def traverse_tree(t):
    yield t.label, t.val
    for child in t.children:
        traverse_tree(child)

有人知道怎么处理吗？

Answer 1

如果您查看该函数，对于每次调用，yield 表达式只会被命中一次。所以你的发电机只会产生一件事。要让它产生不止一件事，你也需要从 children 产生：

def traverse_tree(t):
    yield t.label, t.val
    for child in t.children:
        yield from traverse_tree(child)

这是 python 3.3+ 语法 (IIRC)。对于早期版本：

def traverse_tree(t):
    yield t.label, t.val
    for child in t.children:
        for label, val in traverse_tree(child):
            yield label, val

Answer 2

查看此答案 Recursion using yield, and more specifically the yield from construction here: https://docs.python.org/3/whatsnew/3.3.html#pep-380。

Answer 3

当您调用包含yield的函数时，函数体中的代码不会运行。相反，它 returns 一个生成器对象。

您可以使用列表来存储结果：

def traverse_tree(t, list):
    list.append((t.label, t.val))
    for child in t.children:
        traverse_tree(child, list)

Python 具有递归调用的生成器

Python generator with recursive call

python

recursion

generator