Finding index in nested list

Question

I am trying to create a function that will take as input a nested list and an item, and return a list of indices. For example list = [0, 5, [6, 8, [7, 3, 6]], 9, 10] and item = 7 should return [2, 2, 0], since list[2][2][0] = 7

my code should work since I can print the desires output, but when i run it it returns None.

def find_item(list_input, item, current):
    if list_input == item:
        print(current) ## this does give the desires output, but the function should return not print
        return current
    else:
        if isinstance(list_input, list):
            for j in range(len(list_input)):
                current.append(j)
                find_item(list_input[j], item, current)
                del current[-1]

what am I overlooking here?

You need to handle the return value from the recursive `find_item` call as well. — tzaman, Jul 23 '20 at 18:17
Well, first of all you're not returning anything in your else: — WNG, Jul 23 '20 at 18:18
Does this answer your question? [Why does my recursive function return None?](https://stackoverflow.com/questions/17778372/why-does-my-recursive-function-return-none) — wjandrea, Jul 23 '20 at 18:19

score 0 · Accepted Answer · answered Jul 23 '20 at 18:36

As @tzaman mentioned, you need to handle the return value of find_item recursive call. If the return value of the recursive call is a list, it will mean that searched item is found and we need to stop the recursion.

The following modification will return the earliest found index of the searched item. If no item is found, it will return None.

def find_item(list_input, item, current):
    if list_input == item:
        return current
    else:
        if isinstance(list_input, list):
            for j in range(len(list_input)):
                current.append(j)
                search_result = find_item(list_input[j], item, current)
                if isinstance(search_result, list):
                    return search_result
                del current[-1]

list_input  = [0, 5, [6, 8, [7, 3, 6]], 9, 10]
item = 7
print(find_item(list_input, item, []))

list_input  = [0, 5, [6, 8, [7, 3, 6]], 9, 10]
item = 9
print(find_item(list_input, item, []))

list_input  = [0, 5, [6, 8, [7, 3, 6]], [30, 4], 9, 10]
item = 4
print(find_item(list_input, item, []))

list_input  = [0, 5, [6, 8, [7, 3, 6]], [30, 4], 9, 10]
item = 400
print(find_item(list_input, item, []))

Output:

[2, 2, 0]
[3]
[3, 1]
None

score 0 · Answer 2 · answered Jul 24 '20 at 03:20

It always bothers me when someone sticks a for loop in the middle of a recursive function! Here's a different way to go about this problem:

def find_item(list_input, item, index=0):
    if list_input:
        head, *tail = list_input

        if head == item:
            return [index]

        if isinstance(head, list):
            if result := find_item(head, item):
                return [index] + result

        return find_item(tail, item, index + 1)
    
    return list_input

list_input  = [0, 5, [6, 8, [7, 3, 1]], 9, 10]

print(find_item(list_input, 7))

This solution doesn't require an explicit third argument. And returns an empty list upon failure to find the item, rather than None. Note the use of the new walrus operator :=

            if result := find_item(head, item):

If that's a problem, instead do:

            result = find_item(head, item)
            if result:

Finding index in nested list

2 Answers2