递归实现分类单元祖先查找的逻辑困惑及技术求助

分类学字典定义 #

tax_dict = {
    'Pan troglodytes': 'Hominoidea', 
    'Pongo abelii': 'Hominoidea',
    'Hominoidea': 'Simiiformes', 
    'Simiiformes': 'Haplorrhini',
    'Tarsius tarsier': 'Tarsiiformes', 
    'Haplorrhini': 'Primates',
    'Tarsiiformes': 'Haplorrhini', 
    'Loris tardigradus': 'Lorisidae',
    'Lorisidae': 'Strepsirrhini', 
    'Strepsirrhini': 'Primates',
    'Allocebus trichotis': 'Lemuriformes', 
    'Lemuriformes': 'Strepsirrhini',
    'Galago alleni': 'Lorisiformes', 
    'Lorisiformes': 'Strepsirrhini',
    'Galago moholi': ' Lorisiformes'
}

递归祖先查询函数 #

# print each step to follow up
def get_ancestors(taxon):
    print('calculating ancestors for ' + taxon)
    if taxon == 'Primates':
        print('taxon is Primates, returning an empty list')
        return []
    else:
        print('taxon is not Primates, looking up the parent')
        parent = tax_dict.get(taxon)
        print('the parent is ' + parent + ' ')
        print('looking up ancestors for ' + parent)
        parent_ancestors = get_ancestors(parent)
        print('parent ancestors are ' + str(parent_ancestors))
        result = [parent] + parent_ancestors
        print('about to return the result: ' + str(result))
    return result

调用get_ancestors('Galago alleni')的逻辑拆解 #

我们一步步走一遍递归执行流程，就能明白为什么返回的是列表：

1. 第一次调用get_ancestors('Galago alleni')：

   • 输入不是Primates，查到父类是Lorisiformes
   • 递归调用get_ancestors('Lorisiformes')

2. 调用get_ancestors('Lorisiformes')：

   • 输入不是Primates，查到父类是Strepsirrhini
   • 递归调用get_ancestors('Strepsirrhini')

3. 调用get_ancestors('Strepsirrhini')：

   • 输入不是Primates，查到父类是Primates
   • 递归调用get_ancestors('Primates')

4. 调用get_ancestors('Primates')：

   • 触发终止条件，返回空列表[]

现在开始回溯返回结果：

• 回到get_ancestors('Strepsirrhini')：
  • parent_ancestors拿到的是空列表[]
  • 生成结果['Primates'] + [] = ['Primates']，返回这个列表
• 回到get_ancestors('Lorisiformes')：
  • parent_ancestors拿到的是['Primates']
  • 生成结果['Strepsirrhini'] + ['Primates'] = ['Strepsirrhini', 'Primates']，返回这个列表
• 回到最初的get_ancestors('Galago alleni')：
  • parent_ancestors拿到的是['Strepsirrhini', 'Primates']
  • 生成结果['Lorisiformes'] + ['Strepsirrhini', 'Primates'] = ['Lorisiformes', 'Strepsirrhini', 'Primates']，返回这个最终列表

核心逻辑：递归的终止条件返回空列表，每一层递归都会把当前父类和子递归返回的列表拼接，最终层层叠加出完整的祖先链列表。

基础递归学习要点 #

• 终止条件：必须明确递归何时停止（这里是遇到Primates返回空列表），否则会触发无限递归
• 问题缩小：每一层调用要把问题规模缩小（这里是找当前分类的父类，逐步逼近终止条件）
• 结果拼接：递归返回时，每一层都要将当前层数据与子问题的结果组合后返回（这里是父类与父类的祖先列表拼接）

内容的提问来源于stack exchange，提问作者Sadcow