关于递归的问题 - 查找分类法的父级

Question

我有一个字典：

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'
}

我在Python中写了这段代码：

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

我得到了这些结果：

calculating ancestors for Galago alleni
taxon is not Primates, looking up the parent
the parent is Lorisiformes
looking up ancestors for Lorisiformes
calculating ancestors for Lorisiformes
taxon is not Primates, looking up the parent
the parent is Strepsirrhini
looking up ancestors for Strepsirrhini
calculating ancestors for Strepsirrhini
taxon is not Primates, looking up the parent
the parent is Primates
looking up ancestors for Primates
calculating ancestors for Primates
taxon is Primates, returning an empty list
parent ancestors are []
about to return the result: ['Primates']
parent ancestors are ['Primates']
about to return the result: ['Strepsirrhini', 'Primates']
parent ancestors are ['Strepsirrhini', 'Primates']
about to return the result: ['Lorisiformes', 'Strepsirrhini',
'Primates']
['Lorisiformes', 'Strepsirrhini', 'Primates']

也许这是个简单的问题，但我完全搞不懂。我不知道为什么结果会是一个父母的列表。我以为结果应该是一个值，并且在递归循环结束时运行。我知道这是一个基本的递归，有没有人能帮我一下？你们有没有什么有用的参考资料可以帮助我？谢谢！

Answer 1

如果我们把所有的打印部分去掉，你的函数基本上就和下面这个一样。我在条件语句中使用了return，这样可以避免过多的缩进。

>>> def get_ancestors(taxon, stop_on='Primates'):
...     if taxon == stop_on: return []
...     parent = tax_dict.get(taxon)
...     if not parent: return []
...     return [parent] + get_ancestors(parent, stop_on)
...
>>> get_ancestors('Galago alleni')
['Lorisiformes', 'Strepsirrhini', 'Primates']
>>> get_ancestors('Tarsius tarsier')
['Tarsiiformes', 'Haplorrhini', 'Primates']

现在，如果你不一定想要一个列表，你可以使用yield来创建一个生成器，这样可以根据需要生成父级。

>>> def get_ancestors(taxon, stop_on='Primates'):
...     if taxon == stop_on: return
...     parent = tax_dict.get(taxon)
...     if not parent: return
...     yield parent
...     yield from get_ancestors(parent, stop_on)
...
>>> get_ancestors('Galago alleni')
<generator object get_ancestors at 0x7f7cecec06d0>
>>> list(get_ancestors('Galago alleni'))
['Lorisiformes', 'Strepsirrhini', 'Primates']

Answer 2

你的代码这一行 -

result = [parent] + parent_ancestors

其实就是 -

result = [parent] + get_ancestors(parent)

所以在递归的最高层，你是通过根据更深层递归调用返回的结果，逐个添加所有的父级，来构建最终的结果。