Python: 在不使用 `setrecursionlimit` 的情况下对高度递归对象进行序列化

Question

我在尝试把一个非常复杂的树形对象进行序列化时，遇到了一个错误：RuntimeError: maximum recursion depth exceeded。这就像这里的提问者一样。

他通过用sys.setrecursionlimit来提高递归限制解决了问题。但我不想这样做，因为我觉得这更像是个权宜之计，而不是根本的解决办法。我希望能够序列化我的树，即使它里面有10,000个节点。（目前在大约200个节点时就失败了。）

(而且，每个平台的真实递归限制都是不同的，我真的不想打开这个复杂的问题。)

有没有什么办法从根本上解决这个问题？如果序列化模块能用循环而不是递归来处理，我就不会遇到这个问题了。也许有人有办法让我实现类似的功能，而不需要重写序列化模块？

任何其他解决这个问题的想法都非常欢迎。

Answer 1

别用递归了。可以用一个栈（列表/队列）来存放正在处理的节点，然后逐个处理这些节点。

可以参考下面的伪代码：

stack.add(root)
while not list.empty:
    current = stack.pop
    // process current
    for each child of current:
        stack.add(child)

这样就可以了。

Answer 2

为了让理解变得简单，这里有一个完整的例子，只有一个链接来简化内容：

class Node(object):
  linker = [] # one list for all Node instances
  def __init__(self, payload):
    self.payload = payload
    self.__next = None
    self.__index = len(self.linker)
    self.linker.append(self)
  #
  def getNext(self):
    if self.__next is not None:
      return self.linker[self.__next]
  #
  def setNext(self, another):
    if another is not None:
      self.__next = another.__index
    else:
      self.__next = None
  #
  next = property(getNext, setNext)
  #
  def __str__(self):
    return repr(self.payload)


a = Node("One")
b = Node("Two")
c = Node("Three")

b.next = c
a.next = b

# prints "One" "Two" "Three"
print a, a.next, a.next.next

另外，请注意，这种结构可以很容易地包含循环，但仍然可以简单地进行序列化。

Answer 3

我想大多数人都不会用到这么深的递归结构。因为最简单的序列化实现都是递归的，所以你只会看到这些。

如果我是你，我就不会在这里使用公开的递归数据结构。相反，我会给每个节点编号，然后用一个链接表来高效地将编号转换为对应的节点。每个节点会通过这个表，用数字来引用其他节点（比如它的子节点）。这样做的一个简单好处是，语法上会变得容易。除此之外，处理树遍历的代码就不需要改动了。节点的构造函数需要分配一个编号，并把自己放进链接表，这个过程也很简单。

这个链接表可以只是一个节点的列表，列表的索引就是节点的编号；在Python中，列表通过索引访问的效率很高。如果插入速度很重要，我会预先分配一个足够长的列表，里面填充None，这样占用的空间也不会太大。如果节点自己存储它们的编号，这种结构在两个方向上都能便宜地遍历。

如你所见，序列化和反序列化这样一棵树在任何深度下都是非常简单的。