如何在递归中使用字典

-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

如何在递归中使用字典

回答

相关问题