visit all elements in nested lists and dicts without recursion

Question

I have a structure consisting of nested lists and dicts. I want to apply a function to every element. How to do it without recursion.

def visit(data, func):
    if isinstance(data, dict):
        for k, v in data.items():
            data[k] = visit(v, func)
        return data
    elif isinstance(data, list):
        for i, v in enumerate(data):
            data[i] = visit(v, func)
        return data
    else:
        return func(data)

The recursive version works for small data, but I hit the RecursionError exception when the data is big.

I looked for general ways to eliminate recursion, the ones I found rely on first transforming the recursive call to a tail call, my problem with this is the recursive call in my example is inside a loop.

You will hit the recursion limit for data structures that are nested more than 1000 levels deep, which seems ridiculous. I suspect what's actually happening is that you have cycles in your data. — Sven Marnach, Sep 19 '16 at 18:12
@Zii8roZi why not just up the recursion limit? `import sys; sys.setrecursionlimit(100000)` — Frito, Sep 19 '16 at 18:13
What do you want to achieve? How should lists and dicts be handled since lists contain elements only while dicts provide key-value-pairs. — albert, Sep 19 '16 at 18:14
While it's always good to help OP with their specific problem, this is also a general audience QA site. Moving between recursive and iterative implementations of basic algorithms is an important skill and a good question for this kind of site. — Bi Rico, Sep 19 '16 at 18:16
@Frito this would be a temporary solution. If the data grows again, I'll have to change it. — Zii8roZi, Sep 19 '16 at 18:25
@albert in lists if the item isn't a dict or a list replace it with `func(item)` — Zii8roZi, Sep 19 '16 at 18:27
@Zii8roZi This isn't about the size of the data; it's about the nesting level. If your data is really that deeply nested, something is wrong with your data structures, and you should fix that problem rather than trying to fix the symptoms. — Sven Marnach, Sep 19 '16 at 21:45

juanpa.arrivillaga · Accepted Answer · 2016-09-20T05:21:17.213

This approach will work. For the record, though, I agree with Sven Marnach that there is something definitely fishy going on with your data structures if you have nesting that is breaking the recursion limit. If as Sven conjectures,you have cycles in your data, this approach will also break.

data = [1,2, {'a':1, 'b':{'a':[1,2,3]}},3]

def apply(data, f):
    stack = []
    stack.append(data)
    while stack:
        data = stack.pop()
        if isinstance(data, dict):
            for k,v in data.items():
                if isinstance(v, (dict,list)):
                    stack.append(v)
                else:
                    data[k] = f(v)
        if isinstance(data, list):
            for i,e in enumerate(data):
                if isinstance(e, (dict,list)):
                    stack.append(e)
                else:
                    data[i] = f(e)

In the interpreter shell:

$ python -i apply.py
>>> apply(data, lambda x: x + 1)
>>> data
[2, 3, {'a': 2, 'b': {'a': [2, 3, 4]}}, 4]
>>>

visit all elements in nested lists and dicts without recursion

1 Answers1

Linked