# Puzzling: local variable in recursive function made global?

Daniel Oberski daniel.oberski at gmail.com
Thu Mar 26 17:38:42 CET 2009

```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)
>>>
>>> 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)
>>>
>>>
>>> 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')
>>>
>>>
>>>
>>> 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 = []

"""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

```