[Tutor] recursivity and lists

Gaston aminatane at hotmail.fr
Fri Mar 4 10:00:35 EST 2016


Thank you for these comments. Made me realize that I do not fully 
understand my code, and need to think about it a bit more.

I totally understand the huge side effects, and it is true that it would 
be dangerous if the function was to actually be used. I would like to 
find a fully functional version, using slices then. I propose this :

def linear_merge(list1, list2):
   if list1==[]: return list2
   elif list2==[]: return list1
   elif list1[-1]>list2[-1]:
     return linear_merge(list1[:-1],list2)+[list1[-1]]
   else:
     return linear_merge(list1,list2[:-1])+[list2[-1]]

Or alternatively:

elif list1[-1]>list2[-1]:
     b=linear_merge(list1[:-1],list2)
     b.append(list1[-1])
     return b

Both work but I am not satisfied. Is there not a method that could do 
the job of '+' operator (namely concatenate in a copy)?

As for my first code :

def linear_merge1(list1, list2):
   if list1==[]: return list2
   elif list2==[]: return list1
   elif list1[-1]>list2[-1]:
     a=list1.pop()
     linear_merge(list1,list2).append(a)
     return linear_merge(list1,list2)
   else:
     a=list2.pop()
     linear_merge(list1,list2).append(a)
     return linear_merge(list1,list2)

I don't get why it works to be fair. It feels like return 
linear_merge(list1,list2) does not call the function again. If return 
linear_merge(list1,list2) actually returned linear_merged of the lists, 
with one of them missing an element, I don't see where this element is 
actually added.

I know find it very weird. I would appreciate if you had an explanation 
(and if you understood my point)

Thank you for your help,

Gaston

On 03/03/2016 10:29 PM, Danny Yoo wrote:
>
> Some code comments:  The solution you have depends very much on 
> mutation and side effects: I recommend you try to stay as functional 
> as you can in this situation.
>
> By mixing mutation into the solution, there are certain things that 
> the program is doing that isn't part of the traditional behavior of a 
> merge sort.
>
> For example, it is actively mutating the input lists.  That's both 
> surprising and error prone.
>
> Also, the purpose for the second internal calls to the merge sort in 
> your current solution have nothing to do with merging, but rather to 
> pick which nonempty list to return as the result.  A reader of the 
> code who doesn't look at this code *very* carefully would wonder why 
> the function wasn't infinite-looping.  It's a bit too clever for its 
> own good.
>
> Hope that makes sense!
>



More information about the Tutor mailing list