# File: isinlist.py
# Program to see if something is in a list, recursively
#
# Matt Bishop, ECS 36A, Winter 2019
#
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 type(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]]]]))