使用yield进行递归

Question

有没有办法将递归和 yield 语句结合起来？例如，一个使用递归的无限数字生成器可能如下所示：

def infinity(start):
    yield start
    # recursion here ...

>>> it = infinity(1)
>>> next(it)
1
>>> next(it)
2

我尝试了：

def infinity(start):
    yield start
    infinity(start + 1)

并且

def infinity(start):
    yield start
    yield infinity(start + 1)

但是它们都没能实现我想要的，第一个在产出start后停止了，而第二个则产出了start、生成器然后停止了。

注意：我知道你可以使用while循环来做到这一点：

def infinity(start):
    while True:
        yield start
        start += 1

我只想知道这是否可以递归地完成。

- juliomalegria

---

请点击这里查看我之前提出的一个问题的好答案。 - sizzzzlerz

注意：正确的做法是使用 itertools.count 而不是自己编写解决方案，无论是基于循环还是其他方式。 - Petr Viktorin

@PetrViktorin 这只是一个例子，生成无限的数字并不是真正的问题。 - juliomalegria

Answer 1

是的，你可以这样做：

def infinity(start):
    yield start
    for x in infinity(start + 1):
        yield x

一旦达到最大递归深度，这将报错。

从Python 3.3开始，您可以使用

def infinity(start):
    yield start
    yield from infinity(start + 1)

如果你只是递归调用生成器函数，而不循环它或使用yield from，那么你只是建立一个新的生成器，而没有实际运行函数体或产生任何东西。

参考 PEP 380 获取更多详细信息。

- Sven Marnach

---

但是似乎在使用yield from时仍然存在递归限制 :( - Jo So

递归深度限制将永远存在。 - Radio Controlled

Answer 2

在某些情况下，使用堆栈而不是递归生成器可能更可取。可以使用堆栈和while循环重新编写递归方法。

以下是一个使用回调函数的递归方法示例，可以使用堆栈逻辑进行重写：

def traverse_tree(callback):
    # Get the root node from somewhere.
    root = get_root_node()
    def recurse(node):
        callback(node)
        for child in node.get('children', []):
            recurse(child)
    recurse(root)

上述方法遍历一个节点树，每个节点都有一个children数组，其中可能包含子节点。当遇到每个节点时，会发出回调并将当前节点传递给它。

该方法可以这样使用，打印每个节点的某个属性。

def callback(node):
    print(node['id'])
traverse_tree(callback)

使用堆栈替代，并将遍历方法编写为生成器

# A stack-based alternative to the traverse_tree method above.
def iternodes():
    stack = [get_root_node()]
    while stack:
        node = stack.pop()
        yield node
        for child in reversed(node.get('children', [])):
            stack.append(child)

请注意，如果您希望遍历顺序与原始顺序相同，则需要反转子项的顺序，因为附加到堆栈的第一个子项将是弹出的最后一个子项。

现在您可以使用生成器获得与上面的相同的行为：

for node in iternodes():
    print(node['id'])

这不是一种适用于所有情况的解决方案，但对于某些生成器，您可能会通过使用堆栈处理替代递归来获得良好的结果。

- t.888

---

好的回答！在Python 2.7中，yield不能真正与递归一起使用，但是通过手动管理堆栈，您可以获得相同的效果。 - 00prometheus

Answer 3

def lprint(a):
    if isinstance(a, list):
        for i in a:
            yield from lprint(i)
    else:
        yield a

b = [[1, [2, 3], 4], [5, 6, [7, 8, [9]]]]
for i in lprint(b):
    print(i)

- Юрий Блинков

---

b是什么？请尽量避免只给出代码的答案……稍作解释和说明可以帮助我们更好地理解您的回答。 - Tomerikoo

for i in l: print(a) - Юрий Блинков

为什么不编辑答案，使其更清晰明了呢？您可以通过单击答案下方的小“编辑”标签或单击此处来完成。另外，正如我所说，尝试添加一些解释，说明这样做是如何解决问题的。 - Tomerikoo

yield from 就是我在寻找的。谢谢！ - tarikki