使用 Python 中的递归函数在家谱中保存后代

Question

我有一个家谱字典，其中 child 的名字作为键，列表中他们爸爸妈妈的名字作为值。

d = { 
'Kevin': ('Tom', 'Marge'), 
'Marge': ('John', 'Mary'), 
'Elle': ('Tom', 'Marge'), 
'Seth': ('Tom', 'Marge'), 
'Mary': ('Carl', 'Elena'), 
'Tom': ('Joseph', 'Alice'), 
'Alice': ('Rob', 'Amy'), 
'John': ('James', 'Elena'), 
'Joseph': ('Adam', 'Emma'), 
'James': ('Nick', 'Maria') }

我需要编写一个递归函数，以便在两个人之间存在后代时 return 为 True。如果有后代，它必须打印出关系链，即：

>>> print("Is there a lineage?", lineage('Amy', 'Kevin', d))
Amy
Alice
Tom
Kevin
Is there a lineage? True

否则如果没有：

>>> print("Is there a lineage?", lineage('Mary', 'Alice', d))
Is there a lineage? False

这就是我目前所知道的。似乎 return True or False 始终如一，但我在弄清楚如何保存两个人之间的路径时遇到了麻烦。

line = []

def lineage(parent, child, d):
    dad, mom = d[child][0], d[child][1]
    
    try:
        if parent in d[child]:
            line.append(parent)
        else:
            try:
                lineage(parent, dad, d)
            except:
                lineage(parent, mom, d)
        
        return True
    
    except:
        return False

我是递归的新手，所以非常感谢任何关于如何处理这个问题的想法或帮助。

Answer 1

当路径存在时，我将你的函数 return 作为路径，而不是 True。
我建议避免在此处 try / except。

的确，尝试访问 d[child] 而不检查 child 是否在 d 中可能会导致异常。但是，这是递归的基本情况；如果基本情况在函数开头用明确的 if 明确标识，而不是在函数末尾没有解释的模糊“发生了一些异常”，那么您的代码将更容易理解。

def lineage(parent, child, d):
    if parent == child:
        return [child]
    elif child not in d:
        return False
    else:
        dad, mom = d[child][0], d[child][1]
        path_via_dad = lineage(parent, dad, d)
        if path_via_dad:
            path_via_dad.append(child)
            return path_via_dad
        else:
            path_via_mom = lineage(parent, mom, d)
            if path_via_mom:
                path_via_mom.append(child)
                return path_via_mom
            else:
                return False

这是一个更短的等效版本，它依赖于 python 中逻辑运算符 or 的特定行为：

def lineage(parent, child, d):
    if parent == child:
        return [child]
    elif child not in d:
        return False
    else:
        dad, mom = d[child][0], d[child][1]
        path = lineage(parent, dad, d) or lineage(parent, mom, d)
        if path:
            path.append(child)
        return path

测试：

>>> lineage('Amy', 'Kevin', d)
['Amy', 'Alice', 'Tom', 'Kevin']
>>> lineage('Mary', 'Alice', d)
False

使用 Python 中的递归函数在家谱中保存后代

Save descendence in family tree with a recursive function in Python

recursion

dictionary

family-tree