如何在下面创建递归函数

Question

所以每个人都被表示为一个元组。元组的第一个元素是这个人的名字。的第二个元素元组是一个列表，其中包含此人的子项。每个子级都表示为元组本身。如果一个人没有孩子，他/她的孩子列表是空的。

例如，如果玛丽没有孩子，她被表示为

('Mary', [])

如果简有两个孩子，分别叫尼克和温蒂，而尼克和温迪都没有孩子，那么简就是

('Jane', [('Nick', []), ('Wendy', [])])

如果玛丽和简是弗兰克的孩子，乔恩是玛丽的孩子，而尼克和温蒂是简的孩子，那么弗兰克就代表

('Frank', [('Mary', [('Jon', [])]), ('Jane', [('Nick', []), ('Wendy', [])])])

因此，如何编写一个函数，以按层次顺序返回族中成员的列表？例如

get_family_members(('Mary', []))
['Mary']
get_family_members(('Jane', [('Nick', []), ('Wendy', [])]))
['Jane', 'Nick', 'Wendy']
get_family_members(('Frank', [('Mary', [('Jon', [])]), ('Jane', [('Nick', []), ('Wendy', [])])]))
['Frank', 'Mary', 'Jane', 'Jon', 'Nick', 'Wendy',] 

我的尝试：

def get_family_members(fam_list): 
result = []
if type(fam_list) != list:
fam_list = [fam_list]
for i in range(len(fam_list)):

result.append(fam_list[i][0])

for i in range(len(fam_list)):

if fam_list[i][1] != []:
li = get_family_members(fam_list[i][1])
result += li

return result 

Answer 1

您想要的输出是BFS顺序，递归函数是不合适的。这里有一个非递归的：

def get_family_members(person):
queue = [person]
return [queue.extend(children) or name
for name, children in queue]

不那么黑客的非listcomp版本：

def get_family_members(person):
names = []
queue = [person]
for name, children in queue:
names.append(name)
queue += children
return names

迭代程序版本：

def iter_family_members(person):
queue = [person]
for name, children in queue:
yield name
queue += children
def get_family_members(person):
return list(iter_family_members(person))

或者使用适当的队列：

from collections import deque
def iter_family_members(person):
queue = deque([person])
while queue:
name, children = queue.popleft()
yield name
queue += children