[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