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
– joseville, Commented Nov 9, 2021 at 1:32
Yes, you are right. I am going to include the class here. Thanks. — Qiang Super
– Qiang Super, Commented Nov 9, 2021 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
– Qiang Super, Commented Nov 9, 2021 at 13:25

dantiston · Accepted Answer · 2021-11-09 03:01:00Z

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 9, 2021 at 3:01

answered Nov 9, 2021 at 2:53

dantiston

5,4312 gold badges28 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Qiang Super Over a year ago

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 Over a year ago

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 Over a year ago

The second StackOverflow answer saves me. The original Python document is not that clear. Awesome. Thanks for your help.

joseville Over a year ago

Call by assignment is explained by Ned Bachelder here very well: youtube.com/watch?v=_AEJHKGk9ns. Also, remember to upvote and accept answers that helped you.

Qiang Super Over a year ago

Thanks for your help.

Collectives™ on Stack Overflow

Python recursion updates an array

1 Answer 1

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related