Recursive function that filter names (python)

Question

I need to define a recursive function that takes two parameters (a list with names and an initial), and returns a new list with all the names that start with the initial.

Right now I have got this code, and i don't know why it doesn't work:

def filter_names(names, initial):
    result = []
    if names[0][0] == initial:
        result.append(names[0])
    else:
        filter_names(names[1:], initial)
    return result

I feel like you might be supposed to do `result.extend(filter_names(names[1:], initial))` instead of what you have on that line (after `else:`), but you should provide sample input and expected output so that we can run and test it. — Matiiss, Nov 18 '22 at 23:27
Every recursive call has its own `result` list, and you never send the `result` from one recursive call back up to the parent. Either have them all share the same list by doing something like passing it as a parameter, or use the returned list. — Carcigenicate, Nov 18 '22 at 23:28
That's a terrible example for recursion. Did you read this in an on-line tutorial? Also note that your recursion stops as soon as it hits the FIRST name with that initial. You can't use an `else:`; you need to recurse every time, unless the list is empty. — Tim Roberts, Nov 18 '22 at 23:28
Think carefully about the logic. When the recursive call happens, will it be able to append to the same `result` list as in the parent? No; it will create its **own, completely independent** `result`, **just like** if you called **any other function** rather than using recursion. — Karl Knechtel, Nov 18 '22 at 23:31
@TimRoberts Almost every example for recursion is "terrible" from the standpoint of "why would you use recursion for this?!" - but it's **necessary** to have such "terrible" examples in order to *properly focus on and understand the technique* of recursion. It's pedagogic in the same way as forcibly using iteration where recursion is more appropriate. — Karl Knechtel, Nov 18 '22 at 23:33
Maybe, but we have seen a recent spate of questions from people applying recursion to their real problems where it shouldn't be used. In my opinion, "why" needs to be taught just as much as "how". — Tim Roberts, Nov 18 '22 at 23:37
I wasn't going to mark this duplicate originally, but I really think it's the best answer here. Although the *symptom* is quite different, the *problem* is the same: simply making the recursive call doesn't actually do anything with the result. The way to solve the problem is to think of the recursive call **the same way** as one would think about **any other** function call: what do we need to do with the returned value? We'll get a list, and all of its values should be concatenated with the current `result`, yes? So, we do exactly that. — Karl Knechtel, Dec 02 '22 at 12:14

score 1 · Answer 1 · answered Nov 18 '22 at 23:30

Your recursive call isn't appending to the same result that's defined in the outer scope.

Usually in a recursive function you combine the result of your recursive call with whatever work you've done in the current frame. In this case that might look like this:

def filter_names(names, initial):
    if not names:
        return []
    return (
        [names[0]] if names[0][0] == initial else []
    ) + filter_names([1:], initial)

score 0 · Answer 2 · answered Nov 18 '22 at 23:32

I'm going to say that this is not a good use of recursion, but you have some misconception about how to go about it:

def filter_name(names, initial) -> list[str]:
    if 0 == len(names):  # base case
        return []  
    else:  # iterative case
        head = names[0]  # The first element
        tail = names[1:]  # Everything else
        tail_names = filter_name(tail, initial)  # Get the result of the recursive call on 'everything else'
        if head[0] == initial:  # Decide if the first element should change your result
            tail_names.append(head)  # If so, modify your result
        return tail_names  # Return it

For recursion you need to define a base case and an iterative step. The iterative step should call the function again, with a smaller input. Then it should add (any necessary) change into the returned result before returning it.

This code is unnecessarily explicit - there are more concise ways to do it, but it illustrates what is going on.

The base case is that you have an empty list of names. You know what should be returned in this case - an empty list.

The iterative case should first figure out what the next-smallest version of the problem is. Here, it is a list that is one shorter, tail. First get the result of recursing with that new, shorter input. With that result, you then take the difference - in this case head and decide if you need to modify the result. After that, you return that result.

That said, there is a far easier, efficient and idiomatic way to do this in python:

result = [name for name in names if name[0] == initial]

Recursive function that filter names (python)

2 Answers2