在递归生成器中调用顺序？

Question

def powerset(seq):
    """
    Returns all the subsets of this set. This is a generator.
    """
    if len(seq) <= 1:
        yield seq
        yield []
    else:
        for item in powerset(seq[1:]):
            yield [seq[0]]+item
            yield item

上面是一个递归生成器，可以生成所有的功率集。例如

powerset([1,2,3])=>[1, 2, 3][2, 3][1, 3][3][1, 2][2][1][]

但我对它的工作原理感到困惑。它似乎是这样屈服的：

powerset([1,2,3])=>powerset([2,3])=>powerset([3]) 

它是outside=>；inside，与“recursive”在我的理解中的意思相反，inside=>；outside，例如递归求解阶乘（5）：

factorial has been called with n = 5
factorial has been called with n = 4
factorial has been called with n = 3
factorial has been called with n = 2
factorial has been called with n = 1
intermediate result for  2  * factorial( 1 ):  2
intermediate result for  3  * factorial( 2 ):  6
intermediate result for  4  * factorial( 3 ):  24
intermediate result for  5  * factorial( 4 ):  120
120

那么如何理解递归生成器呢？你知道吗

Answer 1

基本上，生成器实现了一个回溯算法：在到达任何yield之前，已经进行了许多递归调用。只有当递归嵌套的深度足够使剩余列表的长度为1时，才会执行程序文本中首先出现的yield调用，并且只有在嵌套深度足够使剩余列表的长度为1之后才会进入for循环，因为这需要最内部的生成器生成某些内容。你知道吗

powerset([1,2,3]) level 1: seq1=[1,2,3]
| powerset([2,3]) level 2: seq2=[2,3]
| | powerset([3]) level 3: seq3=[3]
| | | yield [3]   3: yield seq3, becomes item2 in level 2
| | yield [2,3]   2: yield [seq2[0]] + item2, becomes item1 in level 1
| yield [1,2,3]   1: yield [seq1[0]] + item1, output
| yield [2,3]     1: yield item1, output
...

只有通过for循环的最后一行“冒泡”，最里面生成的短序列才会出现在最外面调用的输出中。在达到这一点之前，产生与seq[0]的组合。你知道吗

如果您想以另一种方式获得输出，请尝试交换循环中的两行yield。你知道吗

Answer 2

让我们看看：

这是递归部分：

for item in powerset(seq[1:]):
            yield [seq[0]]+item
            yield item

基本上这意味着

for every result in a smaller powerset:

    return the not used value + the result

    then return result alone

如果我们看powerset（[3]），它首先返回[3]，然后返回[]，因为它的长度是1

powerset（[2,3]）调用powerset（[3]），然后执行以下操作：

1. 返回powerset（[3]）（=[2,3]）的2和第一个项
2. 只返回powerset（[3]）（=[3]）的第一项
3. 返回powerset（[3]）（=[2]）的2和秒项
4. return第二个项的powerset（[3]）（=[]）

这导致[2,3] [3] [2] []

如果我们调用powerset（[1,2,3]），同样的事情也会发生

1. 1+[2,3]
2. [2,3]
3. 1+[3]
4. [3条]
5. 1+[2]
6. [2条]
7. 1+[]
8. []