python recursive instance variables sharing data

Question

I'm trying to make a recursive function that creates a tree. Each node holds a state of a tic-tac-toe game, and the children of each node are the next possible moves.

I pass the state of the board to the recursive function. For every possible move I create a copy of the state and then make that move. This new state gets passed to the recursive function.

#XXX
#O O = state [1,1,1,-1,0,-1,1,1,1]
#XXX

playerX = 1
playerO = -1

class node:
    children = [] #holds all the children
    state = [] #holds the state of the board as a list of ints
    def __init__(self,st):
        self.state = st

    def addChild(self,child):
        self.children.append(child) #if only giving birth was this easy

#returns a node with all it's children filled in
#cState is the state for this node
#currentPlayer flips sign every function call
#stateSize is the size of the board
def makeTreeXO(cState,currentPlayer,stateSize):
    newNode = node(cState)
    for i in range(stateSize):
        print "looking at", i, "in", cState
        if(cState[i] == 0): #found an open space
            print "found an empty space"
            newState = cState #create copy of state
            newState[i] = currentPlayer #make the available move
            print "made new state"
            newNode.addChild(makeTreeXO(newState,currentPlayer*-1,stateSize))
    print "Done with this instance"
    return newNode

root = makeTreeXO([1,0,0,1,1,1,1,1,1],playerX,9)

output:

looking at 0 in [1, 0, 0, 1, 1, 1, 1, 1, 1]
looking at 1 in [1, 0, 0, 1, 1, 1, 1, 1, 1]
found an empty space
made new state
looking at 0 in [1, 1, 0, 1, 1, 1, 1, 1, 1]
looking at 1 in [1, 1, 0, 1, 1, 1, 1, 1, 1]
looking at 2 in [1, 1, 0, 1, 1, 1, 1, 1, 1]
found an empty space
made new state
looking at 0 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 1 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 2 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 3 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 4 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 5 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 6 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 7 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 8 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
Done with this instance
looking at 3 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 4 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 5 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 6 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 7 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 8 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
Done with this instance
looking at 2 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 3 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 4 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 5 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 6 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 7 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
looking at 8 in [1, 1, -1, 1, 1, 1, 1, 1, 1]
Done with this instance

From the print statements it's clear that the changes made to the state are being carried back to the parent instance of the function. Does anyone know why?

Answer 1

One problem is this line:

newState = cState

from your comment it looks like you are trying to copy cState, however, you are only copying the reference to the list, not the contents of the list. Thus when you modify newState, you are also modifying cState. What you should have is:

 newState = cState.copy()

EDIT Since this is the accepted answer, the full solution also includes setting self.children = [] in the constructor of node, as mentioned by @thefourtheye

Answer 2

The problem is, you are modifying the class variables, they will be shared by all the objects of a particular class. To fix this, make state and children instance variables like this

class node:
    def __init__(self,st):
        self.state = st
        self.children = []

    def addChild(self,child):
        self.children.append(child) #if only giving birth was this easy

And as per this line,

newState = cState #create copy of state

you are trying to create a copy of cState and store it in newState. Remember, in Python, assignment operator never copies values of one to the other. It simply makes variable on the left side to point to the result of evaluation of the right hand side expression of the assignment statement.

So, what you are actually doing is, making both newState and cState point to the same list. So, if you modify newState, it will affect cState as well. To actually create a copy of the list, you can use slicing operator, like this

newState = cState[:] #create copy of state