Python中如何终止递归生成器的执行？

问题原因说明 #

两个现象的根因如下：

• 原代码中的return仅会终止当前层级的生成器执行，上层通过yield from调用该生成器的父函数只会判定当前子树遍历完成，会继续执行后续的遍历逻辑，因此无法实现全局停止。
• Python 3.3及以上版本规范禁止在生成器内部手动抛出StopIteration，否则会被解释器自动转换为RuntimeError，因此该方法无法生效。

两种方案都可以实现需求，其中自定义异常的实现逻辑更简洁，不需要每层递归额外判断终止状态，更推荐使用。

方案1：自定义异常实现 #

通过自定义专属的终止异常，在满足条件时抛出，外层迭代时捕获该异常即可直接终止整个遍历流程。
代码示例：

# 自定义遍历终止异常
class StopTraversal(Exception):
    pass

def traverse(node):
    if node is None:
        return

    yield from traverse(node.left)

    if node.val == 5:
        # 抛出异常直接终止所有层级的递归
        raise StopTraversal

    yield node.val

    yield from traverse(node.right)

# 外层调用示例
root = 你的二叉树根节点
try:
    for val in traverse(root):
        print(val)
except StopTraversal:
    # 捕获到终止异常即代表遍历提前结束
    pass

方案2：可变标记位实现（无异常版本） #

如果不想用异常控制流程，可以传入一个可变的标记变量，所有递归层级共享该标记，触发终止条件时修改标记，所有层级读取到标记为终止状态就直接返回。
代码示例：

def traverse(node, stop=None):
    # 用列表存储标记位保证可变，所有递归层修改的是同一个对象
    if stop is None:
        stop = [False]
    if stop[0] or node is None:
        return

    yield from traverse(node.left, stop)
    if stop[0]:
        return

    if node.val == 5:
        stop[0] = True
        return

    yield node.val

    yield from traverse(node.right, stop)

# 外层调用示例
root = 你的二叉树根节点
for val in traverse(root):
    print(val)

内容的提问来源于stack exchange，提问作者Haitham Gad