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

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)

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

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

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

这不是一个通用的解决方案,但对于某些生成器,您可能会获得一个很好的结果,用栈处理代替递归.