這種類型的遞歸是否有名字？

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終止。