CODEWITHSUNDEEP
pythonlistif-statementrecursioncompare
Kevin Lucas
Kevin Lucas

Reputation: 39

Python 3: applying recursion to compare lists?

I'm trying to define a function with the following that takes two parameters, list_1 and list_2, and compares them as follows: it returns False if list_1 and list_2 have different lengths, True if list_1 and list_2 are identical, and otherwise returns the index of the first mismatched elements between the lists.

So far I have this:

if len(list_1) != len(list_2):
    return False
elif list_1 == list_2:
    return True
else:
    i = 0
    if list_1[i] == list_2[i]:
        return i
    else:
        i += 1
        compare_lists(list_1, list_2)

Logically i keeps getting reset to 0 when I call the function again. Does anyone know how I can overcome this?

Upvotes: 2

Views: 2446

Answers (1)

Joe Iddon
Joe Iddon

Reputation: 20434

You must pass thei working variable down to each function.

Also, you shouldn't check whether the lists are equal or if they are different lengths in every function as this defeats the point of the recursion as the list_1 == list_2 statement causes a "behind-the-scenes" for-loop to iterate over both lists. This would dramatically decrease performance.

Instead just catch the case where your current index is past the end of one of the lists. In this case, if they are both the same lengths, then we can return True; otherwise we return False since we have reached the end of one but not the other.

In the case where the above case does not apply to the index of this function call, we simply check whether the elements at our index are the same. If they are not, we return our index (which will get passed up through our parents to the initial caller). Otherwise we return the result of calling ourselves (a child) with the same lists, but with an incremented index (i + 1).

def compare_lists(list_1, list_2, i=0):
    l1 = len(list_1)
    l2 = len(list_2)
    if i >= l1 or i >= l2:
        return l1 == l2
    if list_1[i] != list_2[i]:
        return i
    return compare_lists(list_1, list_2, i+1)

which works as intended:

>>> compare_lists([6,4,2], [6,4,2])
True
>>> compare_lists([6,4,2], [6,4,3])
2
>>> compare_lists([6,4,2], [6,4])
False

Upvotes: 2

Related Questions