Endless Recursion in Python

Question

Full disclosure, this is part of a homework assignment (though a small snippet, the project itself is a game playing AI).

I have this function built into a tree node class:

    def recursive_score_calc(self):
        current_score = self.board
        for c in self.children:
            child_score = c.recursive_score_calc()
            if(turn_color == 1):
                if(child_score > current_score):
                    current_score = child_score
            else:
                if(child_score < current_score):
                    current_score = child_score
        self.recursive_score = current_score
        return current_score

On a tree of depth 1 (a root and some children), it hits the Python recursion limit already. The function is designed to use dynamic programming to build a min-max tree from the bottom up. To be honest, I have no idea why this isn't working as intended, but I am fairly new to Python as well.

Good people of Stack Overflow: Why does this code give me a stack overflow?

The Entire Class in question:

from Numeric import *

class TreeNode:
    children = []
    numChildren = 0
    board = zeros([8,8], Int)
    turn_color = 0 # signifies NEXT to act
    board_score = 0 # tally together board items
    recursive_score = 0 # set when the recursive score function is called

def __init__(self, board, turn_color):
    self.board = copy.deepcopy(board)
    self.turn_color = turn_color
    for x in range (0,7):
        for y in range (0,7):
            self.board_score = self.board_score + self.board[x][y]

def add_child(self, child):
    self.children.append(child)
    self.numChildren = self.numChildren + 1

def recursive_score_calc(self):
    current_score = self.board # if no valid moves, we are the board. no move will make our score worse
    for c in self.children:
        child_score = c.recursive_score_calc()
        if(turn_color == 1):
            if(child_score > current_score):
                current_score = child_score
        else:
            if(child_score < current_score):
                current_score = child_score
    self.recursive_score = current_score
    return current_score

The function that interacts with this (Please Note, this is bordering on the edge of what is appropriate to post here, I'll remove this part after I accept an answer): [It didn't turn out to be the critical part anyways]

Can you show us the code that creates the tree? You are possibly adding self as one of the children. — John La Rooy
– John La Rooy, Commented Feb 18, 2010 at 3:14
All there now. Legal moves is a set of possible moves in the current game state, and SHOULD comprise all of the children of the tree node. — alexwood
– alexwood, Commented Feb 18, 2010 at 3:18

Alex Martelli · Accepted Answer · 2010-02-18 03:21:44Z

This bit of your code:

class TreeNode:
    children = []

means that every instance of the class shares the same children list. So, in this bit:

def add_child(self, child):
    self.children.append(child)

you're appending to the "class-global" list. So, of course, every node is a child of every other node, and disaster is guaranteed.

Fix: change your class to

class TreeNode(object):
    numChildren = 0
    board = zeros([8,8], Int)
    turn_color = 0 # signifies NEXT to act
    board_score = 0 # tally together board items
    recursive_score = 0 # set when the recursive score function is called

def __init__(self, board, turn_color):
    self.children = []
    self.board = copy.deepcopy(board)
    self.turn_color = turn_color
... etc, etc ...

the rest doesn't need to change to fix this bug (though there may be opportunities to improve it or fix other bugs, I have not inspected it deeply), but failing to assign self.children in __init__ is causing your current bug, and failing to inherit from object (unless you're using Python 3, but I'd hope you would mention this little detail if so;-) is just a bug waiting to happen.

SLaks · Accepted Answer · 2010-02-18 03:21:45Z

3

It looks like self.children contains self.

EDIT:

The children property is being initialized to the same array instance for every instance of the TreeNode class.

You need to create a separate array instance for each TreeNode instance by adding self.children = [] to __init__.
The board array has the same problem.

edited Feb 18, 2010 at 3:21

answered Feb 18, 2010 at 3:06

SLaks

891k182 gold badges1.9k silver badges2k bronze badges

3 Comments

alexwood Over a year ago

That's a valid possibility, I don't entirely understand the meaning of "self" other than it spat errors at me until I added it there. Can you elaborate please?

SLaks Over a year ago

You are looping through self.children and calling the same method on each of the children. Recursion would happen if one of the children is the object itself. Can you post your entire program?

jathanism Over a year ago

self is the reference to the class object. As in itself. Get it?

Collectives™ on Stack Overflow

Endless Recursion in Python

2 Answers 2

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related