Python递归结合yield生成幂集的代码异常问题排查与求解

问题分析 #

1. 第一版代码返回空的原因 #

你在递归调用gps的时候没有处理生成器的产出，直接写gps(s, res)相当于创建了生成器对象但没有迭代它，所有深层递归里的yield res都不会被外层获取。只有当传入的s为空时才会直接触发yield，但你调用时传入的s是[1,2]非空，整个生成器没有任何产出，所以list()转换后是空列表。
另外这版还有两个隐藏问题：

• 对输入列表s执行pop()后没有做恢复操作，会直接修改原输入列表
• 默认参数res=set()是可变对象，多次调用函数时会复用同一个集合，导致结果错乱

2. 第二版能正确打印的原因 #

这版你添加了s.append(elem)和res.remove(elem)做回溯，递归过程中s和res的状态可以正确回滚，所以走到基线条件时print(res)能输出正确的结果，但这版没有返回值，无法改成生成器直接使用。

3. 第三版加了yield from仍然错误的核心原因 #

你yield的是同一个res集合的引用，所有产出的结果都指向同一个内存地址。后续回溯时执行res.remove(elem)会修改已经产出的集合内容，等到整个递归结束，所有之前产出的集合都被清空了，最终你得到的列表里会是4个空集合。
另外这版仍然存在可变默认参数的问题，需要修正。

修正后的代码 #

def gps(s, res=None):
    # 避免可变默认参数问题
    if res is None:
        res = set()
    if s:
        elem = s.pop()
        yield from gps(s, res)
        res.add(elem)
        yield from gps(s, res)
        # 回溯恢复状态
        res.remove(elem)
        s.append(elem)
    else:
        # 返回集合的副本，避免后续修改影响已产出的结果
        yield set(res)

调用list(gps([1,2]))就能得到正确结果[set(), {1}, {2}, {1, 2}]（幂集不要求元素顺序，顺序存在差异属于正常情况）。

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