# 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.) – 200_success Feb 8 '15 at 14:18
• @200_success- WIll do. I know I missed the point of the exercise, but that's what I needed help with. – LucyBen Feb 8 '15 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() – LucyBen Feb 8 '15 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. – LucyBen Feb 8 '15 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. – 200_success Feb 8 '15 at 18:53
• How is it possible that compare('', '') returns '<'? That's handled by the first conditional, which I didn't change at all. – 200_success Feb 8 '15 at 18:54
• @200_success- nm..I made some minor errors in transcribing the code. It works perfectly. Thank you. – LucyBen Feb 8 '15 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. – LucyBen Feb 8 '15 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? – Alice Feb 9 '15 at 8:56
• @Alice- I made some minor errors in transcribing the code. It works perfectly. Thank you. any suggestions for sort function?? – LucyBen Feb 9 '15 at 9:13