时间戳

首页 > 解决方案 > Python递归更新数组

python - Python递归更新数组

问题描述

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

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

  1. 我的代码：
    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 学习者

标签： pythonrecursiondepth-first-search

解决方案

当列表传入 时，传递dfs的不是 中的当前值list，而是指向list内存中的引用（指针）。只有一个list。这称为通过引用传递。

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

Python FAQ中甚至有一个与此相关的答案。在这个答案中有一些进一步的阅读示例。

如果你想让你的代码按照你想象的方式运行，你可以构造一个 newlist而不是编辑单个list. 这样做有一些原因，但在正常情况list下，它相当昂贵且价值不大。要查看它的实际效果，请将append调用更改为：

    ls = ls + [level.info]

推荐阅读