如何在遞歸中使用字典

-1

我有一個遞歸函數，類似於圖G =（V，E）上的DFS，可以找到所有簡單路徑。遞歸是在for循環中，所以當函數返回時它可能會在返回之前再次遞歸。如何在遞歸中使用字典

只需設置圖片：

def algo(M,v): 
    for u in v.neighbors: 
     # do stuff 
     M[u.name] = u  # dictionary 
     algo(M,u)

但是，由於M是一本字典，它被視爲一個可變的對象，這樣當函數返回它並不像它會爲不可變對象恢復微米。完成這個最好的pythonic方法是什麼？

我不認爲在複製庫的deepcopy的功能將是最好的選擇，因爲在文檔中列出的問題引起遞歸循環：https://docs.python.org/2/library/copy.html

如何才能做到這一點？

來源

2016-07-28 channon

你爲什麼要做'M [u.name] = u'？ –

表示像u和v是節點類的實例，M是一個字典，它記錄了我們在'working'分支中遍歷的節點，然後會有一些操作將M添加到整個數據結構中，如果它導致當我們返回 – channon

時，結束目的地，然後M需要恢復好我明白，那麼究竟是什麼問題？或者你只是想找到更好的方法來恢復字典？ –

你只是想插入一項字典，復發，再刪除該項目：

def algo(M, v): 
    for u in v.neighbors: 
     # do stuff 
     M[u.name] = u # temporarily extend dictionary 
     result = algo(M, u) 
     del M[u.name] # clean up 
     # check result

如果你想確保字典是質樸的下一個迭代和recurance，你可以通過增強（淺）複製：

def algo(M, v): 
    for u in v.neighbors: 
     # do stuff 
     # create a new extended dictionary on the fly 
     result = algo({**M, u.name: u}, u)) 
     # no need to clean up afterwards 
     # check result

如果你沒有運行的Python 3.5或更高版本，然後用一個更詳細的語法，是這樣的：

def algo(M, v): 
    for u in v.neighbors: 
     # do stuff 
     # create a new extended dictionary on the fly 
     result = algo(dict(list(M.items()) + [(u.name, u)]), u)) 
     # no need to clean up afterwards 
     # check result

或者你是否想要實現其他目標？

來源

2016-07-29 06:13:05 cdlane

感謝您的回覆。我認爲你的第二個結果是更加期望的，在這可能會變得棘手的是如果我通過數據結構中的節點和遍歷。我認爲該副本最有意義。 – channon

如何在遞歸中使用字典

回答

相關問題