Python中的无限递归

Question

坦白说，这段内容是我作业的一部分（虽然只是小片段，但整个项目是一个游戏AI）。

我在一个树节点类里写了这个函数：

    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

在深度为1的树上（就是一个根节点和一些子节点），它就已经达到了Python的递归限制。这个函数是用动态规划从底部构建一个最小-最大树的。老实说，我也不知道为什么它没有按预期工作，因为我对Python还很陌生。

亲爱的Stack Overflow的朋友们：为什么这段代码会让我遇到栈溢出的问题？

相关的整个类：

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

与这个函数互动的部分（请注意，这部分内容可能不太适合在这里发布，等我接受了答案后我会删掉这部分）：[不过这部分其实并不是关键内容]

Answer 1

看起来 self.children 里面包含了 self 自己。

编辑：

children 这个属性在每个 TreeNode 类的实例中都被初始化为同一个数组。

你需要为每个 TreeNode 实例创建一个单独的数组，可以在 __init__ 方法里加上 self.children = []。
board 数组也有同样的问题。

Answer 2

你代码中的这一部分：

class TreeNode:
    children = []

意味着这个类的每一个实例都共享同一个 children 列表。所以，在这一段：

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

你是在往这个“类全局”的列表里添加内容。因此，当然每个节点都是其他节点的子节点，这样就会出问题。

解决办法：把你的类改成

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

其他部分不需要改动来修复这个错误（虽然可能有机会改进或者修复其他错误，我没有深入检查），但是在 __init__ 中没有给 self.children 赋值是导致你当前错误的原因，而没有从 object 继承（除非你在用 Python 3，但我希望如果是这样你能提到这个小细节；-)）也是一个潜在的错误。