How to carry variable through recursive function in Python?

Question

I was doing some leetcode problems and found that I couldn't carry my variables through recursive functions as I thought I could.

So for example, say I wanted to sum all of nodes of a tree.

So I thought of implementing it this way:

def Sum(root):


    def dfs(root,x):
        if root:
            dfs(root.left, x)
            x.append(root.val)
            dfs(root.right,x)

        return x

    return(sum(dfs(root,x=[])))

And this works. However, say I want to cut down on memory, how come this implementation doesn't work and just returns the root node.

def Sum(root):


    def dfs(root,x):
        if root:
            dfs(root.left, x)
            x+=(root.val)
            dfs(root.right,x)

        return x

    return(sum(dfs(root,x=0)))

Any help or guidance would be appreciated.

Does this answer your question? Python - using a shared variable in a recursive function — user12531529
– user12531529, Commented Dec 14, 2019 at 14:31

chepner · Accepted Answer · 2019-12-14 14:34:08Z

1

x is mutable in your first definition; each call to dfs gets a reference to the same list.

In your second example, x is immutable. The value of x is not modified by the recursive call; x += root.val just updates the local copy of the argument.

Instead, you need to add the return value of dfs directly to x.

def Sum(root):
    def dfs(root, x):
        if root:
            x += dfs(root.left, x)
            x += root.val
            x += dfs(root.right,x)
        return x

    return dfs(root, x=0)

There's no need to define dfs, since you aren't really doing a generic search or walk any more. Just call Sum recursively. Also, the return value is sufficient; you don't need an x argument at all.

def Sum(root):
    if not root:
        return 0
    else:
        return Sum(root.left) + root.val + Sum(root.right)

answered Dec 14, 2019 at 14:34

chepner

538k77 gold badges594 silver badges746 bronze badges

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

1 Comment

fynmnx Over a year ago

That makes sense to me. Thank you for explaining it so clearly.

Collectives™ on Stack Overflow

How to carry variable through recursive function in Python?

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related