Python recursion updates an array

Question

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.

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

Is `level.child[c]` a dictionary? Please include the class that definition. I'm not sure I fully understood your question, but note that `ls` is being modified in place, so `ls = self.dfs(level.child[c], ls)` is just reassigning `ls` to itself. — joseville, Nov 09 '21 at 01:32
Yes, you are right. I am going to include the class here. Thanks. — Qiang Super, Nov 09 '21 at 13:23
@joseville The question here is that ```ls = self.dfs``` will get itself updating. But why ```self.dfs``` without assigning will also update the ```ls```? Thanks. — Qiang Super, Nov 09 '21 at 13:25

dantiston · Accepted Answer · 2021-11-09T03:01:00.330

2

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]

edited Nov 09 '21 at 03:01

answered Nov 09 '21 at 02:53

dantiston

5,161
2
26
30

Thanks so much for your answer. I think this is what I am looking for. Can we say ```list``` here behaves more likely a global variable, and will get update in each iteration? ```list += [level.info]``` is going to create a new memory space, and assign the value with ```list + [level.info]```. But, ```list.append()``` will only update the value, but not the reference. – Qiang Super Nov 09 '21 at 13:31
Remember that arguments are passed by assignment in Python. (Does it mean the function only takes out the values from the argument? ) Since assignment just creates references to objects, there’s no alias between an argument name in the caller and callee, (The argument in the caller and callee are totally unrelated, like you said the returned ```ls``` is a new object. ) and so no call-by-reference per se. – Qiang Super Nov 09 '21 at 13:37
1

The second StackOverflow answer saves me. The original Python document is not that clear. Awesome. Thanks for your help. – Qiang Super Nov 09 '21 at 13:47
2

Call by assignment is explained by Ned Bachelder here very well: https://www.youtube.com/watch?v=_AEJHKGk9ns. Also, remember to upvote and accept answers that helped you. – joseville Nov 09 '21 at 15:50
Thanks for your help. – Qiang Super Nov 09 '21 at 21:01

Python recursion updates an array

1 Answers1