Counting all descendants in a family tree (python dictionary)-CodePudding

I'm kind of beating my head against a wall here and I'm hoping that someone on stackoverflow can help me. Let's say I have a python dictionary that looks like:

{
    'Son1': 'Father',
    'Son2': 'Father',
    'Father': 'Grandfather',
    'Grandfather': 'Great Grandfather',
    'Uncle': 'Grandfather',
    'Cousin': 'Uncle',
}

Right, so each key is a person and the corresponding value is that person's parent. All I want to do at the moment is find out how many total descendants a given person has. I've got a pretty simple function that finds and returns a list of a given person's immediate children.

def get_kids(person, dictionary):
    kids = []
    for key in dictionary:
        if dictionary[key] == person:
            kids.append(key)
    return kids

Which works fine. From there, I keep thinking that all I need to do is write a recursive function that's something like:

def descendants(person, dictionary, count):
    kids = get_kids(person, dictionary)
    count = count   len(kids)
    for kid in kids:
         descendants(kid, dictionary, count)
    return count

But this doesn't work. I think because the 'count' variable resets at the end of a 'line' of descendants, instead of being a running total. e.g. If I run:

descendants('Grandfather', familydictionary, 0)

I get back a value of 2 (instead of the hoped-for 5). Presumably, the count reaches 4 when the function is exploring the 'Father' line, but then drops back down to 3 when it explores the 'Uncle' line, instead. And then, I suppose, the count drops all the way back to 2 when the function finds that 'Cousin' has no kids? I often struggle with these kinds of recursion problems. What I want to do is pretty straightforward: check if a person has kids and count them, check if their kids have kids and count them, add them to the total ... keep going until there are no more kids. But I get very muddled when I try to actually, well, write the code that does that. Any help or guidance is appreciated.

CodePudding user response：

You need to actually use the value returned by the recursive call. And passing count in isn't necessary or useful. It's being passed by value, so changing it inside one level of your recursion won't affect the parent calls at all. Rather:

def descendants(person, dictionary):
    count = 0
    for kid in get_kids(person, dictionary):
         count  = 1   descendants(kid, dictionary)
    return count

CodePudding user response：

You need to sum the descendants of each descendant.

>>> tree = {
...     'Son1': 'Father',
...     'Son2': 'Father',
...     'Father': 'Grandfather',
...     'Grandfather': 'Great Grandfather',
...     'Uncle': 'Grandfather',
...     'Cousin': 'Uncle',
... }
>>> def descendants(person: str, tree: dict[str, str]) -> int:
...     return sum(
...         1   descendants(child, tree)
...         for child, parent in tree.items() 
...         if parent == person
...     )
...
>>> descendants("Father", tree)
2
>>> descendants("Grandfather", tree)
5

If you want a list of the actual descendants, you can use the same basic structure but sum the lists instead of the counts. This also makes it easier to visualize how the summing leads to the final solution for the recursive case:

>>> def descendants(person: str, tree: dict[str, str]) -> list[str]:
...     return sum((
...         [child]   descendants(child, tree)
...         for child, parent in tree.items()
...         if parent == person
...     ), [])
...
>>> descendants("Father", tree)
['Son1', 'Son2']
>>> descendants("Uncle", tree)
['Cousin']
>>> descendants("Grandfather", tree)
['Father', 'Son1', 'Son2', 'Uncle', 'Cousin']

i.e.:

descendants("Father", tree) == []   ["Son1"]   ["Son2"]
descendants("Uncle", tree) == []   ["Cousin"]
descendants("Grandfather", tree) == []   ["Father"]   descendants("Father", tree)   ["Uncle"]   descendants("Uncle", tree)