Python字符串全排列代码异常：Helper函数引发的输出问题排查

我在实现字符串全排列的编程题时，发现左侧的错误代码无法返回正确结果。调试后发现每次调用栈结束后，out数组都会被重置为空列表。但把helper函数里的逻辑移到主函数answer中（右侧正确代码），程序就能正常运行。请问这是什么原因？

错误输出代码 #

def answer(st):
    out = []
    if not st:
        out.append(" ")
        return out 

    head = st[0]        
    last = answer(st[1:]) 
    for perm in last:
        temp = helper(perm,head)
        out.append(temp)

    return out

def helper(perm,head):
    for x in range (len(perm)):
        stt = perm[:x] 
        stt+= head
        stt+= perm[x:]
        return stt 

st = '12'

正确输出代码 #

def answer(st):
    out = []
    if not st:
        out.append(" ")
        return out 

    head = st[0]        
    last = answer(st[1:]) 
    for perm in last:
        for x in range (len(perm)):
            stt = perm[:x] 
            stt+= head
            stt+= perm[x:]
            out.append(stt)
    
    return out

st = '12'

问题根源 #

错误代码里的helper函数逻辑存在致命问题——它的for循环仅执行第一次迭代就直接return，导致每次调用helper只能生成一种插入结果，而非当前字符插入到排列所有位置的全部可能。

以st='12'的执行流程为例：

1. 递归到answer('')，返回[' ']
2. 回到answer('2')，head='2'，遍历last=[' ']并调用helper(' ', '2')。此时helper的循环x=0，生成'2 '后立刻返回，out仅添加该结果，answer('2')最终返回['2 ']
3. 回到最上层answer('12')，head='1'，遍历last=['2 ']并调用helper('2 ', '1')。循环x=0时生成'12 '就返回，out只添加这一个结果，最终仅返回['12 ']，完全漏掉了'21 '这种合法排列。

而正确代码将循环逻辑直接放在主函数中，每次遍历所有插入位置，把所有可能的排列都添加到out数组里，自然能得到正确的全排列结果。

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