Zii8roZi - 1 year ago 48

Python 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.

Answer Source

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. Although, I suppose if you had a list of ~1000 lists, that would also break the recursion limit...

```
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]
>>>
```