CODEWITHSUNDEEP
pythonlistpointersscope
Ian Zhang
Ian Zhang

Reputation: 432

Python: how does list work within recursion

I'm trying to print the path(from root to leaf node) for a binary tree. I was trying to use a list as input to record the path and return it.

However, the return value is empty, I can see the path is being generated correctly, by printing the path at the recursion function.

Case 1:

Input:
res = printPath(root, node,[]) 

Output:
res = []

My question is, how does list work with recursion, how does python handle the scope of it?

Case 2:

Input:
p_ = []

res = printPath(root, node, p_)

Output:
res != []

also res is not equal to the final path, which inside the recursion, can you please let me know why is that. Eg, path = [3, 5], res = []

res is not empty but it will have some middle value of the recursion. I guess, in this case, the list is treated as a pointer.

If you can let me know the difference between these 2 cases, it would be great.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def printPath(self, root, node, path):
        if root:
            # print root.val, node
            if root.val == node:
                path.append(node)
                print path
                return path
            if root.left:
                path.append(root.val)
                self.printPath(root.left, node, path)
            if root.right:
                path.append(root.val)
                self.printPath(root.right, node, path)

    def lowest_main(self, root, p):
        # print root.val, p
        p_ = []
        print self.printPath(root, 5, p_)
        # print p_

Upvotes: 0

Views: 100

Answers (2)

fountainhead
fountainhead

Reputation: 3722

Case 1:

Here, you are passing a list object having zero elements, as argument to the "root invocation" of printPath().

Inside this invocation, that empty list can be accessed with the parameter called path.

During the execution of the function, that empty list would become non-empty.

But once you've exited this "root invocation" of the function, that parameter called path, which is referring to the (now non-empty) list, goes out of scope.

Now, you are left with no other variable (or name) referring to that non-empty list, so there is no way for you to actually look at the non-empty path and celebrate.

Case 2:

Here also, you are passing an empty list object to your "root invocation" of printPath(). But the difference is that even before you invoke printPath(), you have ensured that there is one more variable (or name) called p_, which is pointing to the same empty list object that you are passing to the "root invocation". As with Case 1, inside the invocation, the empty list object is accessed with the parameter name path. As with Case 1, this empty list will become non-empty during the execution. As with Case 1, when the root invocation eventually completes execution and returns control, the parameter named path which was pointing to the (now non-empty) list object, will go out of scope, but you are still left with one more variable called p_, pointing to the same (now non-empty) list object.

Reason why print self.printPath(root, 5, p_) prints None:

Let's take a simple tree, in which the root node has a value of 0, and the left child has a value of 5. Assume that there are no other nodes in the tree.

What happens in your root invocation of printPath():

You will first check if root.val == node. The test will fail.

You will next check if root.left. The test will pass. You will enter that if block, append 0 to path, and make your second invocation of printPath(). Now, carefully note the fact that the second invocation is made from within the first invocation. The first invocation has not yet completed. In fact, at that instant, the first invocation as well as the second invocation are both in a state of having partially executed. Correct? And the first invocation and second invocation at two different line numbers. The first invocation is at the line where printPath() is invoked for the left child, and the first invocation is just about to start executing at the first line of printPath(). Correct?

What happens next?

The second invocation also checks if root.val == node. This time, the test succeeds, and it enters the if block, appends 5 to path, and returns path.

But where does this returned value go? To the place where this second invocation happened ! Which, if you remember, is another line in printPath(). At that line, you are invoking printPath(), but not capturing its return value in any variable -- you are just ignoring its return value. So, the 0 5 string returned by the second invocation is being ignored. The execution of the first invocation continues until it reaches the last line of printPath(). At the last line, there is no other return statement. So, in the absence of an explicit return statement, any Python function will return None. So, this first invocation will return None, to the place where your first invocation happened (I think that is in lowest_main()).

The first invocation is printing this None value.

How to correct:

To correct this, please change the following line:

self.printPath(root.left, node, path)

to this:

return self.printPath(root.left, node, path)

Similarly, please change the following line:

self.printPath(root.right, node, path)

to this:

return self.printPath(root.right, node, path)

Upvotes: 1

U13-Forward
U13-Forward

Reputation: 71610

Because:

>>> [].append(2)
>>> []
[]
>>> l=[]
>>> l.append(2)
>>> l
[2]
>>>

Because [] isn't stored anywhere, so won't update any variable, that's why.

[] would be kept in memory after append, but no way to access it.

Upvotes: 1

Related Questions