没有 return 语句的递归函数

Question

我有一些数据被插入到嵌套字典中。数据已创建，理论上可以无限深。它可以例如看起来像这样：

data = {'leaves': {'dark': {}, 'green': {'light': {}}, 'without': {'veins': {'blue': {}}}, '5': {}}}

澄清一下：在这个小样本中，表示某植物有'leaves'，'leaves'分别是'dark'、'green'和'without'.在这个例子中 'green' 是 'light' 等等

我想取消嵌套这个字典并将每个键、值组合存储到一个元组中。例如，它可能看起来像这样：

[('leaves', 'dark'), ('leaves', 'green'), ('green', 'light'), ('without', 'veins'), ('leaves', '5'), ('veines', 'blue')]

注意：顺序并不重要。对于那些感兴趣的人，这些元组会被进一步操纵，最终会出现在知识图谱中。

我认为递归函数可以解决这个问题，但我的函数在没有重述的情况下效果最好，没有 return 语句的函数只是一个简单的循环。但是，我无法通过简单的循环使其工作。

edit: doubles 变量是一个全局列表。

我写的函数：

def undict(d):
    for key in d.keys():
        if isinstance(d[key], dict):
            doubles += [(key, k) for k in d[key].keys()]
        undict(d[key]) # Normally: return undict(d[key])

也许任何人都可以提供一些关于如何使其真正递归或使用简单循环的见解？我在这一点上迷路了。

Answer 1

你的方法很不错！

但是请注意，您使用的是全局变量 doubles，而不是局部变量和 return 语句，后者会更简洁。

为了避免 .append 或 .extend 或 += 与列表的问题，一个非常 pythonic 的方法是使用生成器函数，使用关键字 yield 而不是关键字return.

data = {'leaves': {'dark': {}, 'green': {'light': {}}, 'without': {'veins': {'blue': {}}}, '5': {}}}

def undict_to_pairs(d):
    for k,v in d.items():
        if isinstance(v, dict):  # always true with your example data
            for subk in v:
                yield (k, subk)
            yield from undict_to_pairs(v)
        else:
            yield (k,v)          # this statement is never reached with your example data

print(list(undict_to_pairs(data)))
# [('leaves', 'dark'), ('leaves', 'green'), ('leaves', 'without'), ('leaves', '5'), ('green', 'light'), ('without', 'veins'), ('veins', 'blue')]

请注意，对于您的示例数据，isinstance(v,dict) 始终为真。 else 分支永远不会到达。所以这个较短的版本也可以工作：

def undict_to_pairs(d):
    for k,v in d.items():
        for subk in v:
            yield (k, subk)
        yield from undict_to_pairs(v)

print(list(undict_to_pairs(data)))
# [('leaves', 'dark'), ('leaves', 'green'), ('leaves', 'without'), ('leaves', '5'), ('green', 'light'), ('without', 'veins'), ('veins', 'blue')]

让我也建议一个不同的版本，这不是您要求的，但就您的数据而言，我认为它更合乎逻辑：生成长元组而不是对。我从该版本中删除了 isinstance(v, dict)，因为您的数据中的值似乎始终是字典。

def undict_to_tuples(d, acc = ()):
    if d == {}:
        yield acc
    else:
        for k,v in d.items():
            yield from undict_to_tuples(v, acc + (k,))

print(list(undict_to_tuples(data)))
# [('leaves', 'dark'), ('leaves', 'green', 'light'), ('leaves', 'without', 'veins', 'blue'), ('leaves', '5')]

没有 return 语句的递归函数

Recursive function without return statement

python

recursion

dictionary

loops