了解Python中的递归“本地”变量

Question

我刚刚学习了递归，并试图将它应用于一些有趣的，易于理解的方式。 （是的，这整个事情是更好地由三个嵌套for循环完成）

def generate_string(current_string, still_to_place): 
    if still_to_place: 
     potential_items = still_to_place.pop(0) 
     for item in potential_items: 
      generate_string(current_string + item, still_to_place) 
      #print("Want to call generate_string({}, {})".format(current_string + item, still_to_place)) 
    else: 
     print(current_string) 
generate_string("", [['a','b','c'],['d','e','f'],['g','h','i']]) 

如果我注释掉的递归调用，并取消打印，其打印正是我希望它会被调用。然而，只要取消注释，就会发现它调用了一个空的still_to_place数组，即使它仍然具有来自“更高”递归的[d，e，f]，[g，h，i]我认为。

我在理解中错过了什么？谢谢！

Answer 1

我输出了每次迭代generate_string时得到的结果，这就是我得到的。这可能会让所有人感到困惑，因为没有任何行为符合您的预期，但让我来解释一下Python的想法。

#1st time 
current_string = "" 
still_to_place = [['a', 'b', 'c'], ['d', 'e', 'f'], ['g', 'h', 'i']] 

我们通过传递上述数据，但是开始时，当我们在发生什么事走，我们先弹出第一个阵列['a', 'b', 'c']，我们开始通过这个弹出的阵列进行迭代。但是，由于我们叫.pop（0），我们现在只有数组的后半部分，第一递归调用的still_to_place.pop(0)要使其generate_string（）取得

#2nd time 
current_string = "a" 
still_to_place = [['d', 'e', 'f'], ['g', 'h', 'i']] 

这正是在current_string和仍然第一次进行递归调用。现在我们将从头开始再次执行该功能。我们再次调用pop函数，删除第二个数组['d', 'e', 'f']。现在我们只剩下第三个也是最后一个数组了。

#3rd time 
current_string = "ad" 
still_to_place = [['g', 'h', 'i']] 

当我们遍历['g', 'h', 'i']时，因为still_to_place现在是空的。 （我们刚刚弹出了最后一个数组。）任何对generate_string的调用将直接进入else子句，我们将打印出“ad”字符串加上刚刚弹出的数组中的值。

#4th, 5th and 6th time 
still_to_place = [] 
current_string = "adg" 

still_to_place = [] 
current_string = "adh" 

still_to_place = [] 
current_string = "adi" 

我们现在继续最后一次递归调用停止的地方，当我们经历第二次时。这是事情变得混乱的地方。当我们离开current_string = "a"和still_to_place原本是[['d', 'e', 'f'], ['g', 'h', 'i']]，但我们已经从阵列中弹出了所有的东西。你看，数组的行为与数字或字符串不同。阵列的所有版本都共享相同的数据。您只需更改一次数据，然后在数组使用的任何地方更改。 （对象和字典也以这种方式表现）。

因此，所有说still_to_place = []和still_to_place将保留为空的剩余的递归调用。 potential_items仍然有它弹出的数据['d', 'e', 'f']。我们已经执行的步骤＃4，＃5，＃6的“D”的字符串，所以我们可以完成我们留下的

#7th and 8th times 
still_to_place = [] 
current_string = "ae" 

still_to_place = [] 
current_string = "af" 

再次potential_items有['a', 'b', 'c']，我们已经执行“一”。与still_to_place不同，potential_items是一个范围较小的局部变量。如果你知道范围是如何工作的，那么它会使我们为什么可以有多个potential_items，但它与正在使用的still_to_place是一样的。每次我们从still_to_place中弹出一个项目时，我们会将弹出的结果添加到具有有限范围的新潜在项目变量中。 still_to_place对于整个程序来说是全球性的，所以对still_to_place的一个改变会导致在不被预期的情况下的改变。

希望我让事情更加混乱，而不是混乱。留下你需要更多解释的评论。

Answer 2

对，这是预期的行为。原因是每个函数调用之间共享still_to_place。 Python中的可变对象是“通过赋值传递”的，这意味着，如果将一个列表传递给一个函数，那么该函数将共享对SAME列表的引用。 This thread has more detail.

因此，每次调用still_to_place.pop（0）时，都会在每次递归调用中弹出列表。他们都分享完全相同的名单。

这种行为并不总是可取的，通常你希望你的列表是不可变的。在这种情况下，您需要将递归调用传递给数据结构的修改副本。这里是你的代码是什么样子用一成不变的方法：

def generate_string(current_string, still_to_place): 
    if still_to_place: 
     potential_items = still_to_place[0] 
     for item in potential_items: 
      generate_string(current_string + item, still_to_place[1:]) 
      print("Want to call generate_string({}, {})".format(current_string + item, still_to_place)) 
    else: 
     print(current_string) 
generate_string("", [['a','b','c'],['d','e','f'],['g','h','i']]) 

作为一个经验法则，在对象上的方法（例如.pop）将修改它的地方。而且，不同的语言对可变性的处理方式也有所不同，在某些语言中，数据结构总是不可变的。