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;

我的问题是：为什么我在基本字符串函数中找到的模式在我的字符串排列函数中不成立？

我即将进行面试，我不想因为对递归退出调用感到困惑而让自己尴尬。

PS这是我用来启发字符串排列代码的算法。

标签： pythonalgorithmlistrecursiondata-structures

Answer 1

此处提供的示例使遵循您正在讨论的递归模式有些困难，但是您对引用的直觉基本上是正确的。

通常，当使用列表作为递归函数的参数遍历这样的调用树时，有两种方法。第一种是传入列表的副本，您的第一个示例说明了这一点（使用切片语法[:]，它会复制整个列表）。

第二种方法是从不复制列表，并允许调用堆栈中的函数在整个遍历过程中引用同一个列表。这种方法需要在每次调用解决后恢复列表状态。我们必须这样做以通过防止子节点的突变修改父状态来保留副本的逻辑。

这是您提供的示例函数的快速重写，以遵守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

请注意，打印发生在递归调用开始解析之后，因此我们首先在最终调用打印中看到一个完全填充的列表。如果这令人困惑，请重新排列功能以首先打印 - 位置无关紧要。重要的是每个列表都有一个完全不同的 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都伴随着 a 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

我们可以看到两者都是正确的并且产生了相同的输出。顶部函数创建列表的新副本以传递给子级。通过这样做，它不必担心一旦从孩子返回列表后恢复其状态。这种方法的缺点是每次调用都需要创建一个新列表，效率低下。

另一方面，恢复版本只是简单地传递一个列表并在其上执行所有交换。执行交换后，它将变异列表传递给其子代，子代也对其执行交换，但是一旦其子代对列表进行操作（并最终撤消它们的交换），每个子代都会反转它执行的任何交换。

您显示的代码具有更复杂的状态，但让我们检查一下这段代码：

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是逐字重复在printPermutations. 部分问题在于 Java 是一种比 Python 更冗长的语言，具有非常不同的操作和结构，因此 Java 代码的字面翻译几乎可以保证是非 Pythonic。

更紧密地遵循 Python 风格的一些建议：

• snake_case对于变量和函数。
• if(foo==bar):应该写成if foo == bar:（在运算符周围使用空格，省略不必要的括号）。
• foo=foo+1更清楚的是foo += 1（增量运算符，运算符周围的空格）。
• result.pop(len(result)-1)更清晰result.pop()。
• 无需在变量名中使用类型。Python 没有数组，所以countArraycan be counts、charArraycan becharacters等（复数是表示列表的好方法）。
• 分号是不必要的。

• 在块语句周围使用垂直空格：

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

  应该

  counts = []
  
  for i in range(26):
  

• 遵循 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"))))