Python中的递归，从每个循环中创建几个新实例

Question

我遇到了一个问题，因为我有一个包含类对象的字典，它引用了一个或多个项。字典的关键字是每一项的id。我正在尝试设置一个递归函数，用于查找x步的相邻项目ID链。

它是有效的，但前提是每个"项目"中只有一个项目；adjacent_ items"-变量如果有更多，它仍然只抓住第一个并继续前进；7〃；永远不会被处理。

我对递归函数很陌生，但我觉得应该有一种有效的方法，所以用递归来解决这个问题。任何意见都将不胜感激。

class Item:
def __init__(self, id_num: str, adjacent: list):
self.id = id_num
self.adjacent_items = adjacent

def get_adjacent_x_steps(start: str, item_dict: dict, x: int, wip_set=None):
"""Get adjacent items for x steps"""
if wip_set is None:
wip_set = set()
if x != 0:
x -= 1
for item in item_dict[start].adjacent_items:
wip_set.add(item)
# Todo, only takes first hit, return exits this instance..
return get_adjacent_x_steps(item, item_dict, x, wip_set)
else:
return wip_set

def example():
"""Example items"""
item1 = Item("1", ["4", "7"])
item2 = Item("4", ["5"])
item3 = Item("7", ["5"])
item4 = Item("5", ["8", "17"])
item_dict = {}
for item in (item1, item2, item3, item4):
item_dict[item.id] = item
chained_items = get_adjacent_x_steps("1", item_dict, 2)
print(chained_items)

if __name__ == '__main__':
example()

Answer 1

尝试以下操作：

class Item:
def __init__(self, id_num: str, adjacent: list):
self.id = id_num
self.adjacent_items = adjacent
def get_adjacent_x_steps(start, item_dict, x):
if x == 0 or start not in item_dict:
return [[]]
return [[adj, *lst]
for adj in item_dict[start].adjacent_items
for lst in get_adjacent_x_steps(adj, item_dict, x - 1)]
item1 = Item("1", ["4", "7"])
item2 = Item("4", ["5"])
item3 = Item("7", ["5"])
item4 = Item("5", ["8", "17"])
item_dict = {i.id: i for i in (item1, item2, item3, item4)}
print(get_adjacent_x_steps('1', item_dict, 1))
print(get_adjacent_x_steps('1', item_dict, 2))
print(get_adjacent_x_steps('1', item_dict, 3))

递归发生在列表理解上；在start，获取所有相邻项(for adj in item_dict[start].adjacent_items(，并将函数应用于这些项少一步(get_adjacent_x_steps(adj, item_dict, x - 1)(。然后返回结果列表lst和adj。

输出：

[['4'], ['7']]
[['4', '5'], ['7', '5']]
[['4', '5', '8'], ['4', '5', '17'], ['7', '5', '8'], ['7', '5', '17']]

如果你想得到一组目的地，那么你可以在之后应用一个集合理解：

print({x[-1] for x in get_adjacent_x_steps('1', item_dict, 3)})
# {'17', '8'}