Python recursion with a nested list

Question

I am trying to make a recursive function that goes through any level of nested list with single character strings and returns True or False whether a given character is in that list.

This is my code:

def inlist(character, lists):
    """Checks if a given character is in a list of any level"""
    
    if lists[0] == character:
        return True
    
    elif isinstance(lists[0], list):
        return inlist(character,lists[0])
    
    elif not lists[0] == character:
        return inlist(character,lists[1:])
    
    else:
        return False

When i run the code with: ("c", [["a", "b","c", "d"],"e"])

it seems to be working fine. However, when i am typing the list in this way: ("c", [["a", "b",],["c", "d"],"e"])

It gives me an error, which says: IndexError: list index out of range

Can i not write a nested list in this way? If so, why? Or is there anything wrong with my code that makes it not go through the whole list?

Note how you're doing lists[0] before checking if lists has any elements. — Carcigenicate
– Carcigenicate, Commented Sep 26, 2020 at 21:57
Hmm, would it be better if i had another if statement on top with that and indented everything else? — Tulsan
– Tulsan, Commented Sep 26, 2020 at 22:01
I would just turn your current if into an elif, then have the if something like if not list:. No need to nest. — Carcigenicate
– Carcigenicate, Commented Sep 26, 2020 at 22:04
You logic is a little flawed too, if the first element is a list with out the character the elif will fire and return False even though one of the later lists might have returned True. — Mark
– Mark, Commented Sep 26, 2020 at 22:12
@Wups Slicing is actually safe to do on an empty list. It's a nice feature. — Carcigenicate
– Carcigenicate, Commented Sep 27, 2020 at 0:40

Wups · Accepted Answer · 2020-09-26 23:29:40Z

1

Going for the the purely recursive approach, like it is used in the question:

def inlist(char, lists):
    if not lists: # check for empty list
        return False
        
    if lists[0] == char:
        return True

    elif isinstance(lists[0], list) and inlist(char, lists[0]):
        return True # return only if found in sublist, otherwise continue

    elif len(lists) > 1: # check rest of the list, if there is a rest
        return inlist(char, lists[1:])
        
    return False # all possibilities exhausted. Char not in this (sub-)list

This can be useful for some problems, but to find an element in a list, a loop would be faster. Also, the max recursion depth will be a problem for longer lists.

edited Sep 26, 2020 at 23:29

answered Sep 26, 2020 at 23:06

Wups

2,5691 gold badge8 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Mulan · Accepted Answer · 2020-09-27 03:53:02Z

@Wups has you covered for the purely recursive solution. And nice catch on the isinstance(lists[0], list) case where you must still be careful to check lists[1] if the recursive call returns false.

Always check if a list is empty before reaching in for a value. Here's another way to think about the problem using higher-order functions like, some.

def some(f, t):
  if not t:
    return False
  else:
    return f(t[0]) or some(f, t[1:])

def inlist(char, ls):
  return some \
    ( lambda v: inlist(char, v) if isinstance(v, list) else char == v
    , ls
    )

input = ["c", [["a", "b",],["c", "d"],"e"]]
print(inlist("a", input))
print(inlist("z", input))

True
False

Above we write some as an exercise. You should be aware Python has a built-in any function -

def inlist(char, ls):
  return any(isinstance(v, list) and inlist(char, v) or char == v for v in ls)

input = ["c", [["a", "b",],["c", "d"],"e"]]
print(inlist("a", input))
print(inlist("z", input))

True
False

Yossi Levi · Accepted Answer · 2020-09-27 08:31:22Z

0

You made it a bit complicated, while the way of thinking in case of recursion should be much simpler

DFS-ish version:

(you can read more on DFS traversal all over the net)

def inlist(character, lists):
    """Checks if a given character is in a list of any level"""
    for item in lists:
        if item==character:
            return True
        if isinstance(item, list):
            if inlist(character, item):
                return True
    return False
    
            
        
a = ["c", [["a", "b",],["c", "d"],"e"]]
print(inlist("a", a))

output:

True

for this input:

print(inlist("z", a))

output is:

False

short explanation:

loop over all items in list
if the item is the character - finish
if the item is list - invoke recursion immediately (the catchy part here, is to return only if True, because if not - it not means that the character isn't found in other items)
if finish over all items and not found - finish
better when there is more chances that the item is in inner lists

BFS-ish version:

(you can read more on BFS traversal all over the net)

def inlist(character, lists):
    """Checks if a given character is in a list of any level"""
    extra_arr = []
    for item in lists:
        if item==character:
            return True
        if isinstance(item, list):
            extra_arr.append(item)
    
    for extra_item in extra_arr:
        if inlist(character, extra_item):
            return True
    return False

of-course, same results.

short explanation:

loop over all items in list
if the item is the character - finish
if the item is list - append to extra_arr which will execute after verify all the items in the current level
if finish over all items and not found - finish
better when there is more chances that the item is in outer lists

edited Sep 27, 2020 at 8:31

answered Sep 26, 2020 at 22:29

Yossi Levi

1,2681 gold badge7 silver badges7 bronze badges

2 Comments

Tulsan Over a year ago

This seems to be a much smarter and simpler solution, I will keep it in mind! I understand this is a mix of iteration and recursion. Is that the usual way to go about solving these problems? Or are there instances where only recursion is preferred?

Yossi Levi Over a year ago

I added some more "educational stuff" of DFS and BFS approaches, It mostly come from graphs traversals, but through my eyes it seems to be similar case in here. I don't know if there is any cut-and-clear definition of what is 'usual way', each person with his prefers I guess, more over it that I think that there is no relations between the recursion and iterations.

Collectives™ on Stack Overflow

Python recursion with a nested list

3 Answers 3

Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related