如何在Python中的递归函数中使用yield

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就会丢失。我该如何再次yield该字典？我得到的只是一个生成器，这不是我想要的。

- Mithil Bhoras

---

但是它返回的是一个生成器对象，而不是一个字典。 - Mithil Bhoras

Answer 1

请注意，递归调用时请使用“yield from”，否则您将忽略递归调用的结果。：

使用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，但本质上只是简单地从额外的循环中产生yield的简称：

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

为实现您想要的数据结构，最好使用生成器(yield)返回元组而不是字典(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

- user2390182

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)元组，并且当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'}

- Martijn Pieters

Answer 3

请注意，您不一定需要使用yield:

def last(d):
  c = [i for b in d.items() for i in ([b] if not isinstance(b[-1], dict) else last(b[-1]))]
  return c

print(dict(last({'a': {'b': {'c': 'd', 'e': 'f'}}})))

输出：

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

- Ajax1234