使用递归重新创建过滤器（）函数

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

问题是，你的递归最后用长度为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 3

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

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 4

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

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])) 

Answer 5

其他的答案正确识别出导致你的异常问题是缺乏一个基本情况的。当你的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:]) 

如果你没有使用递归，做同样的事情的一个更Python（和更有效）的方法是使用列表理解：

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循环将不会执行任何操作，从而导致返回空列表。