Python: Pickling highly-recursive objects without using `setrecursionlimit`

Question

I've been getting RuntimeError: maximum recursion depth exceeded when trying to pickle a highly-recursive tree object. Much like this asker here.

He solved his problem by setting the recursion limit higher with sys.setrecursionlimit. But I don't want to do that: I think that's more of a workaround than a solution. Because I want to be able to pickle my trees even if they have 10,000 nodes in them. (It currently fails at around 200.)

(Also, every platform's true recursion limit is different, and I would really like to avoid opening this can of worms.)

Is there any way to solve this at the fundamental level? If only the pickle module would pickle using a loop instead of recursion, I wouldn't have had this problem. Maybe someone has an idea how I can cause something like this to happen, without rewriting the pickle module?

Any other idea how I can solve this problem will be appreciated.

Answer 1

I suppose that most people never use recursive structures of such depth. Since easiest serialization implementations are recursive, you're going to only see them.

If I were you I'd not use an openly recursive data structure here. Instead I'd number every node and use a link table that efficiently translates a number to a node with that number. Every node would refer to other nodes (e.g. its children) via that table, using numbers. A simple property would make this syntactically easy. Beyond that properties, no code dealing with tree traversal would have to change. Node constructor will have to allocate a number and put itself into the link table, which is trivial, too.

The link table might be just a list of nodes, where index into the list serves as the node number; Python lists seem to have efficient access by index. If speed of inserts is important, I'd preallocate a long enough list filled with None; it would not take too much space. If nodes stored their own numbers, this structure would be cheaply traversable in both directions.

As you see, pickling and unpickling such a tree would be trivial at any depth.