# Recursive functions for sorting

I made a few recursive functions for learning purposes which do a variety of tasks. Here is my current and functioning code:

def separate(p,l):
''' recursive function when is passed a predicate and a list returns a 2-tuple
whose 0 index is a list of all the values in the argument list for which the
predicate returns True,and whose 1 index is a list of all the values in the
argument list for which the predicate returns False.'''
if len(l) == 0:
return ([],[])
else:
(true_list, false_list) = separate(p,l[1:])
if p(l):
return ([l] + true_list, false_list)
else:
return (true_list, [l] + false_list)

def is_sorted(s):
''' recursive function when passed a list returns a bool telling whether or not
the values in the list are in non-descending order: lowest to highest allowing
repetitions. '''
if len(s) <= 1:
return True
elif s < s:
return is_sorted(s[1:])
else:
return False

def sort(l):
''' recursive function when passed a list; it returns a new list (not mutating
the passed one) with every value in the original list, but ordered in non-
descending order. '''
if len(l) == 0:
return []
else:
(before, after) = separate(lambda i: i < l, l[1:])
return sort(before) + [l] + sort(after)

def compare(a,b):
''' a recursive function when is passed two str arguments; it returns one of
three str values: '<’, '=’, or '>’ which indicates the relationship between the
first and second parameter.'''
if a == '' and b == '':
return '='
if a == '' and b != '':
return '<'
if a != '' and b == '':
return '>'
if a > b:
return '>'
if a < b:
return '<'
else:
return compare(a[1:],b[1:])


Is there a way to write these recursive functions in a cleaner/concise way? Any help would be great.

• Please ask a separate question for code_metric(). It is neither recursive, nor does it reuse your other functions. (I believe you have missed the point of the exercise as well.) Feb 8, 2015 at 14:18
• @200_success- WIll do. I know I missed the point of the exercise, but that's what I needed help with. Feb 8, 2015 at 15:56

is_sorted() does not behave as described or as expected. It requires elements to be strictly increasing rather than non-descending.

The implementation and docstring could be shorter as well.

def is_sorted(list):
"""Recursively checks if the elements in the list are in non-descending order."""
return len(list) <= 1 or (list <= list and is_sorted(list[1:]))


I'd expect that trimming lists at the end would be more efficient (though the code definitely looks weirder):

def is_sorted(list):
"""Recursively checks if the elements in the list are in non-descending order."""
return len(list) <= 1 or (list[-2] <= list[-1] and is_sorted(list[:-1]))


compare() has some redundant checks.

Here, I feel that the else is incongruous. Either rely on the early returns, or use else in conjunction with elif everywhere.

def compare(a,b):
"""Lexicographically compares strings a and b, returning '<', '=', or '>'."""
if a == '' and b == '':
return '='
if a == '':
return '<'
if b == '':
return '>'
if a > b:
return '>'
if a < b:
return '<'
return compare(a[1:], b[1:])


Instead of checking for == '', consider checking the length, so that the function can operate on lists as well.

• @200_success- using the is_sorted function when I try to do is_sorted([]) it should return True but it gives me error stating return len(list) <= 1 or (list <= list and is_sorted(list[1:])) TypeError: object of type 'type' has no len() Feb 8, 2015 at 16:03
• @200_success- compare has the same issue. when I do compare('','') it returns < when it should be =. compare('','abc') return > when it should be <. Similarly, the problem persists if any of the strings compared is empty. Works perfectly fine when comparing with non-empty string args. Feb 8, 2015 at 16:04
• @LucyBen If you're getting TypeError: object of type 'type' has no len(), then you probably missed the detail that I renamed the parameter from s to list. Feb 8, 2015 at 18:53
• How is it possible that compare('', '') returns '<'? That's handled by the first conditional, which I didn't change at all. Feb 8, 2015 at 18:54
• @200_success- nm..I made some minor errors in transcribing the code. It works perfectly. Thank you. Feb 8, 2015 at 19:52

I recommend you be more consistent in not combining if followed by a statement sequence ending in return with an else (I left out the comments):

def separate(p,l):
if len(l) == 0:
return ([],[])
(true_list, false_list) = separate(p,l[1:])
if p(l):
return ([l] + true_list, false_list)
return (true_list, [l] + false_list)


as you do e.g. in compare().

In compare() I would nest the conditions (arbitrarily based on a):

def compare(a,b):
if a == '':
if b == '':
return '='
return '<'
if a != '':
if b == '':
return '>'
if a > b:
return '>'
if a < b:
return '<'
return compare(a[1:],b[1:])


That way it is more clear to me that compare() never ends without a return value.

Your comments should at least use triple double quotes (PEP8) and you should try to conform to PEP 257 (docstring conventions).

• @Alice- when I do compare('','') it returns < when it should be =. compare('','abc') return > when it should be <. Similarly, the problem persists if any of the strings compared is empty. Works perfectly fine when comparing with non-empty string args. Feb 8, 2015 at 16:01
• @LucyBen it doesn't in my test program. Are you sure you are running the right tests? And the same ones that give the correct results on your own code? Feb 9, 2015 at 8:56
• @Alice- I made some minor errors in transcribing the code. It works perfectly. Thank you. any suggestions for sort function?? Feb 9, 2015 at 9:13