我在這里有點撞墻，我希望stackoverflow上的人可以幫助我。假設我有一個 python 字典，看起來像：

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

對，所以每個鍵都是一個人，對應的值是那個人的父母。我現在想做的就是找出一個人有多少子孫。我有一個非常簡單的函式，可以查找并回傳給定人的直系子女的串列。

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

哪個作業正常。從那里開始，我一直在想，我需要做的就是撰寫一個遞回函式，類似于：

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

但這不起作用。我認為是因為“計數”變數在后代“行”的末尾重置，而不是一個運行總數。例如，如果我運行：

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.

uj5u.com熱心網友回復：

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

uj5u.com熱心網友回復：

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)

uj5u.com熱心網友回復：

You can use treelib to achieve your desired result using the library's methods. Recursive functions are a great way to traverse a tree structure but it is very useful to have a good foundation for them to work on. Depending on what other functions you will be building, treelib can come in very handy indeed to avoid reinventing the wheel and losing time in the process. Especially if what you're working on is a family tree.

Treelib can be installed by pip install treelib.

Code

>>> from treelib import Tree
>>> family = Tree()
>>> family.create_node("Great Grandfather", "Great Grandfather")  # root node
>>> family.create_node("Grandfather", "Grandfather", parent="Great Grandfather")
>>> family.create_node("Uncle", "Uncle", parent="Grandfather")
>>> family.create_node("Father", "Father", parent="Grandfather")
>>> family.create_node("Cousin", "Cousin", parent="Uncle")
>>> family.create_node("Son1", "Son1", parent="Father")
>>> family.create_node("Son2", "Son2", parent="Father")

>>> family.show() # tree.show() prints the tree in human-readable format

Great Grandfather
└── Grandfather
    ├── Father
    │   ├── Son1
    │   └── Son2
    └── Uncle
        └── Cousin

>>> def descendants(person, tree):
...     person_family = tree.subtree(person) # Create a subtree starting with person.
...     return person_family.size() - 1 # Subtracting 1 for Great Grandfather because tree.size() returns the total number of nodes in a tree.

>>> person = "Great Grandfather"
>>> print("{person} has {desc} descendants.".format(person=person, desc=descendants(person, family)))
Great Grandfather has 6 descendants.

>>> person = "Grandfather"
>>> print("{person} has {desc} descendants.".format(person=person, desc=descendants(person, family)))
Grandfather has 5 descendants.

>>> person = "Father"
>>> print("{person} has {desc} descendants.".format(person=person, desc=descendants(person, family)))
Father has 2 descendants.

標籤：python dictionary recursion

上一篇：串列上的遞回除法

下一篇：如何在Python中重復輸入直到滿足特殊條件？