Maximum recursion depth exceeded in json tree

Question

def get_children(node):
    for child in node['children']:
        yield child 
        for grandchild in get_children(child):
            yield grandchild


for line in f:
    d = json.loads(line)
    child_dic={}
    for child in get_children(d):
        if child not in child_dic.keys():
            child_dic[child["id"]]=1

When I runt his code which is to find the number of children a json tree has, I get an error maximum recursion depth exceeded while calling a Python objec. Please help me with the same.

Answer 1

You have a tree that has more that 998 levels deep:

>>> def build_nested(depth):
...     d = {'children': []}
...     for i in range(depth - 1):
...         d['children'].append({'children': []})
...         d = d['children'][0]
...     return d
... 
>>> try:
...     len(list(get_children(build_nested(998))))
... except RuntimeError:
...     print 'too deep'
... 
997
>>> try:
...     len(list(get_children(build_nested(999))))
... except RuntimeError:
...     print 'too deep'
... 
too deep

Don't use recursion in this case. Use a stack:

def get_children(node):
    stack = [node]
    while stack:
        node = stack.pop()
        stack.extend(node['children'][::-1])
        yield node

This simple approach traverses your tree depth first, like the recursive version, in the same order.

This is only limited by the amount of memory you can give Python:

>>> try:
...     len(list(get_children(build_nested(999))))
... except RuntimeError:
...     print 'too deep'
... 
998
>>> try:
...     len(list(get_children(build_nested(10**6))))
... except RuntimeError:
...     print 'too deep'
... 
999999

This won't help with loading such an object however; json library also has limits:

>>> import json
>>> json.loads('{"a":' * 100000 + '1' + '}' * 100000)
Traceback (most recent call last):
   File "<stdin>", line 1, in <module>
   File "/.../lib/python2.7/json/__init__.py", line 338, in loads
     return _default_decoder.decode(s)
   File "/.../lib/python2.7/json/decoder.py", line 366, in decode
     obj, end = self.raw_decode(s, idx=_w(s, 0).end())
   File "/.../lib/python2.7/json/decoder.py", line 382, in raw_decode
     obj, end = self.scan_once(s, idx)
RuntimeError: maximum recursion depth exceeded while calling a Python object

You can try raising the Python recursion limits with sys.setrecursionlimit(), but be careful. Set it too high and you'll crash the Python interpreter with a segfault instead. Start by looking at sys.getrecursionlimit() and use that as a starting point to increase the limit until you can load your data.

I'm not aware of any other Python JSON library that can handle JSON objects of such depth as you appear to have. jsonlib2 just segfaults, ujson has a hard-coded depth limit of 1024 objects, and demjson gives you a maximum recursion depth error too.