python - 为什么退出递归调用时保留一些变量或列表，而另一些则不保留？

Question

我试图理解在退出列表时Python中变量的发生情况。我认为传递给递归函数的所有变量都被推到堆栈上。当您退出堆栈时，这些变量被弹出。不过，我认为情况并非如此。
我创建了一个简单的递归字符串函数来测试这个。当我运行此代码时：

def recursiveArr(n, listB):

    if(n==0):
        return True;
    else:
        listB.append(n);
        listC = listB;
        recursiveArr(n-1, listB[:]);
        print(n)
        print(listB)

我得到以下输出：

1
[4, 3, 2, 1]
2
[4, 3, 2]
3
[4, 3]
4
[4]
[4]

这表明列表和变量n都保留在堆栈中。然后，我将调用修改为recursiveArr(n-1, listB)
我得到了以下输出：

1
[4, 3, 2, 1]
[4, 3, 2, 1]
2
[4, 3, 2, 1]
[4, 3, 2, 1]
[4, 3, 2, 1]
[4, 3, 2, 1]
4
[4, 3, 2, 1]
[4, 3, 2, 1]
[4, 3, 2, 1]

从这两次运行中，我得出的结论是，简单的整数变量始终保持不变，只有在传递列表及其所有值的副本时，列表才会保持不变这就是棘手的地方。
我写了一些代码来打印字符串的排列它可以工作，但我必须减少level，弹出结果数组的最后一个实例，并减少相应的计数值，以便在递归调用后获取变量，即使我只传入结果或计数值数组的值。
代码如下：

def stringify(theList):
    theString = ''

    return theString.join(theList)
def getPerm(charArray, countArray, result, level, lenOrigString): 
    if(level == lenOrigString):
        print(stringify(result))
        return
    for i in range(len(charArray)):
        if (countArray[i]!=0):
            result.append(charArray[i])
            countArray[i] = countArray[i]-1;
            level = level + 1;
            getPerm(charArray, countArray, result, level, lenOrigString)
            result.pop(len(result)-1)
            countArray[i] = countArray[i]+1
            level = level - 1;



    #print("Congratulations! You made it to the second layer!")
def printPermutations(toPerm):
    toPerm = toPerm.lower()
    lenOrigString = len(toPerm)
    charArray = [ord(iChar)-97 for iChar in toPerm]
    countArray = [];
    for iChar in range(26):
        countArray.append(0)
    for i in range(len(charArray)):
        countArray[charArray[i]] = countArray[charArray[i]] + 1
    uniqueChar = [];
    for iChar in charArray:
        if iChar not in uniqueChar:
            uniqueChar.append(iChar)
    uniqueChar = [chr(iChar+97) for iChar in uniqueChar] #keeps track of the possible characters to use
    countArray = list(filter(lambda x: x>0, countArray))#keep track of how many of each character has not been used
    uniqueChar.sort()
    result = [];
    level = 0;
    for i in range(len(uniqueChar)):
        if (countArray[i]!=0):
            result.append(uniqueChar[i])
            countArray[i] = countArray[i]-1;
            level = level + 1;
            getPerm(uniqueChar, countArray, result, level, lenOrigString)#call next level
            result.pop(len(result)-1)
            countArray[i] = countArray[i]+1
            level = level - 1;


printPermutations("ApPLe")

上面的代码运行良好。但是，当我删除调用后数组修改并尝试使用切片获得相同的效果时，我得到的结果比原始字符串长，使它们不是排列。
下面是修改后的代码：

    for i in range(len(uniqueChar)):
        if (countArray[i]!=0):
            result.append(uniqueChar[i])
            countArray[i] = countArray[i]-1;
            level = level + 1;
            getPerm(uniqueChar, countArray[:], result[:], level, lenOrigString)#call next level
            level = level -1;

我的问题是：为什么我在基本字符串函数中找到的模式在字符串置换函数中不成立？
我有面试的机会，我不想让自己感到困惑，因为我对递归退出电话感到困惑。
P.S.This is the algorithm我曾经启发过字符串置换码。

Answer 1

这里给出的例子使得遵循您正在讨论的递归模式有些困难，但是您对引用的直觉基本上是正确的。
通常，当使用列表作为递归函数的参数遍历这样的调用树时，有两种方法。第一种方法是传入列表的副本，第一个示例演示了该副本（使用slice语法[:]，它生成整个列表的副本）。
第二种方法是从不复制列表，并允许call stack中的函数在整个遍历过程中引用同一个列表这种方法要求在每次调用解析后恢复列表状态我们必须这样做，以防止子节点的突变修改父状态，从而保留副本的逻辑。
下面是对您所提供的示例函数的快速重写，该函数将遵守PEP8并删除无用的行（listC = listB;）：

def foo(n, lst):
    if n:
        lst.append(n)
        foo(n - 1, lst[:])
        print(f"n: {n}, lst: {lst}, id: {id(lst)}")

if __name__ == "__main__":
    foo(4, [])

输出：

n: 1, lst: [4, 3, 2, 1], id: 140439070012752
n: 2, lst: [4, 3, 2], id: 140439070012832
n: 3, lst: [4, 3], id: 140439139990576
n: 4, lst: [4], id: 140439072829760

