How to find an element in a nested list using recursion?

Question

I'm trying to write a function with recursion that will return True if the element is in the nested list or False of it isn't. So far my code works only for certain elements:

def inthere(ls, s):
    if s in ls:
        return True
    else:
        for thing in ls:
            if isinstance(thing, list): 
                return inthere(thing,s)

When I run:

A=[[2,4],[6,[[[8],10]],12],14,16]
print(inthere(A,12)) #Should return True, but does not.
print(inthere(A,2)) #Returns True, as it should.

I'm definitely missing something here, I can't seem to tell, I appreciate all the help!

You're missing how to step through your code and see what's happening inside it: http://stackoverflow.com/questions/4929251/can-you-step-through-python-code-to-help-debug-issues or at least [printf debugging](http://stackoverflow.com/questions/189562/what-is-the-proper-name-for-doing-debugging-by-adding-print-statements) — TessellatingHeckler, Feb 24 '17 at 03:49
@wwii agreed. A quick search shows a lot of awnsers to this question that could've been used — FancyDolphin, Feb 24 '17 at 04:06
Use the accepted answer to [Flatten (an irregular) list of lists in Python](http://stackoverflow.com/questions/2158395/flatten-an-irregular-list-of-lists-in-python) to iterate over the flattened list(s) and check. — wwii, Feb 24 '17 at 04:13

score 4 · Accepted Answer · answered Feb 24 '17 at 03:40

4

return inthere(thing,s)

should be:

if inthere(thing,s):
    return True

and then put a return False at the very end of the function. The reason that's not working right now is that if it doesn't find the thing in the first nested list it finds, it doesn't check any others.

answered Feb 24 '17 at 03:40

Joseph Sible-Reinstate Monica

45,431
5
48
98

If the function reaches the end, it will implicitly return `None` which is "falsy". – Klaus D. Feb 24 '17 at 03:49
@KlausD. Yes, but the question specifically says if the item isn't in the list, it should return False, not just any falsy value. – Joseph Sible-Reinstate Monica Feb 24 '17 at 03:50

score 1 · Answer 2 · answered Feb 24 '17 at 03:47

you can print the thing then you know why:

def inthere(ls, s):
if s in ls:
    return True
else:
    for thing in ls:
        print thing
        if isinstance(thing, list):
            return inthere(thing,s)

Result:

[2, 4]
2
4
None
[2, 4]
True

Yes, you stop the loop because you return the function at the first element of ls.You just check the whole list and the first element of list.You can:

if inthere(thing, s):
    return True

Paul Rooney · Answer 3 · 2017-02-24T04:04:27.593

First error is that the first thing you should do is check if the item is a list. If its not then you wouldnt use in with it, you'd use equals.

Then if it is a list you call isthere on each item in the list. However you shouldn't return in the loop unless you get a True response, otherwise the loop stops after the first iteration. There is a ready made function to perform this shortcutting behaviour any.

def inthere(i, s):
    if isinstance(i, list):
        return any(inthere(x, s) for x in i)
    return i == s

You could also add a basic test to assert that the returned values are correct.

B = {2, 4, 6, 8, 10, 12, 14, 16}
for i in range(20):
    assert inthere(A, i) == (i in B)

score 0 · Answer 4 · answered Feb 24 '17 at 03:56

My suggestion would've been to do something like this: (but not sure what your requirements are)

def traverse(o, tree_types=(list, tuple)):
    if isinstance(o, tree_types):
        for value in o:
            for subvalue in traverse(value, tree_types):
                yield subvalue
    else:
        yield o
#give a list of all values [2, 4, 6, 8, 10, 12, 14, 16]

def inthere(ls,s): 
    if s in list(traverse(ls)): #check if your value is in that list
        return True
    else:
        return False


A=[[2,4],[6,[[[8],10]],12],14,16]

print(inthere(A,12)) #return True
print(inthere(A,2)) #Returns True

How to find an element in a nested list using recursion?

4 Answers4