python - Python 3.2 中的递归

Question

我正在努力研究递归，并发布了一个工作算法来生成给定列表的所有子集。

def genSubsets(L):
    res = []
    if len(L) == 0:
        return [[]]
    smaller = genSubsets(L[:-1])
    extra = L[-1:]
    new = []
    for i in smaller:
        new.append(i+extra)
    return smaller + new

假设我的列表是 L = [0,1]，正确的输出是 [[],[0],[1],[0,1]]

使用 print 语句，我缩小了 genSubsets 在进入 for 循环之前被调用两次的范围。我得到了这么多。

但为什么第一个 for 循环将 L 的值初始化为 [0] 而第二个 for 循环使用 [0,1]？包含 for 循环的递归调用究竟是如何工作的？

Answer 1

我认为使用更长的源列表实际上更容易可视化。如果您使用 [0, 1, 2]，您会看到递归调用重复地从列表中删除最后一项。也就是说，recusion 建立了一堆递归调用，如下所示:

genSubsets([0,1,2])
    genSubsets([0,1])
        genSubsets([0])
            genSubsets([])

此时它达到了递归算法的“基本情况”。对于此函数，基本情况是作为参数给出的列表为空。达到基本情况意味着它返回一个包含空列表 [[]] 的列表。这是堆栈返回时的样子:

genSubsets([0,1,2])
    genSubsets([0,1])
        genSubsets([0]) <- gets [[]] returned to it

因此返回值返回到上一级，它保存在 smaller 变量中。变量 extra 被分配为仅包含列表最后一项的切片，在本例中为全部内容 [0]。

现在，循环遍历 smaller 中的值，并将它们与 extra 的串联添加到 new。由于 smaller(空列表)中只有一个值，new 最终也只有一个值，[]+[0]是[0]。我假设这是您在某个时候打印出的值。

然后最后一条语句返回smaller和new的拼接，所以返回值为[[],[0]]。堆栈的另一个 View :

genSubsets([0,1,2])
    genSubsets([0,1]) <- gets [[],[0]] returned to it

返回值再次赋给smaller，extra为[1]，再次循环。这一次，new 得到两个值，[1] 和 [0,1]。它们再次连接到 smaller 的末尾，返回值为 [[],[0],[1],[0,1]]。最后的堆栈 View :

genSubsets([0,1,2]) <- gets [[],[0],[1],[0,1]] returned to it

同样的事情再次发生，这次将 2 添加到目前找到的每个项目的末尾。 new 以 [[2],[0,2],[1,2],[0,1,2]] 结束。

最终返回值为[[],[0],[1],[0,1],[2],[0,2],[1,2],[0,1, 2]]