访问嵌套列表和字典中的所有元素而无需递归

Question

我有一个由嵌套列表和字典组成的结构。我想对每个元素应用一个函数。如何做到没有递归。

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)

递归版本适用于较小的数据，但是当数据较大时，我会遇到RecursionError异常。

我寻找了消除递归的一般方法，发现这些方法首先依赖于将递归调用转换为尾调用，而我的问题是示例中的递归调用位于循环内。

Answer 1

这种方法将起作用。但是，根据记录，我同意Sven Marnach的观点，即如果您的嵌套超出了递归限制，则数据结构肯定会发生混乱。如果按照斯文猜想，您的数据中存在周期，那么这种方法也会中断。

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)

在解释器外壳中：

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