如何正確寫入python 2.7中的遞歸過程？

Question

我在Python 2.7以下代碼：

net = {'Freda': [['Olive', 'John', 'Debra'], ['Starfleet Commander', ' Ninja Hamsters', ' Seahorse Adventures']], 'Ollie': [['Mercedes', 'Freda', 'Bryant'], ['Call of Arms', ' Dwarves and Swords', ' The Movie: The Game']], 'Debra': [['Walter', 'Levi', 'Jennie', 'Robin'], ['Seven Schemers', ' Pirates in Java Island', ' Dwarves and Swords']]} 

def get_secondary_connections(network, person): 
    if person in network: 
     for person in network: 
      connections = network[person][0] 
      result = connections 
      for connection in connections: 
       result = result + get_secondary_connections(network, connection) 
       return result 
    return None   
print get_secondary_connections(net, 'Fred') 

當我執行它提供了以下錯誤：

result = result + get_secondary_connections(network, connection) 

RuntimeError: maximum recursion depth exceeded 

請告訴我在哪裏出了錯。

Answer 1

首先，要注意的語義：使用列表[x, y, z]爲這你打算通過循環的集合;使用元組(x, y, z)作爲你想要索引的固定長度集合，這個集合不夠大而不能成爲它自己的類。所以，你應該有

net = { 
    'Freda': (['Olive', 'John', 'Debra'], 
       ['Starfleet Commander', ' Ninja Hamsters', ' Seahorse Adventures']), 
    'Ollie': (['Mercedes', 'Freda', 'Bryant'], 
       ['Call of Arms', ' Dwarves and Swords', ' The Movie: The Game']), 
    'Debra': (['Walter', 'Levi', 'Jennie', 'Robin'], 
       ['Seven Schemers', ' Pirates in Java Island', ' Dwarves and Swords']) 
} 

其次，做一個遞歸問題時，通過你想先用一些例子來發生的，因爲如果你的機器是什麼步驟。處理Freda時，您的第一項任務是加載她的連接Olive, John, Debra。你想用這些做什麼？那麼你要嘗試加載橄欖的連接出現故障，試圖加載約翰的連接出現故障，然後嘗試加載黛布拉的連接，那麼你就必須Walter, Levi, Jennie, Robin.什麼你想在這個名單呢？把它返還？與其他人的朋友串連起來？關於次級連接沒有任何「遞歸」，至少不像人們通常認爲的那樣。換句話說，它似乎與要定義的函數的名稱相匹配：

def get_secondary_connections(network, person): 
    primary_connections, movies = network.get(person, ([], [])) 
    out = [] 
    for friend in primary_connections: 
     secondary_connections, movies = network.get(person, ([], [])) 
     out.extend(secondary_connections) 
    return out 

無需遞歸。我們什麼時候需要遞歸？那麼，如果我們想找到大家誰這個人是由朋友或朋友-的-A-朋友或連接到一個朋友-的-A-朋友-的-A-朋友，然後我們需要探索整個圖和遞歸可能會有所幫助。當然，我們可能也希望這個東西不要包含重複項，所以我們可能需要使用set而不是list。

的首種嘗試可能是：

def get_all_connections(network, person): 
    primary_connections, movies = network.get(person, ([], [])) 
    out = set(primary_connections) # copy this list into an output set 
    for friend in primary_connections: 
     out = out.union(get_all_connections(network, person)) 
    return out 

而且現在你會發現，的確，在排序網絡的錯，這件事情很容易超過最大遞歸深度。這是一個簡單的網絡：

net = { 
    'Alice': (['Bob'], []), 
    'Bob': (['Alice'], []) 
} 

爲什麼會發生這種情況？因爲找到Alice的所有朋友，你需要找到Bob的所有朋友，但要找到Bob的所有朋友，你需要找到Alice的所有朋友。那麼我們如何克服這一點？

我們可以要求所有鮑勃的朋友不包括那些通過愛麗絲來。這將需要一個完整的清單，否則我們只會絆倒其他循環的情況下，如：

net = { 
    'Alice': (['Bob'], []), 
    'Bob': (['Carol', 'Dylan'], []), 
    'Carol': (['Alice'], []), 
    'Dylan': (['Bob'], []) 
} 

注意，當我們問Bob的朋友，我們將遞歸兩個卡羅爾和迪倫，我們需要告訴既他們排除都愛麗絲和鮑勃，因爲已經被處理。因此，導致

def get_all_connections(network, person, excluding=()): 
    if person in excluding: 
     return set() # we exclude by immediately returning the empty set. 
    excluding_us_too = excluding + (person,) 
    primary_connections, movies = network.get(person, ([], [])) 
    out = set(primary_connections) 
    for friend in primary_connections: 
     out = out.union(get_all_connections(network, person, excluding_us_too)) 
    return out 

這個週期檢測策略是由幾個不同的名稱，但通常這裏的元組被稱爲「路徑」，因爲當我們處理任何的迪倫的朋友也說('Dylan', 'Bob', 'Alice')，這意味着我們通過先訪問愛麗絲，然後是鮑勃，然後是迪倫來到迪倫的朋友那裏。

請注意，'卡羅爾'在迪倫的路上無處可尋;有時這可能是一件好事，有時候不會：如果Dylan連接到Carol並且應用到Carol的get_all_connections即使在排除Alice和Bob和Dylan的情況下也會產生一百萬個結果，那麼我們可以預期這兩個結果都會爲Dylan產生相同的結果，然後當我們到達Bob時，我們必須將這兩百萬個結果編成union，這些結果只有一百萬 - 這是很多不必要的工作！

因此，另一個刺將是保持人員處理隊列和我們處理的人員。在這一點上你不會想要使用遞歸，你更願意使用正常的循環結構。

def get_all_connections(network, person): 
    visited, to_visit, out = set(), set([person]), set() 
    while len(to_visit) > 0: 
     visiting = to_visit.pop() 
     visited.add(visiting) 
     connections, movies = network.get(visiting, ([], [])) 
     for friend in connections: 
      out.add(friend) 
      if friend not in visited: 
       to_visit.add(friend) 
    return out 

像這樣的循環可以被轉換成一個高效的遞歸，但不幸的是Python不使這種風格遞歸的效率，使運動的學術，而不是實際的。