[Tutor] recursivity and lists

[Gaston]

Hello everyone !

I was trying to do this little exercise:
# E. Given two lists sorted in increasing order, create and return a merged
# list of all the elements in sorted order. You may modify the passed in 
lists.
# Ideally, the solution should work in "linear" time, making a single
# pass of both lists.

I wanted to try doing it in a recursive way. Here is my function:

def linear_merge(list1, list2):
   if list1==[]: return list2 #initial case 1
   elif list2==[]:return list1 #initial case 2
   elif list1[-1]>list2[-1]: #recursive case 1
     a=list1.pop()
     return linear_merge(list1,list2).append(a)
   else: #recursive case 2
     a=list2.pop()
     return linear_merge(list1,list2).append(a)

So I add the biggest element of the two list to the end of the sorted 
couple of lists with this element removed.

Problem is that python complains that he cannot know the type of the 
result of this function (list). In C++ I would specify the type, but 
from what I understood, Python should not need this. What did I miss ?

I hope I made myself clear and thank you for your help,

Cheers,

Gaston