#
# Program to see if something is in a list, recursively
# Matt Bishop, MHI 289I, Winter 2018
#
def isinlist(x, L):
    #
    # base case: L is empty
    #
    if len(L) == 0:
        return False
    #
    # check each element
    # if element is a list, recurse
    #
    for y in L:
        # see if it's equal to the element
        if x == y:
            return True
        # nope -- see if element in list is a list
        # if so, see if x is in it
        if isinstance(y, list) and isinlist(x, y):
            return True
    #
    # if you get here, x isn't in L
    #
    return False

print "3 in [1, 4, 2, 3] is", isinlist(3, [1, 4, 2, 3])
print "3 in [1, [4, 2, 3]] is", isinlist(3, [1, [4, 2, 3]])
print "[2, 3] in [1, [4, 2, 3]] is", isinlist([2, 3], [1, [4, 2, 3]])
print "[2, 3] in [1, [4, 2], [[2, [2, 3]]] is", isinlist([2, 3], [1, [4, 2], [[2, [2, 3]]]])
print "[] in [1, [4, 2], [[2, [2, 3]]] is", isinlist([], [1, [4, 2], [[2, [2, 3]]]])