How do I create a recursive function below?

Question

So each person is represented as a tuple. The first element of the tuple is this person’s name. The second element of the tuple is a list that contains this person’s children. Each child is represented as a tuple itself. If a person has no child, the list of his/her children is empty.

For example, if Mary has no child, she is represented as

 ('Mary', [])

If Jane has two children named Nick and Wendy, and neither Nick nor Wendy has any child, then Jane is represented

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

If Mary and Jane are Frank’s children, and Jon is Mary's child, while Nick and Wendy are Jane's children, then Frank is represented as

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

Thus, how do I write a function that will return a list of members in the family in a hierarchal order? For example

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',]

My attempt:

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

Why a recursive function? That makes no sense. And where is your attempt? — superb rain
– superb rain, Commented Nov 14, 2020 at 15:30
Does [Given a flat list of (parent,child), create a hierarchical dictionary tree [closed] ](stackoverflow.com/questions/45460653/…) answer your question? — itprorh66
– itprorh66, Commented Nov 14, 2020 at 15:32
Just uploaded my attempt. If not recursive function, then what do you recommend? — OnionCoder
– OnionCoder, Commented Nov 14, 2020 at 15:41

superb rain · Accepted Answer · 2020-11-14 15:52:38Z

Your desired output is BFS order, for which a recursive function is inappropriate. So here's a non-recursive one:

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

Less hacky non-listcomp version:

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

Iterator version:

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))

Or with a proper queue:

from collections import deque

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

Collectives™ on Stack Overflow

How do I create a recursive function below?

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related