Puzzling: local variable in recursive function made global?

[andrew cooke]

it's not global, it's mutable.  you are passing THE SAME FRICKING OBJECT
to is_terminal and appending values to it.

instead, make a new copy:

   branch.next.is_terminal(list(seen_nodes))

sorry for the shouting, but someone asks this EVERY DAY AND I CAN'T TAKE
ANY MORE.

andrew



Daniel Oberski wrote:
> Hello all,
>
>
> I wrote this function to recurse through a tree structure of Nodes
> connected by Branches.
>
> I use a local variable seen_nodes to mark off Nodes already seen by the
> function (i.e. add them to a list).
>
> What is puzzling me is that the local variable seen_nodes seems to be
> made global by Python. That is, Nodes from function calls 'lower' in the
> recursion order are still there after return. Even Nodes added by
> completely unrelated function calls on a different graph in the same
> program are in seen_nodes. This can only mean the variable is global, but
> I absolutely did not expect it nor do I understand why that should be.
>
> The solution was to delete seen Nodes before return, so I do not have a
> problem with the program. I am just very surprised by this behaviour!
>
> I was wondering if anybody can explain to me why the interpreter should
> behave in this way and where this is documented. The complete program
> with usage examples as a doctest is listed below.
>
> Thank you very much in advance,
>
> Daniel
>
>
> ----------------- graph.py -------------------
> """
> # The null graph:
>>>> Node('null node').is_terminal()
> 1
>
>>>> # An infinitely recursing graph: node1 --> node2 --> node1 --> ...
> ... n1 = Node("node1")
>>>> n2 = Node("node2")
>>>> b1 = Branch(next = n2)
>>>> b2 = Branch(next = n1)
>>>> n1.add(b1)
>>>> n2.add(b2)
>>>>
>>>> print "Node 1 terminal?"
> Node 1 terminal?
>>>> print n1.is_terminal()
> 0
>
>>>> # A simple acyclical graph:
> ... #              --> n3
> ... #  n1 --> n2 --|
> ... #              --> n4 --> n5
> ... n1 = Node('Start')
>>>> n2 = Node('Second')
>>>> n3 = Node('Third, first')
>>>> n4 = Node('Third, second')
>>>> n5 = Node('Fourth from Third, second')
>>>>
>>>> b1 = Branch(next = n2)
>>>> b2 = Branch(next = n3)
>>>> b3 = Branch(next = n4)
>>>> b4 = Branch(next = n5)
>>>>
>>>> n1.add(b1)
>>>> n2.add(b2)
>>>> n2.add(b3)
>>>> n4.add(b4)
>>>>
>>>> print n1.is_terminal()
> 1
>
>>>> # terminal graph with a cycle
>>>> #    -> b1 ->  b2 -> b3
>>>> # a -|
>>>> #    -> c1 -> c2 -> b1
>>>>
>>>> a = Node('a')
>>>> b1 = Node('b1')
>>>> b2 = Node('b2')
>>>> b3 = Node('b3')
>>>> c1 = Node('c1')
>>>> c2 = Node('c2')
>>>> c3 = Node('c3')
>>>>
>>>> a.add(Branch(next = b1))
>>>> b1.add(Branch(next = b2))
>>>> b2.add(Branch(next = b3))
>>>>
>>>> a.add(Branch(next = c1))
>>>> c1.add(Branch(next = c2))
>>>> c2.add(Branch(next = b1))
>>>>
>>>> print a.is_terminal()
> 1
>
> """
>
> # Total number of times the recursive function is_terminal has been
> called:
> num_calls = 0
>
>
> class Node:
>
>     def __init__(self, name):
>         self.name = name
>         self.branches = []
>
>     def add(self, branch):
>         """Adds a branch to this node."""
>         self.branches.append(branch)
>
>     def is_terminal(self, seen_nodes = []):
>         """Recurses from this node to see if *all* its branches eventually
>             end up in a terminal node. Calling this on the source node of
> a
>             graph establishes that the graph is terminal.
>            Returns 1 if yes, 0 if no. """
>         global num_calls # For debugging
>         num_calls += 1
>
>         if self in seen_nodes: # deja vu, we are going in circles
>             return 0
>         seen_nodes.append(self)
>         # unfortunately seen_nodes is automatically made global by the
> Python
>         # interpreter :-(. Instead of using black scoping magic I just
> delete self
>         # from seen_nodes later on.
>
>         num_terminal = 0
>         for branch in self.branches:
>             if branch.next: # Recurse through this branch
>                 num_terminal += branch.next.is_terminal(seen_nodes)
>             else: # Found the terminal node ('sink')
>                 num_terminal += 1
>         # necessary because of Python's weird scoping rules (see above):
>         seen_nodes.remove(self)
>
>         if num_terminal == len(self.branches): # all branches are terminal
>             return 1
>         else: # at least one branch is not terminal or no branches
>             return 0
>
>
> class Branch:
>     """A branch is an edge. It is found in a Node and points to what we
> can only
>     hope is another Node."""
>     next = False
>
>     def __init__(self, next = False):
>         self.next = next
>
> if __name__ == "__main__":
>     import doctest
>     doctest.testmod()
>
>     print "is_terminal() was called a total of %d times."  % num_calls
> --
> http://mail.python.org/mailman/listinfo/python-list
>
>