Finding List Intersection Using Python List Slices & Recursion

def findIntersection(list1, list2): if list1 == [] or list2 == []: return [] elif list1[0] < list2[0]: return [list1[0]] + findIntersection(list[1:], lis

Solution 1:

Your problem is that you carefully return elements that are not in the intersection:

elif list1[0] < list2[0]:
    return [list1[0]] + findIntersection(list[1:], list2)
elif list1[0] > list2[0]:
    return [list2[0]] + findIntersection(list1, list2[1:])
else:
    return ([list1[0]] + findIntersection(list1[1:], list2[1:]))

Of these three cases, the only one that identifies a valid intersection element, is the last one: the element is in both lists.

For the other two, your recursion is correct, but adding the lower element is an error. You have to discard this element, because you know it isn't in both lists.

elif list1[0] < list2[0]:
    # Drop the lowest element of list1 and recurreturn findIntersection(list[1:], list2)
elif list1[0] > list2[0]:
    # Drop the lowest element of list2 and recurreturn findIntersection(list1, list2[1:])
else:
    The element isin both lists; add it to the solution and recur.
    return ([list1[0]] + findIntersection(list1[1:], list2[1:]))

Solution 2:

[i for i in list1 if i in list2]

Uses list comprehension. Cycles though each element in list1 and adds them to a new list if and only if they are found in list2.

If you want to use slicing and recursion, then you're very close... you only want to include an element in the intersection list if its in both lists - that's only true in the final else. Also you have a typo in your code - list where should be list1. Note also that this method requires the input lists to be sorted (either both ascending or both descending).

deffindIntersection(list1, list2):
    if list1 == [] or list2 == []:
        return []
    elif list1[0] < list2[0]:
        return findIntersection(list1[1:], list2)
    elif list1[0] > list2[0]:
        return findIntersection(list1, list2[1:])
    else:
        return [list1[0]] + findIntersection(list1[1:], list2[1:])

list1 = [0,2,3,5]
list2 = [1,2,3,4,5,6]
print(findIntersection(list1, list2))

Returns [2,3,5]