[Tutor] about recursion code

[Guillermo Fernandez Castellanos]

Usually, in case of doubt, use a debugger or print statements:
def selection_sort(lst,start,end):
	"""sort the lst from selection start to end"""
	print lst, start, end
	if len(lst)==1:
		print "list of size 1"
		return lst
	elif lst=="":
		print "list is an emtpy string"
	        return ""
	else:
		print "selection_sort(",lst,start+1,end,")"
	        return lst[:start]+selection_sort(lst,start+1,end)

Let's see what happens:
>>> a=[1,3,5,2]
>>> b=1
>>> c=3
>>> selection_sort(a,b,c)
[1, 3, 5, 2] 1 3
selection_sort( [1, 3, 5, 2] 2 3 )
[1, 3, 5, 2] 2 3
selection_sort( [1, 3, 5, 2] 3 3 )
[1, 3, 5, 2] 3 3
selection_sort( [1, 3, 5, 2] 4 3 )
[1, 3, 5, 2] 4 3
selection_sort( [1, 3, 5, 2] 5 3 )
[1, 3, 5, 2] 5 3
selection_sort( [1, 3, 5, 2] 6 3 )
[1, 3, 5, 2] 6 3
selection_sort( [1, 3, 5, 2] 7 3 )
[1, 3, 5, 2] 7 3
Etc,etc,etc

It seems that you are incrementing the start variable.
This is done in the line of code:
return lst[:start]+selection_sort(lst,start+1,end)

If we arrive to this line of code is because of the conditions of the
two previous "if":
- The list is not of size 1.
- The list is not an empty string.

Actually, when you do a recursion function you must make sure you have
an exit condition. And your function does not have.

If you want your function to end, it must arrive at one point to a
size of 1 or to be an empty string.

I did this by changing the line:
return lst[:start]+selection_sort(lst,start+1,end)
into the line:
return lst[:start]+selection_sort(lst[start:],start+1,end)

Oh... I am also wandering why you look for an empty string. You would
be better off by substituing "" by an empty list []

elif lst==[]:
		print "list is emtpy"
	        return []

You can even put togheter this line with the if len(lst)==1: line:
if len(lst)==1:
		print "list of size 1"
		return lst
	elif lst==[]:
		print "list is emtpy"
	        return []

becomes

if 0<len(lst)<2:
		return lst

It's not the good implementation of your algorithm (because I don't
know what you intend to do...), but because each time our lst becomes
tinier, the recursive function will not enter an infinite loop:

>>> def selection_sort(lst,start,end):
	"""sort the lst from selection start to end"""
	print lst, start, end
	if 0<=len(lst)<2:
		print "list of size 1 or less"
		return lst
	else:
		print "selection_sort(",lst,start+1,end,")"
	        return lst[:start]+selection_sort(lst[start:],start+1,end)

>>> selection_sort_modified(a,b,c)
[1, 3, 5, 2] 1 3
selection_sort( [1, 3, 5, 2] 2 3 )
[3, 5, 2] 2 3
selection_sort( [3, 5, 2] 3 3 )
[2] 3 3
list of size 1
[1, 3, 5, 2]

>>> a=[1,6,2,2,5,3,9,0,3,4]
>>> b=3
>>> c=8
>>> selection_sort(a,b,c)
[1, 6, 2, 2, 5, 3, 9, 0, 3, 4] 3 8
selection_sort( [1, 6, 2, 2, 5, 3, 9, 0, 3, 4] 4 8 )
[2, 5, 3, 9, 0, 3, 4] 4 8
selection_sort( [2, 5, 3, 9, 0, 3, 4] 5 8 )
[0, 3, 4] 5 8
selection_sort( [0, 3, 4] 6 8 )
[] 6 8
list of size 1 or less
[1, 6, 2, 2, 5, 3, 9, 0, 3, 4]

Hope that helps,

G

On Tue, 07 Dec 2004 12:37:20 +0800, Lin Jin <jinlin555 at msn.com> wrote:
> hello,tutors:
>   i am working on the recursion of selection sort,and my code is:
> def selection_sort(lst,start,end):
>     """sort the lst from selection start to end"""
>     if len(lst)==1:
>         return lst
>     elif lst=="":
>         return ""
>     else:
>         return lst[:start]+selection_sort(lst,start+1,end)
> a=[1,3,5,2]
> b=1
> c=3
> print selection_sort(a,b,c)
> 
> but it seems not working when i call the function,anyone could tell me that
> what  i did wrong with my code?
> 
> _________________________________________________________________
> 享用世界上最大的电子邮件系统— MSN Hotmail。  http://www.hotmail.com
> 
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> http://mail.python.org/mailman/listinfo/tutor
>