瞭解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）將修改它的地方。而且，不同的語言對可變性的處理方式也有所不同，在某些語言中，數據結構總是不可變的。