Python全排列回溯递归调用栈行为与执行流程解析

本次测试输入为[1,2,3]，对应实现代码如下：

totalcount = 0
res = []

def permute(nums):
    backtrack(nums, [])

def backtrack(nums, path):
    global totalcount
    totalcount += 1
    if not nums:
        res.append(path)
    for x in range(len(nums)):
        #res.append(x)
        backtrack(nums[:x]+nums[x+1:], path+[nums[x]])

permute([1,2,3])

调试现象 #

取消代码中#res.append(x)的注释进行调试，得到的res输出为：

[0, 0, 0, [1, 2, 3], 1, 0, [1, 3, 2], 
  1, 0, 0, [2, 1, 3], 1, 0, [2, 3, 1], 
  2, 0, 0, [3, 1, 2], 1, 0, [3, 2, 1]]

此时统计backtrack函数调用次数的totalcount值为16。

核心疑问 #

• 首次调用backtrack时x=0，按照传参逻辑可以理解第一个结果[1,2,3]的生成过程，但原本认为所有内层调用执行完毕后外层x才会变为2，预期输出仅为[1,2,3],[2,1,3],[3,1,2]，实际代码输出了所有首元素为1、2、3的全排列，该逻辑如何实现？
• 每个排列结果前置的x值数量有时为3有时为2，这些x值的取值逻辑是什么？
• 递归调用的真实执行顺序是什么？16次调用过程中各相关变量的取值分别是怎样的？

问题解答 #

全排列的生成逻辑 #

每一层递归的for循环和x变量都是独立的，归属于当前函数的调用栈帧，只有当前层x对应的所有子递归全部执行完成，当前层的x才会自增，这是之前理解偏差的核心点。
最外层第一次调用backtrack([1,2,3], [])时，该层的for循环x会依次取0、1、2：

• x=0时，选中nums[0]=1放入path，递归传入剩余元素[2,3]进入下一层，这一层会跑完x=0、x=1对应的所有子递归，生成所有首元素为1的排列：[1,2,3]、[1,3,2]
• 等x=0对应的所有子递归全部返回，最外层x才会自增为1，选中nums[1]=2放入path，递归传入剩余元素[1,3]，跑完所有子递归生成首元素为2的两个排列
• 最外层x=2时逻辑同理，生成首元素为3的两个排列
  最终就得到了3!共6个全排列结果。

前置x值数量不一致的原因 #

添加的调试代码res.append(x)写在for循环内部，只要进入for循环就会往res中追加x值，和是否走到递归终止条件无关。
x值的数量等于「从当前递归层到生成最终排列，还需要向下递归的层数」：

• 如果当前层nums长度为3，选中x后需要再往下递归3次才会到nums为空的终止条件，就会连续追加3个x值
• 如果已经回到nums长度为2的递归层（比如首元素已经选完1，当前剩余元素是[2,3]），选中x后只需要再往下递归2次就到终止条件，就只会追加2个x值
  以生成[1,3,2]的过程为例：生成[1,2,3]后，递归返回到nums为[2,3]的层，该层x自增为1，选中3后往下递归，此时只需要再选1次x（选剩余的2）就到终止条件，所以排列前只追加了1、0两个x值，和调试输出完全匹配。

16次调用的计算与执行顺序 #

调用次数可以按递归层的nums长度直接计算：

• 第1次：最外层调用，nums长度为3
• 长度为3的层循环3次，发起3次nums长度为2的递归调用，累计调用4次
• 每个长度为2的调用循环2次，发起2次nums长度为1的递归调用，共3*2=6次，累计调用10次
• 每个长度为1的调用循环1次，发起1次nums长度为0的递归调用，共6*1=6次，累计调用16次
  其中nums长度为0的调用共6次，刚好对应6个全排列结果，也就是递归的终止节点。
  按调用顺序的变量变化如下（缩进代表递归深度）：

调用1: nums=[1,2,3], path=[] → 循环x=0,1,2
  x=0 → 调用2: nums=[2,3], path=[1] → 循环x=0,1
    x=0 → 调用3: nums=[3], path=[1,2] → 循环x=0
      x=0 → 调用4: nums=[], path=[1,2,3] → 命中终止条件，加入res，无循环直接返回
    x=1 → 调用5: nums=[2], path=[1,3] → 循环x=0
      x=0 → 调用6: nums=[], path=[1,3,2] → 命中终止条件，加入res，返回
  x=1 → 调用7: nums=[1,3], path=[2] → 循环x=0,1
    x=0 → 调用8: nums=[3], path=[2,1] → 循环x=0
      x=0 → 调用9: nums=[], path=[2,1,3] → 命中终止条件，加入res，返回
    x=1 → 调用10: nums=[1], path=[2,3] → 循环x=0
      x=0 → 调用11: nums=[], path=[2,3,1] → 命中终止条件，加入res，返回
  x=2 → 调用12: nums=[1,2], path=[3] → 循环x=0,1
    x=0 → 调用13: nums=[2], path=[3,1] → 循环x=0
      x=0 → 调用14: nums=[], path=[3,1,2] → 命中终止条件，加入res，返回
    x=1 → 调用15: nums=[1], path=[3,2] → 循环x=0
      x=0 → 调用16: nums=[], path=[3,2,1] → 命中终止条件，加入res，返回

这个执行顺序和调试得到的res序列完全对应。

内容的提问来源于stack exchange，提问作者jojo33