Puzzling: local variable in recursive function made global?

[Daniel Oberski]

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