为何将children设为默认空列表会导致树形结构无限递归生成？

尝试构建非二叉树时，给Node类的构造函数设置默认空列表children=[]会导致子节点无限递归生成，调用max_depth时触发RecursionError。

错误代码示例：

class Node:
    # Constructor to create a Node
    def __init__(self, data, children=[]):
        self.value = data
        self.children = children

    @classmethod
    def spawn(cls, data):
        return cls(data)

    def spawn_child(self, data):
        child = self.spawn(data)
        self.children.append(child)


def max_depth(node):
    if len(node.children) == 0:
        return 0
    else:
        depths = []
        for child in node.children:
            depths.append(max_depth(child))
        return np.max(depths)+1


if __name__ == '__main__':
    """ Let us create following example tree
         50
        / \
        30   70
     """

    root = Node(50)
    root.spawn_child(30)
    root.spawn_child(70)
    print(max_depth(root))  # results in RecursionError 

实际生成的树形结构是无限递归形式：

50
        / \
        30    70
       / \   / \
      30 70  30  70
      /   \  /   \
      30  70 30  70
     /     \ /    \
     .     . .     .
     .     . .     .
     .     . .     .

修改构造函数，移除默认参数并在内部初始化空列表后恢复正常：

class Node:
    # Constructor to create a Node
    def __init__(self, data):
        self.value = data
        self.children = []

此时生成正确树形结构，max_depth返回正确值1。

问题原因 #

这是Python中默认参数的初始化机制导致的问题：

• Python的函数默认参数是在函数定义阶段创建的，而不是每次调用函数时重新创建。也就是说，children=[]这个空列表只会在Node.__init__被定义的时候生成一次，之后所有调用Node()（不传入children参数）的实例，都会共享这同一个列表对象。
• 当root.spawn_child(30)创建子节点30时，这个子节点的children属性指向的是和root共享的那个默认列表。接着root.spawn_child(70)把70节点添加到这个共享列表里，此时30节点的children列表里也会出现70节点，同时root的children里有30和70。
• 后续访问子节点的children时，会发现这个列表里已经有其他节点，而这些节点的children又指向同一个共享列表，从而形成无限递归的结构，最终触发RecursionError。

而修改后在__init__内部初始化self.children = []，会在每次创建Node实例时生成一个全新的空列表，每个节点的children都是独立的，不会出现共享的情况，因此树形结构正常。

内容的提问来源于stack exchange，提问作者Kyle