Python递归实现permutations排列算法的递归逻辑相关疑问

首先附上完整的实现代码：

def permutations(word):
    if len(word) == 1:
        return [word]
    perms = permutations(word[1:])
    char = word[0]
    result = []
    for perm in perms:
        for i in range(len(perm) + 1):
            result.append(perm[:i] + char + perm[i:])
    return result

疑问1：为什么代码执行return语句后仍会继续运行？ #

这是递归调用的层级特性导致的，每一次调用permutations函数都会生成一个独立的函数实例压入调用栈，return语句只会终止当前层级的函数实例运行，把返回值传递给上一层调用它的函数实例，不会直接终止所有层级的调用。
举个实际调用的例子：你调用外层permutations("23")时，会先触发内层调用permutations("3")，内层函数碰到return [word]只会把["3"]返回给外层函数的perms变量，外层函数后续的循环逻辑还没执行，所以看起来像return之后代码还在运行，实际上运行的是上一层的剩余逻辑，已经return的内层函数不会再执行。

疑问2：递归到最底层时perms的值为['3']，程序是如何从['3']回溯得到上层的['23']的？ #

我们以上层调用是permutations("23")的场景拆解执行流程：

1. 执行perms = permutations(word[1:])，也就是调用permutations("3")，拿到返回值perms = ["3"]
2. 取char = word[0]，值为字符"2"
3. 初始化空列表result存储当前层级的排列结果
4. 遍历perms中的元素，当前只有一个元素"3"
5. 内层循环i的取值范围是range(len(perm)+1)，perm长度为1，所以i会取0、1两个值：
   • 当i=0时：perm[:0]为空字符串，拼接char也就是"2"，再拼接perm[0:]也就是"3"，最终得到"23"，添加到result中
   • 当i=1时：perm[:1]为"3"，拼接"2"，再拼接perm[1:]空字符串，最终得到"32"，添加到result中
6. 当前层级最终返回result = ["23", "32"]，你提到的"23"就是这个步骤生成的其中一个排列结果。

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