Might I ask a question a bout Python recursion? I would like to check the logic behind this, and why this is able to keep updating the results?

The question: A DFS recursion is constructed to append all its children nodes with a specified condition met, e.g., if a node’s end indicator is True, we are going to add this node to the array. This recursion will be used in another function.

2. My code:

    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

The DFS will be called by:

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

The level is a self-defined Trie:

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

I am not sure why this ls will get updated in each for loop iteration, and then pass to the next iteration. I am also surprised that, the following codes are also working:

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

Without returning the ls. I am not sure why this works?

Thanks in advance for your help.

Best,

Naive Python learner

CodePudding user response：

When the list is passed into dfs, it is not the current values in the list that are passed, but instead a reference (a pointer) to the list in memory. There is only one list. This is called pass by reference.

Similarly, when the code assigns the output of dfs to ls, this is literally replacing the pointer to the list object with a pointer to the list object, i.e. it is doing nothing.

There is even an answer related to this in the Python FAQ. There’s some further reading with examples in this answer.

If you want to make your code behave the way you’re thinking it does, you can construct a new list instead of editing the single list. There are some reasons to do this, but with a normal list it is fairly expensive and provides little value. To see it in action, change the append call to:

    ls = ls   [level.info]