CODEWITHSUNDEEP
pythonlistif-statementrecursionunique
Aimforchris
Aimforchris

Reputation: 73

Comparing lists; returning unique list. - Python

Preface: This WAS for an exam which I previously took in my Data structures and algorithm class.

Question: Modify this function so it returns a sorted list of those items that are in L1 and L2. For example, given [1,2,3,4,5], [0,2,3,5,8] the function should return [2,3,5]. The function must use recursion in some way.

    def merge(L1, L2):
        if L1 == []:
            return L2
        elif L2 == []:
            return L1
        elif L1[0] <= L2[0]:
            return L1[:1] + merge(L1[1:], L2)
        else:
            return L2[:1] + merge((L1, L2[1:])

I modified the function to:

    def merge(L1, L2): 
        if L1 == []:                
           return L1
        elif L2 == []:              
           return L2
        elif L1[0] < L2[0]:         #Push L1 forward
           return merge(L1[1:], L2)
        elif L1[0] > L2[0]:         #Push L2 forward
           return merge(L1, L2[1:])
        elif L1[0] == L2[0]:        #If same element, return element
           return L1[:1] + merge(L1[1:], L2[1:])

I used basic if statements to push the lists forward making sure each element in each list was being checked against each other. It was getting late and my previous code kept returning [2,3,5,8] because, I originally had:

    if L1 == []:
       return L2
    elif L2 == []:
       return L1

When L1 was exhausted it would return the rest of L2.I then was retyping the code and accidentally put in:

   if L1 == []:
      return L1
   elif L2 == []:
      return L2

And it worked! The output is [2,3,5] but, it doesn't make sense to me

My questions are:

Why do the first two if statements of returning the exhausted list give me the output [2,3,5]?

Why does returning an empty list break out of the recursive function?

Lastly, Is there a way to break out of a chain of if statements if my list was exhausted in a recursive function?

Upvotes: 1

Views: 170

Answers (2)

Abhishek Bansal
Abhishek Bansal

Reputation: 12705

You want to find the intersection of two lists. Hence if either of the lists is empty, you need to return an empty list since the intersection would be [].

The output returns [2,3,5] because the previous recursive call has 

elif L1[0] == L2[0]:
    return L1[:1] + merge(L1[1:], L2[1:])

Hence from the above statement, the only elements that shall be added will be the ones that are common to both the lists.
The statement can also be modified to be:

return L1[0] + merge(L1[1:], L2[1:]) #add the common element and merge the remaining parts

Upvotes: 0

thefourtheye
thefourtheye

Reputation: 239573

Why do the first two if statements of returning the exhausted list give me the output [2,3,5]?

Because when there are no elements left in one of the lists, there will be nothing common between an empty list and the rest of the other list.

Why does returning an empty list break out of the recursive function?

return L1 and return L2 are the base conditions of your recursion. Once they are met, we have got a definite value (not another level of recursion). Unless we decide to recurse, once the base condition is met, the recursion will unwind and return the result.

Upvotes: 3

Related Questions