CODEWITHSUNDEEP
pythonlistrecursion
Abbas Ali
Abbas Ali

Reputation: 13

list equality with recursion Python

I am trying to write a program that tells whether 2 lists are the exact same using recursion, it works when the lists are not the same, but when they are the same, it gives me an error saying the list index is out of range. The way I'm writing it, I'm not comparing the lists directly (lst1 ==lst2). I'm just comparing single elements of the list and the lengths of the lists. 

def compare (lst1, lst2):
    if len(lst1) != len(lst2):
        return False
    if lst1[0] != lst2[0]:
        return False
    return compare(lst1[1:],lst2[1:])

example:

>>> compare(['ispython',1,2,3], ['isPYthon',1,2,3])
False
>>> compare(['ispython',1,2,3], [1,2,3])
False
>>> compare(['ispython',1,2,3], ['ispython',1,2,3])
True

Upvotes: 1

Views: 2317

Answers (3)

Walter_Ritzel
Walter_Ritzel

Reputation: 1397

Try this:

def compare (lst1, lst2):
    if lst1 and lst2:
        if len(lst1) != len(lst2):
            return False
        if lst1[0] != lst2[0]:
            return False
        return compare(lst1[1:],lst2[1:])
    else:
        return True

Upvotes: 0

DJMcMayhem
DJMcMayhem

Reputation: 7689

You need a base case. Your logic is almost correct, it just has no exit point on the recursion. What would happen if you entered an empty list?

if len(lst1) != len(lst2):
    return False

The length of each list is 0, so it will not return here.

if lst1[0] != lst2[0]:
    return False

lst1[0] does not exist, and neither does lst2[0] That's where your index error is happening. Try adding this:

if len(lst1) == 0 == len(lst2) == 0:
    return True

Upvotes: 1

tzaman
tzaman

Reputation: 47830

You're missing a case. After you've compared the last elements of both lists, you still call compare(lst1[1:]... even though there's nothing left, so your next call's lst1[0] is looking in an empty list.

You need to check for that and actually return True before that:

if len(lst1) == len(lst2) == 0:
    return True

Upvotes: 0

Related Questions