Python 递归更新一个数组

Question

我可以问一个关于 Python 递归的问题吗？我想看看这背后的逻辑，以及为什么它能够不断更新结果？

问题： DFS 递归被构造为追加满足指定条件的所有子节点，例如，如果节点的结束指示符为 True，我们将把该节点添加到数组中。此递归将在另一个函数中使用。

我的代码：

    def dfs(self, level, ls):
        # if we meet the end of a level, this level’s information will be added to the returned list
        if level.end:
            ls.append(level.info)
        # go further to explore this level’s children, even an end is met. 
        for c in level.child:
            ls = self.dfs(level.child[c], ls)
        return ls

DFS 将由以下人员调用：

ls = self.dfs(self.curr, [])

关卡为自定义Trie：

class Trie:
    def __init__(self):
        self.child = collections.defaultdict(Trie)
        # self.child = {}
        self.end = False 
        self.w = ''
        self.f = 0

我不确定为什么这个 ls 会在每次 for 循环迭代中得到更新，然后传递到下一次迭代。我也很惊讶，以下代码也有效：

        for c in level.child:
            self.dfs(level.child[c], ls)

不返回ls。我不确定为什么会这样？

在此先感谢您的帮助。

最佳，

天真Python学习者

Answer 1

当列表传递到 dfs 时，传递的不是 list 中的当前值，而是对 list 中的引用（指针）记忆。只有一个list。这称为按引用传递。

类似地，当代码将 dfs 的输出分配给 ls 时，这实际上是用指向 list 的指针替换指向 list 对象的指针对象，即它什么都不做。

Python FAQ. There’s some further reading with examples in this answer.

中甚至有与此相关的答案

如果你想让你的代码按照你想象的方式运行，你可以构建一个新的 list 而不是编辑单个 list。这样做有一些原因，但是对于普通的 list 它相当昂贵并且提供的价值很小。要查看实际效果，请将 append 调用更改为：

    ls = ls + [level.info]

Python 递归更新一个数组

Python recursion updates an array

python

recursion

depth-first-search