Question

Write the recursive version of the function filter which returns a list and takes in

f a one-argument function that returns True if the passed in argument should be included in the resulting list or False otherwise
seq a list of values
Note that this is different from the built in filter function we learned previously, which returns a filter object, not a list.

Answer 1

A recursive version of the filter function is:

def recursive_filter(f, seq):
if not seq:
return []
else:
head = seq[0]
tail = seq[1:]
if f(head):
return [head] + recursive_filter(f, tail)
else:
return recursive_filter(f, tail)

Step-by-step explanation:

To write a recursive version of the filter function that returns a list based on a predicate function, we can define the function as follows:

def recursive_filter(f, seq):
if not seq:
return []
else:
head = seq[0]
tail = seq[1:]
if f(head):
return [head] + recursive_filter(f, tail)
else:
return recursive_filter(f, tail)

This function takes two arguments: f, which is a function that returns True for items to include in the output list, and seq, which is the list of items to be filtered.

The function defines a base case that returns an empty list when seq is empty. If seq is not empty, the function checks if the first element satisfies the condition f.

If it does, the element is included in the result list followed by a recursive call on the remaining sublist. If not, only the recursive call on the remaining sublist is returned, effectively excluding the current head element.