如何在Python中的递归函数中产生

Question

所以我有一本字典:

{'a': {'b': {'c': 'd', 'e': 'f'}}}

我需要创建一个字典如下:

{'c':'d', 'e','f'}

它可以更深入到任何级别,但我应该始终获得最大深度的键值对.所以我写了一个函数:

def boil_down_array(key, data):
    if type(data) == dict:
        for key, item in data.items():
            boil_down_array(key, item)
    else:
        yield {key:data}

现在的问题是,一旦进入递归,yield就会丢失.如何再次出示该词典？我得到的只是一台不是我想要的发电机.

Answer 1

使用yield from您的递归调用,否则你只是忽略了递归调用的结果:

def boil_down_array(key, data):
    if type(data) == dict:
        for key, item in data.items():
            yield from boil_down_array(key, item)
    else:
        yield {key: data}

这只适用于Python> 3.3,但基本上只是简单地从额外的循环中产生:

for key, item in data.items():
    for x in boil_down_array(key, item):  # just exhaust the recursive generator
        yield x  # and "re-yield" what it produces

为了实现所需的数据结构,最好不要使用对dicts,而是可以更容易地将结果转换为结果dict:

yield key, data

然后你就可以使用它:

result = dict(boil_down_array(None, input_dict))

更简单的递归方法只会返回一个完整的dict:

def boil_down_nested(dct):
    result = {}
    for k, v in dct.items():
        if isinstance(v, dict):
            result.update(boil_down_nested(v))
        else:
            result[k] = v
    return result

Answer 2

您忽略了递归调用产生的生成器对象：

for key, item in data.items():
    boil_down_array(key, item)  # creates a generator object

所以递归调用实际上并未执行（生成器中的代码永远不会为该调用执行）。

你要使用yield from到迭代委派到该呼叫：

for key, item in data.items():
    yield from boil_down_array(key, item)

yield from将控制从当前生成器转移到表达式之后yield from产生的迭代器；这是你的递归生成器。

yield from需要 Python 3.3 或更新版本。如果您使用的是 Python 2 或更旧的 Python 3 版本，您还可以添加另一个循环来显式生成迭代产生的每个结果：

for key, item in data.items():
    for result in boil_down_array(key, item):
        yield result

我也会使用isinstance(data, dict)而不是使用type(...) ==, 来允许子类：

def boil_down_array(key, data):
    if isinstance(data, dict):
        for key, item in data.items():
            yield from boil_down_array(key, item)
    else:
        yield {key: data}

请注意，您的代码实际上并未生成字典作为输出。它生成一个可迭代的单键值字典：

>>> d = {'a': {'b': {'c': 'd', 'e': 'f'}}}
>>> list(boil_down_array('v', d))
[{'c': 'd'}, {'e': 'f'}]

key来自最外层调用的参数在这里也是多余的，因为您将其替换为当前迭代的键。

如果您确实需要坚持使用生成器函数，那么至少生成(key, value)元组并且当值不是字典时不要打扰递归（因此在递归之前进行测试），以消除传递键的需要；剩下的data参数现在被假定为一个字典，总是：

def boil_down_nested(data):
    for key, value in data.items():
        if isinstance(value, dict):
            yield from boil_down_nested(value)
        else:
            yield (key, value)

并使用dict(boil_down_nested(input_dict))生成器现在输出的键值元组生成新字典：

>>> next(boil_down_nested(d))  # first resulting key-value pair
('c', 'd')
>>> dict(boil_down_nested(d))  # all key-value pairs into a dictionary.
{'c': 'd', 'e': 'f'}

无需递归，您可以使用堆栈来跟踪仍要处理的嵌套字典；这使得直接输出字典变得更加容易：

def boil_down_nested_dict(d):
    stack = [d]
    output = {}
    while stack:
        for key, value in stack.pop().items():
            if isinstance(value, dict):
                stack.append(value)  # process this value next
            else:
                output[key] = value
    return output

不再dict()需要单独调用：

>>> boil_down_nested_dict(d)
{'c': 'd', 'e': 'f'}