如何在没有递归的情况下展平嵌套字典？

Question

我遇到了一个可以使字典变平的函数：

def flatten(dictionnary, container=None):
    if container is None:
        container = []
    for k, v in dictionnary.items():
        container.append(k)
        if v:
            flatten(v, container)
    return container

为了测试它，我创建了一个dictionnay，它嵌套了n次，如下所示：

^{pr2}$

函数在n小于999时工作，否则将达到递归限制：

RecursionError: maximum recursion depth exceeded while calling a Python object

因此，经过一点搜索，似乎any recursive function can rewritten to iteration但我不知道如何才能为函数实现，我必须产生相同的结果。在

我在玩这个游戏时遇到的另一个奇怪的问题是，如果我为n >= 998尝试下面的代码：

nesteddict = {}
for i in range(n, 0, -1):
    emptydict = {}
    emptydict[i] = nesteddict
    nesteddict = emptydict
print(nesteddict)

我得到递归错误：

RecursionError: maximum recursion depth exceeded while getting the repr of an object

这很奇怪，因为我没有看到任何递归。在

Answer 1

与其将dict保存在堆栈中，不如将项的迭代器保存在堆栈中。在

这样，您就可以恢复iterator on命令。在

另外，由于您要按顺序暂停和恢复迭代器的执行，因此结果将始终与dict的顺序一致

顺便说一下，@iBug，dict是根据Python 3.7的规范进行排序的

def flatten(dictionary, container=None):
    if container is None:
        container = []
    iterators = []
    iterator = iter(dictionary.items())
    while True:
        for k, v in iterator:
            container.append(k)
            if v:
                # Save the current iterator for later
                iterators.append(iterator)
                # Run on the new dict
                iterator = iter(v.items())
                break

        # Current iterator is done, fetch the next one
        else:
            try:
                iterator = iterators.pop()
            except IndexError:
                return container

print(flatten({1: None, 2: {3: None, 4: None}, 5: None}))
[1, 2, 3, 4, 5]

Answer 2

如果你想在没有递归的情况下完成它，那是不可能的。在

这里是递归错误的解决方案。在

基于doc of python. 您可以使用sys.getrecursionlimit()查看递归的限制。您也可以使用sys.setrecursionlimit()来设置上限。在

Answer 3

从逻辑上讲，嵌套字典（和列表）是一种递归，所以如果你想避免逻辑递归，那是不可能的。在

但是，由于递归只是递归，您可以保留自己的堆栈并在循环中模拟它：

def flatten(dct, c=None):
    if c is None:
        c = []
    stack = [dct]
    while stack:  # non-empty
        d = stack.pop()
        for k, v in d.items():
            c.append(k)
            if v:
                stack.append(v)
    return c

这个函数很好地模拟了函数递归的行为，有一个自定义堆栈。在

有一个潜在的缺点：理论上，字典

^{pr2}$

应展平为[1, 2, 3, 4, 5]，而此方法将给出[1, 2, 5, 3, 4]。这很像DFS搜索与BFS在图形上的搜索。在

但是，因为字典是无序的，这应该不是什么大问题（除非您使用collections.OrderedDict），这就是为什么我说这是一个潜在的缺点。在