For循环使用递归调用的输出作为参数

Question

目前正在阅读Mark学习Python5e，其中有一个置换函数，我无法理解它，并希望得到一些指导。

def permute1(seq):
    if not seq:
        return [seq]
    else:
        res = []
        for i in range(len(seq)):
            rest = seq[:i] + seq[i+1:]
            for x in permute1(rest):
                res.append(seq[i:i+1] + x)
        return res

seq = (1,2,3)
permute1(seq)

1. 用于x的值。是上一次permute1()调用的结果吗？
2. 为什么res在整个过程中处于else:语句的顶部仍然是空的？这是一个可变的与不变的问题吗？for循环实际上将其输出附加到哪个变量？
3. 在for循环中重新构建序列之前，清空序列的过程是否是我可以在其他地方查找的常见设计模式？

这里可能是permute1()的一个更有用的版本，所有的变量都要打印出来。

def permute1(seq):
    if not seq:
        return [seq]
    else:
        res = []
        print('at the top seq = {} res = {},'.format(seq, res))
        for i in range(len(seq)):
            rest = seq[:i] + seq[i+1:]
            print('recursive call seq = {}, rest = {}, i = {}'.format(seq, rest, i))
            for x in permute1(rest):
                print('inside x = {}, rest = {}, seq = {}'.format(x, rest, seq))
                res.append(seq[i:i+1] + x)
        print('seq = {}; res = {}'.format(seq,res))
        return res

seq = (1,2,3)
permute1(seq)

Answer 1

递归函数调用只是另一个函数调用，这类调用并没有什么特别之处。调用一个函数，当它返回时，使用该调用的结果。

使用递归，所发生的情况是有一个调用堆栈，一个调用另一个调用，直到函数最终返回一个结果，因此第一个外部调用可能需要等待一段时间才能继续给定的结果。

在您的示例中，permute1()总是返回一个列表(return [seq]位于顶部，或者return res更低)，因此for x in ...循环该结果(一旦递归调用返回)，并使用结果中的每个元组为其添加单个元素元组(res[i:i + 1]切片元组仅包含单个元素，索引i处的元素)。

使用空元组调用函数时，该函数将立即返回：

>>> permute1(())
[()]

这是一个没有递归调用的阶段，这一点很重要！递归就是这样结束的！

另一个块使用seq使用rest = seq[:i] + seq[i+1:]创建一个新的元素列表。这是一个元组，去掉了一个元素，在索引i中

>>> seq
(1, 2, 3)
>>> seq[:1] + seq[2:]  # if i is 1, then..
(1, 3)

