使用递归重新创建 filter() 函数

Question

我们必须使用递归重新创建filter()函数。

我有以下几点：

def even(X):
    if X % 2:
        return True
    return False
def myFilter(f, L):
    return f(L[0]) + myFilter(f, L[1:])

当我尝试运行：print (myFilter(even, [0, 1, 2, 3, 4, 5, 6]))时，我收到一个错误，说IndexError: list index out of range。

有人可以指出我解决这个问题的正确方向吗？

注意：我们不能使用任何内置的python函数

Answer 1

您需要捕获基本情况：

def even(X):
    if not X % 2:
        return True
    return False
def myFilter(f, L):
    if not L:
        return []
    return [f(L[0])] + myFilter(f, L[1:])
>>> myFilter(even, [0, 1, 2, 3, 4, 5, 6])
[True, False, True, False, True, False, True]
>>> myFilter(even, [])
[]
>>> myFilter(even, [2])
[True]
>>> myFilter(even, [1])
[False]

Answer 2

其他答案已正确确定导致异常的问题是缺少基本情况。当您的myFilter函数被调用时，它无法使用空列表，它无法访问L[0] 。

但是，它们并没有解决您实际上根本没有过滤的事实，而是您正在执行与内置map函数相同的操作。如果你真的想过滤，你需要稍微改变一下操作。

def myFilter(f, L):
    if not L:
        return []  # base case, fixes the exception
    if f(L[0]):  # use the return value of f to tell whether to include L[0] in return
        return L[0] + myFilter(f, L[1:])
    else:
        return myFilter(f, L[1:])

如果你不必使用递归，那么做同样事情的更 Pythonic （和更有效）的方法是使用列表推导：

def myFilter(f, L):
    return [x for x in L if f(x)]

如果你还没有学习列表推导，它基本上与这个解压缩版本相同：

def myFilter(f, L):
    result = []
    for x in L:
        if f(x):
            result.append(x)
    return result

这些版本的好处是它们不需要显式的基本情况。如果列表L为空，则 for 循环将根本不执行任何操作，从而导致返回空列表。

Answer 3

问题是您的递归最终以长度为 0 的列表结束。这就是为什么在这里访问L[0]不起作用的原因。

def my_filter(callback, let):
     if len(lst) == 0: 
         return []
     return ([lst[0]] if callback(lst[0]) else []) + my_filter(callback, lst[1:]) 

请注意，f(L[0]) + myFilter(f, L[1:])不起作用，因为 myFilter 应该返回一个列表，而 f（L[0]） 是一个布尔值。

Answer 4

您没有递归停止条件。 试试这个：

def even(X):
    if X % 2:
        return True
    return False
def myFilter(f, L):
    if (len(L) == 1):
        return f(L[0])
    return f(L[0]) + myFilter(f, L[1:])

Answer 5

你应该定义递归结束条件：

def even(X):
if X % 2:
    return True
return False

def _filter(f, l):
    if len(l) == 1:
        return [l[-1]] if f(l[-1]) else []
    else:
        return filter(f, l[:-1]) + ([l[-1]] if f(l[-1]) else [])
print(_filter(even, [1, 2, 3, 4, 5, 1, 1, 1, 6]))