这种类型的递归有名字吗？

Question

我在python中有一个链表，我想编写一个filter函数，返回一个新的链表如果对f(item)的调用为真，这个实现有一个filter函数，它自下而上构建链表。我很难理解这个递归。这是什么类型的递归？你知道吗

我更熟悉递归，比如fibonacci，其中返回递归在最底层。你知道吗

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的单个实例终止。你知道吗