如果您使用单个元素元组调用permute1()，那么for i in range(len(seq))只循环一次，使用i = 0。这意味着res被设置为空元组(长度为1的元组(删除了1元素的元组是空元组)，因此只有一个permute1(())调用。我们在上面看到了，它只返回[()]，最后是添加到res中的seq[i:i+1] + x，函数返回。

因此，其中包含一个元素的调用进行了一个递归调用，并返回了一个带有单个元组的列表，这与您开始使用的内容基本相同：

>>> permute1((1,))
[(1,)]

对于2个元素，循环迭代两次，使用单个元素元组调用两次permute1()，这将完成上述操作。这两个调用都会生成一个包含1个元素的列表，因此您将得到两个新的元组res，这是输入元素的两个顺序：

>>> permute1((1,))
[(1, 2), (2, 1)]

你可以从那里推断出3个元素是如何工作的。

通过传递级别信息，它可以帮助缩进打印信息：

def permute1(seq, level=0):
    indent = '    ' * level
    p = lambda msg, *args: print(indent + msg.format(*args))
    p('permute1({}, {}) called', seq, level)
    if not seq:
        p('- end stage, seq is empty, returning [(),]')
        return [seq]
    else:
        p('- Looping {} times over {}', len(seq), seq)
        res = []
        for i in range(len(seq)):
            rest = seq[:i] + seq[i+1:]
            p('| Loop #{}, rest is: {}, seq[i] is {}, making recursive call', i + 1, rest, seq[i])
            for x in permute1(rest, level + 1):
                p(' + processing 1 result from recursive call, {}', x)
                res.append(seq[i:i+1] + x)
                p(' + res appended to, now {}', res)
            p('\ Loop #{} complete, res is: {}', i + 1, res)
        p('Function done, returning {}', res)
        return res

p lambda打印前面有4个空格的level消息；递归越深，调用缩进的越多。

这有点冗长，但现在您可以看到在什么级别发生的事情：

>>> permute1(seq)
permute1((1, 2, 3), 0) called
- Looping 3 times over (1, 2, 3)
| Loop #1, rest is: (2, 3), seq[i] is 1, making recursive call
    permute1((2, 3), 1) called
    - Looping 2 times over (2, 3)
    | Loop #1, rest is: (3,), seq[i] is 2, making recursive call
        permute1((3,), 2) called
        - Looping 1 times over (3,)
        | Loop #1, rest is: (), seq[i] is 3, making recursive call
            permute1((), 3) called
            - end stage, seq is empty, returning [(),]
         + processing 1 result from recursive call, ()
         + res appended to, now [(3,)]
        \ Loop #1 complete, res is: [(3,)]
        Function done, returning [(3,)]
     + processing 1 result from recursive call, (3,)
     + res appended to, now [(2, 3)]
    \ Loop #1 complete, res is: [(2, 3)]
    | Loop #2, rest is: (2,), seq[i] is 3, making recursive call
        permute1((2,), 2) called
        - Looping 1 times over (2,)
        | Loop #1, rest is: (), seq[i] is 2, making recursive call
            permute1((), 3) called
            - end stage, seq is empty, returning [(),]
         + processing 1 result from recursive call, ()
         + res appended to, now [(2,)]
        \ Loop #1 complete, res is: [(2,)]
        Function done, returning [(2,)]
     + processing 1 result from recursive call, (2,)
     + res appended to, now [(2, 3), (3, 2)]
    \ Loop #2 complete, res is: [(2, 3), (3, 2)]
    Function done, returning [(2, 3), (3, 2)]
 + processing 1 result from recursive call, (2, 3)
 + res appended to, now [(1, 2, 3)]
 + processing 1 result from recursive call, (3, 2)
 + res appended to, now [(1, 2, 3), (1, 3, 2)]
\ Loop #1 complete, res is: [(1, 2, 3), (1, 3, 2)]
| Loop #2, rest is: (1, 3), seq[i] is 2, making recursive call
    permute1((1, 3), 1) called
    - Looping 2 times over (1, 3)
    | Loop #1, rest is: (3,), seq[i] is 1, making recursive call
        permute1((3,), 2) called
        - Looping 1 times over (3,)
        | Loop #1, rest is: (), seq[i] is 3, making recursive call
            permute1((), 3) called
            - end stage, seq is empty, returning [(),]
         + processing 1 result from recursive call, ()
         + res appended to, now [(3,)]
        \ Loop #1 complete, res is: [(3,)]
        Function done, returning [(3,)]
     + processing 1 result from recursive call, (3,)
     + res appended to, now [(1, 3)]
    \ Loop #1 complete, res is: [(1, 3)]
    | Loop #2, rest is: (1,), seq[i] is 3, making recursive call
        permute1((1,), 2) called
        - Looping 1 times over (1,)
        | Loop #1, rest is: (), seq[i] is 1, making recursive call
            permute1((), 3) called
            - end stage, seq is empty, returning [(),]
         + processing 1 result from recursive call, ()
         + res appended to, now [(1,)]
        \ Loop #1 complete, res is: [(1,)]
        Function done, returning [(1,)]
     + processing 1 result from recursive call, (1,)
     + res appended to, now [(1, 3), (3, 1)]
    \ Loop #2 complete, res is: [(1, 3), (3, 1)]
    Function done, returning [(1, 3), (3, 1)]
 + processing 1 result from recursive call, (1, 3)
 + res appended to, now [(1, 2, 3), (1, 3, 2), (2, 1, 3)]
 + processing 1 result from recursive call, (3, 1)
 + res appended to, now [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1)]
\ Loop #2 complete, res is: [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1)]
| Loop #3, rest is: (1, 2), seq[i] is 3, making recursive call
    permute1((1, 2), 1) called
    - Looping 2 times over (1, 2)
    | Loop #1, rest is: (2,), seq[i] is 1, making recursive call
        permute1((2,), 2) called
        - Looping 1 times over (2,)
        | Loop #1, rest is: (), seq[i] is 2, making recursive call
            permute1((), 3) called
            - end stage, seq is empty, returning [(),]
         + processing 1 result from recursive call, ()
         + res appended to, now [(2,)]
        \ Loop #1 complete, res is: [(2,)]
        Function done, returning [(2,)]
     + processing 1 result from recursive call, (2,)
     + res appended to, now [(1, 2)]
    \ Loop #1 complete, res is: [(1, 2)]
    | Loop #2, rest is: (1,), seq[i] is 2, making recursive call
        permute1((1,), 2) called
        - Looping 1 times over (1,)
        | Loop #1, rest is: (), seq[i] is 1, making recursive call
            permute1((), 3) called
            - end stage, seq is empty, returning [(),]
         + processing 1 result from recursive call, ()
         + res appended to, now [(1,)]
        \ Loop #1 complete, res is: [(1,)]
        Function done, returning [(1,)]
     + processing 1 result from recursive call, (1,)
     + res appended to, now [(1, 2), (2, 1)]
    \ Loop #2 complete, res is: [(1, 2), (2, 1)]
    Function done, returning [(1, 2), (2, 1)]
 + processing 1 result from recursive call, (1, 2)
 + res appended to, now [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2)]
 + processing 1 result from recursive call, (2, 1)
 + res appended to, now [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
\ Loop #3 complete, res is: [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
Function done, returning [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]