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]].堆栈的另一个视图:

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

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

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

同样的事情再次发生,这次将2s 添加到目前为止找到的每个项目的末尾.new最终成为[[2],[0,2],[1,2],[0,1,2]].

最终的回报值是 [[],[0],[1],[0,1],[2],[0,2],[1,2],[0,1,2]]