3

我正试图围绕递归展开我的头脑，并发布了一个工作算法来生成给定列表的所有子集。

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]]

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

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

4

2 回答 2

7

我认为使用更长的源列表实际上更容易可视化。如果您使用[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，并将它们的连接与extrato相加new。由于smaller（空列表）中只有一个值，因此new最终也只有一个值，[]+[0]即[0]. 我认为这是您在某个时候打印出来的值。

smaller然后最后一条语句返回and的串联new，所以返回值为[[],[0]]。堆栈的另一个视图：

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

返回值被smaller再次分配给extrais [1]，并且循环再次发生。这一次，new得到两个值，[1]和[0,1]。它们再次连接到末尾，smaller返回值为[[],[0],[1],[0,1]]. 最后一个堆栈视图：

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

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

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

于 2012-12-06T06:45:42.847 回答
3

我不喜欢尝试可视化递归函数的整个调用图以了解它们的作用。

我相信有一个更简单的方法：

进入递归函数做正确事情的童话世界™。

假设genSubsets(L)有效：

# This computes the powerset of the list L minus the last element
smaller = genSubsets(L[:-1])

因为这神奇地起作用了，所以唯一缺少的条目是那些包含最后一个元素的条目。

这个片段构建了所有那些缺失的子集：

new = []
for i in smaller:
    new.append(i+extra)

现在我们有那些包含最后一个元素的new子集，我们有那些不包含最后一个元素的子集smaller。

因此，我们现在必须拥有所有子集，因此我们可以返回new + smaller。

唯一剩下的就是确保递归停止的基本情况。因为空集（或本例中的列表）是每个幂集的一个元素，我们可以使用它来停止递归：请求空集的幂集是包含空集的集合。所以我们的基本情况是正确的。由于每个递归步骤都会从列表中删除一个元素，因此必须在某个时间遇到基本情况。

因此，代码确实会产生幂集。

注意：这背后的原理是归纳法。如果某事物适用于某个已知的n 0，并且我们可以证明： 适用于的算法n意味着它适用于n+1，因此它必须适用于所有n ≥ n 0。

于 2012-12-06T09:38:29.157 回答