about using global variable or local variable in recursion

Question

Hi recently I encountered a subtle issue while trying to build a Trie function:

def search(self, word):
    def dfs(node, word):
        if not word:
            if node.end:
                self.res = True
            return
        if word[0]!='.':
            node = node.next.get(word[0])
            if not node:
                return
            dfs(node, word[1:])
        else:
            for n in node.next.values():
                dfs(n, word[1:])

    curr = self.root
    self.res = False
    dfs(curr, word)
    return self.res

This works.

But this doesn't:

def search(self, word):
    def dfs(node, word, res):
        if not word:
            if node.end:
                res = True
            return
        if word[0]!='.':
            node = node.next.get(word[0])
            if not node:
                return
            dfs(node, word[1:], res)
        else:
            for n in node.next.values():
                dfs(n, word[1:], res)

    curr = self.root
    res = False
    dfs(curr, word, res)
    return res

I don't get it why the latter approach, which passes a variable along the recursion instead of using a global variable, does not work.

Because assigning to a parameter doesn't change the variable at the call site. Though you don't need a "global" in either case, as `dfs` is a nested function — UnholySheep, Dec 19 '18 at 18:21
because the value of `res` changes during each recursive call and is not stored anywhare, unlike `self.res`. You can make the second example work correctly byassigning the `res` to some global state — Nikos M., Dec 19 '18 at 19:03

AShelly · Answer 1 · 2018-12-19T19:03:01.047

The issue has to do with the way objects are handled and passed to functions in Python. Inside the function res is a new variable, initialized to the object the function was called with. But assigning res = True inside the function just means res now names a different object. It doesn't change the object in the callers scope. As a simple example imagine this code:

def Test(result):
  if (something):
     result = True

Test(False) 

#what would I check to see if result changed?
#is the global False constant now equal to True?

I can see a few ways around your problem.

Return res from the function. res = dfs(n, word, res)
Pass an array, whose contents can be modified inside a function. res = [True] would make res name a different array, but res[0] = True changes a value inside the original array.

Like this.

res = [False]
dfs(n, word, res)
...
return res[0]

3- Use the nonlocal keyword to use a variable in a higher scope:

def search(self, word):
    res = False
    def dfs(node, word):
        nonlocal res #this is the same object as the `res` in `search`
        if not word:
            if node.end:
                res = True #this will modify `res` as intended
        ... #rest of dfs function

    dfs(self.root, word)
    return res

see https://stackoverflow.com/q/52548178/10396 and related questions to understand pass-by-value vs. pass-by-reference. — AShelly, Dec 19 '18 at 18:33
*Everything* in Python is passed by value. The issue is whether you try to mutate the object referenced by that value (where mutation is distinct from simple assignment to a name.) — chepner, Dec 19 '18 at 18:34
Since `dfs` is a nested function in OPs code you should also mention the option of using `nonlocal res` — UnholySheep, Dec 19 '18 at 18:34

about using global variable or local variable in recursion

1 Answers1