# Problem with arrays in a recursive class function

Aaron Scott aaron.hildebrandt at gmail.com
Thu Aug 20 22:02:57 CEST 2009

```I have a list of nodes, and I need to find a path from one node to
another. The nodes each have a list of nodes they are connected to,
set up like this:

class Node(object):
def __init__(self, connectedNodes):
self.connectedNodes = connectedNodes

nodes = {
1: Node([4]),
2: Node([3]),
3: Node([2, 4, 5]),
4: Node([1, 6, 3]),
5: Node([3, 7]),
6: Node([4, 9]),
7: Node([5, 8]),
8: Node([7, 9]),
9: Node([6, 8])
}

I made a quick brute-force pathfinder to solve it (in this case, a
path from node 1 to node 9). Here it is:

class PathFind(object):
def __init__(self, source, destination):
self.source = source
self.destination = destination
self.solved = []
def Search(self):
self.PathFind([self.source])
if self.solved:
print "Solutions: "
for i in self.solved:
print "\t" + str(i)
else:
print "Couldn't solve."
def PathFind(self, trail):
location = trail[-1]
if location == self.destination:
self.solved.append(trail)
print "Solution found: " + str(trail)
else:
possibilities = []
for i in nodes[location].connectedNodes:
if not i in trail: possibilities.append(i)
for i in possibilities:
trail.append(i)
self.PathFind(trail[:])
if not possibilities:
print "Dead end: " + str(trail)

finder = PathFind(1, 9)
finder.Search()

Unfortunately, it doesn't seem to be giving me the result I was after.
This is the output:

Solution found: [1, 4, 6, 9]
Dead end: [1, 4, 6, 3, 2]
Solution found: [1, 4, 6, 3, 2, 5, 7, 8, 9]
Solutions:
[1, 4, 6, 9]
[1, 4, 6, 3, 2, 5, 7, 8, 9]

The problem is the array trail[], which seems to survive from instance
to instance of PathFind(). I thought that by calling self.PathFind
(trail[:]), I was creating a new copy of trail[], but obviously
something isn't running like I expected. Is there something I'm
misunderstanding here, or is there just a stupid bug in my code I
haven't caught?

```