visit all elements in nested lists and dicts without recursion
<p>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.</p>

<pre><code>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)
</code></pre>

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

<p>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.</p>

<p>This approach will work. For the record, though, I agree with Sven Marnach that there is something <em>definitely fishy</em> 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. </p>

<pre><code>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)
</code></pre>

<p>In the interpreter shell:</p>

<pre><code>$ python -i apply.py
&gt;&gt;&gt; apply(data, lambda x: x + 1)
&gt;&gt;&gt; data
[2, 3, {'a': 2, 'b': {'a': [2, 3, 4]}}, 4]
&gt;&gt;&gt; 
</code></pre>

python recursion data-structures