注意，打印发生在递归调用开始解析之后，所以我们首先在final call printing中看到一个完全填充的列表。如果这很混乱，请重新排列函数以首先打印--位置不相关。重要的是每个列表有一个完全不同的id，所以我们总共创建了4个列表。
现在，这里有一个等价的版本（就输出而言），它始终只使用一个列表，并使用上面描述的“状态恢复”技术：

def bar(n, lst):
    if n:
        lst.append(n)
        bar(n - 1, lst)
        print(f"n: {n}, lst: {lst}, id: {id(lst)}")
        lst.pop() # undo the append to restore state in this frame

if __name__ == "__main__":
    bar(4, [])

输出：

n: 1, lst: [4, 3, 2, 1], id: 139793013186800
n: 2, lst: [4, 3, 2], id: 139793013186800
n: 3, lst: [4, 3], id: 139793013186800
n: 4, lst: [4], id: 139793013186800

注意一些事情首先，逻辑输出相同说服自己，每个append都伴随着一个pop来完全恢复父调用的状态，撤消当前堆栈帧中执行的所有突变。其次，请注意，我们有一个列表，整个时间，id为139793013186800。
请记住，在递归调用堆栈中，父调用被搁置，直到所有子调用完全解析为止，因此我们只需要担心当前帧的状态。
现在我们已经看到了这个理论，让我们看看排列法的两个版本：

def print_permute_copy(lst, i=0):
    if i == len(lst):
        print("".join(lst))
    else:
        for j in range(i, len(lst)):            
            cpy = lst[:]
            cpy[i], cpy[j] = cpy[j], cpy[i]
            print_permute_copy(cpy, i + 1)

def print_permute_restore(lst, i=0):
    if i == len(lst):
        print("".join(lst))
    else:
        for j in range(i, len(lst)):            
            lst[i], lst[j] = lst[j], lst[i]
            print_permute_restore(lst, i + 1)
            lst[i], lst[j] = lst[j], lst[i]

if __name__ == "__main__":
    print_permute_copy(list("abc"))
    print()
    print_permute_restore(list("abc"))

输出：

abc
acb
bac
bca
cba
cab

abc
acb
bac
bca
cba
cab

我们可以看出两者都是正确的，并且产生了相等的输出。top函数创建列表的新副本，并将其传递给子级。通过这样做，它不必担心从子级返回列表后恢复其状态。这种方法的缺点是需要为每个调用创建一个新列表，这是低效的。
另一方面，恢复版本只需传递一个列表并对其执行所有交换。在执行交换之后，它会将经过修改的列表传递给同时在其上执行交换的子级，但每个子级在其列表上操作后（并最终撤消其交换）会反转其执行的任何交换。
您所显示的代码的状态要复杂得多，但让我们检查一下这段代码：

for i in range(len(uniqueChar)):
    if (countArray[i]!=0):
        result.append(uniqueChar[i])
        countArray[i] = countArray[i]-1;
        level = level + 1;
        getPerm(uniqueChar, countArray[:], result[:], level, lenOrigString)
        level = level -1;

尝试使用切片失败，因为countArray[i] = countArray[i]-1（更清楚地说是countArray[i] -= 1）不是在副本上执行的，而是在父列表上执行的对于result.append(uniqueChar[i])--这应该在我们准备交给子列表的副本上执行，而不是在父列表上执行。
这是有效的：

for i in range(len(uniqueChar)):
    if countArray[i] != 0:
        cpy = countArray[:]
        cpy[i] = cpy[i] - 1;
        level = level + 1;
        getPerm(uniqueChar, cpy, result + [uniqueChar[i]], level, lenOrigString)
        level = level -1;

请注意，这比原来的“状态恢复”方法效率低，所以我只是为了演示而演示还要注意result + [uniqueChar[i]]使用列表连接并创建一个附加了新项的新列表。随着字符串长度的增加，所有这些列表的拷贝数都会爆炸（时间复杂度是O（n！））。首先）。
为了完整起见，请注意这个函数可以简单地写成list(itertools.permutations(iterable))。即使您选择手工编写它来达到这样的教育目的，也有比所提供的算法简单得多的算法，它使用了很多额外的状态，并且由于在getPerm内部有重复的代码，因此很难解释问题的一部分在于，Java是一种比Python更加冗长的语言，其操作和结构非常不同，因此Java代码的直译几乎可以保证是非Pythonic的。
关于更紧密地遵循Python风格的一些建议：
printPermutations用于变量和函数。
snake_case应写成if(foo==bar):（在运算符周围使用空格，省略不必要的括号）。
if foo == bar:比foo=foo+1更清晰（递增运算符，运算符周围为空白）。
foo += 1比result.pop(len(result)-1)更清晰。
不需要在变量名中使用类型。python没有数组，因此result.pop()可以是countArray，counts可以是charArray，等等（复数是表示列表的好方法）。
分号是不必要的。
在块语句周围使用垂直空格：

countArray = [];
for iChar in range(26):

应该是

counts = []

for i in range(26):

避免使用产生virtually repeated verbatim并希望返回side effects的函数，请遵循itertools：

def permute(lst, i=0):
    if i == len(lst):
        yield lst[:]
    else:
        for j in range(i, len(lst)):            
            lst[i], lst[j] = lst[j], lst[i]
            yield from permute(lst, i + 1)
            lst[i], lst[j] = lst[j], lst[i]

if __name__ == "__main__":
    print(list(permute(list("abc"))))