这种类型的递归是否有名字？

Question

我有一个在python中的链表，我想写一个过滤器函数，如果对f(item)的调用是真的，返回一个新的链接列表，这个实现有一个过滤器，从下往上建立列表。我无法理解这种递归。这是什么类型的递归？

我更加熟悉像斐波那契这样的递归递归在最底层的递归。

class Link: 
    empty =() 

    def __init__(self, first, rest=empty): 
     assert rest is Link.empty or isinstance(rest, Link) 
     self.first = first 
     self.rest = rest 

    def __getitem__(self, i): 
     if i == 0: 
      return self.first 
     else: 
      return self.rest[i-1] 

    def __len__(self): 
     return 1 + len(self.rest) 

    def __repr__(self): 
     if self.rest == Link.empty: 
      return "Link(" + str(self.first) + ")" 

     return 'Link({0}, {1})'.format(self.first, repr(self.rest)) 


def filter_link(f, s): 
    if s is Link.empty: 
     return s 
    else: 
     filtered = filter_link(f,s.rest) # How does this work? 
     if f(s.first): 
      return Link(s.first, filtered) 
     else: 
      return filtered 

Answer 1

这是排序你是用来递归。

我刚刚查找了一个递归fibonacci解决方案，其中早期返回是在第二行，就像你的代码。此外，与您的代码一样，示例中的递归发生在更正常的回报之前。

它看起来像你的代码从下到上返回功能f批准的元素的新链接列表。也就是说，它会在元素s.first周围创建Link的新实例，并由单个实例Link.empty终止。