Recursive Python Function to Check if Two Given Lists are Equal

In Python, I want to write a recursive function that takes in two separate integer lists as parameters. If the lists are exactly the same, the function will return True. If the lists are not exactly the same, they return False. The function cannot use any built-in library functions or the "==" operator to compare the lists. I can only use "==" to compare individual integers. The function also cannot have loops.

Quite honestly, I have no idea where to even start or how to proceed from there forwards. Can someone please help?

1 answer

  • answered 2018-08-09 00:32 ggorlen

    Taking a stab at it yourself and posting your attempt is generally the best way to learn. Having said that, here's my algorithm:

    def eq(a, b):
        if len(a) != len(b):
            return False
        elif not a and not b:
            return True
    
        return a[0] == b[0] and eq(a[1:], b[1:])
    
    print(eq([1,2,3], [1,2,3]))
    print(eq([1,2,3], [1,6,3]))
    print(eq([1,2,3], [1,2,3,4]))
    

    Output

    True
    False
    False
    

    Explanation

    Start with the base cases: if the lengths of the lists aren't the same, we can conclusively say they aren't equal and return false. Otherwise, if we have two empty lists, let's call them equal.

    Let's tackle the recursive case. Call the 0th element of each list the "current elements". If the current elements aren't equal, return false straight away. Otherwise, chop them off the front of the list and recursively call eq() with the remaining lists.