使用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

我只是想知道是否可以用递归来实现。

Answer 1

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)

当然可以！请把你想要翻译的内容发给我，我会帮你用简单易懂的语言解释清楚。

Answer 2

在某些情况下，使用栈而不是递归来处理生成器可能更好。你可以用栈和一个循环来重写一个递归的方法。

下面是一个使用回调的递归方法的例子，这个方法可以用栈的逻辑来重写：

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)

（注意，如果你想保持和最初相同的遍历顺序，你需要反转子节点的顺序，因为第一个放入栈的子节点会是最后一个被取出的。）

现在你可以得到和上面 traverse_tree 一样的效果，但用生成器来实现：

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

这并不是适用于所有情况的解决方案，但对于某些生成器来说，用栈处理代替递归可能会得到不错的结果。

Answer 3

是的，你可以这样做：

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。