递归收集Python/Django中的子项

Question

我有一个这样的模型....

class Person(models.Model):
    name = models.CharField(max_length=55,null=False, blank=False)
    parent = models.ForeignKey('Person.Person', null=False, blank=False)

我想创建一个递归函数,最终将返回整个人家谱的字典....

所以例如......

first_person = Person.objects.filter(name='FirstPerson')
family_tree = GetChildren(first_person)

GetChildren是我的递归函数,它将不断调用GetChildren,直到没有更多的子项......它应该返回一个包含所有这些子项的字典,如此...

{
    'name': 'FirstPerson',
    'children': [
        {
            'name': 'FirstPersonChild1'
            'children': [ ... ]
        },
        {
            'name': 'FirstPersonChild2'
            'children': [ ... ]
        }
    ]
}

我从来没有善于递归,有人会介意如何解决这个问题......

Answer 1

这个实现应该有效

def get_family_tree(person):
    """ return a family tree for a Person object """

    children = person.children.all()

    if not children:
        # this person has no children, recursion ends here
        return {'name': person.name, 'children': []}

    # this person has children, get every child's family tree
    return {
        'name': person.name,
        'children': [get_family_tree(child) for child in children],
    }

请注意，这将需要与人数一样多的数据库调用。如果遇到性能问题，您可以尝试将所有数据提取到内存中。

关于递归的思考

考虑递归的一种方法是从基本情况开始——即递归结束的地方。就您而言，我们知道如果一个人没有孩子，家谱会是什么样子：

{
    'name': 'FirstPerson',
    'children': [],
}

有了基本情况后，请考虑必须执行一次递归的问题。

就您而言，这将是有孩子的父母，但没有孙子。我们知道每个孩子的家谱应该是什么样子 - 这只是基本情况！这引导我们找到返回父母姓名和每个孩子的家谱列表的解决方案。导致类似的事情：

{
    'name': FirstPerson,
    'children': [<each element is a child's family tree>]
}

编辑

Django 自动为ForeignKey 生成反向关系。

class Person(models.Model):
    ....
    parent = models.ForeignKey('self', related_name='children', blank=True, null=True)

p = Person()
p.children.all() # automatically fetch all Person objects where parent=p

请参阅https://docs.djangoproject.com/en/1.9/ref/models/fields/#foreignkey