这种递归可以更有效地编写吗？

Question

我有一个分层组织，它是一个树，如果父母赞助孩子，节点是一个孩子。似乎我可以用这个代码遍历树

def get_team(self, person, team):
    firstline = User.query(User.sponsor == person.key).fetch(99999999)
    if firstline:
        for person in firstline:
            team.append(person)
            newdownline = self.downline(person, team)        
    return team

.

使用上面的我可以通过获得用户的组织

downline=user.get_team(user, [])

但有一种更有效的方式，因为我必须多次为单个请求做这一次，并且那么多的递归可能是无效的？或者代码会很好，因为它可以正确地遍历树？在我的第一个版本中，我使用了三个变量，我发现我可以只重新排列代码到两个变量而不是这个：

def downline(self, person, team, teamlist):
    firstline = User.query(User.sponsor == person.key).fetch(99999999)
    if firstline:
        for person in firstline:
            teamlist.append(person)
            newdownline = self.downline(person, team, teamlist)        
            team.append(newdownline)
    return teamlist 

.

我发现Teamlist变量不是真正需要的，所以我删除了它。我做的方式首先是一个变量太多：

people = user.downline(user, [], [])

Answer 1

Yes, there is a more efficient way to do it, depending on your computational tradeoffs.

You are currently doing a depth-first traversal of your tree, a perfectly fine approach. You could add some speed by caching results at the expense of some RAM usage, so:

if person.id in downline_cache:
      team.append(downline_cache[person.id])
else:
      downline_cache[person.id] = results
      team.append(results)

If the tree is fairly small, you could just cache the whole thing upfront, once per thread. That takes more RAM than what you're doing, but is much faster than doing a depth-first traversal every time you care what the results are. A lot depends on your usage patterns and the amount of data you're storing.

If you use a cache, you must make sure you have some way to deal with the underlying data changing, either with timeouts and 'eventually correct' type guarantees, or keeping track of when and how you must wipe the cache, or elements of the cache.