Recursive functions for sorting

Question

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[0]): return ([l[0]] + true_list, false_list) else: return (true_list, [l[0]] + 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[0] < s[1]: 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[0], l[1:]) return sort(before) + [l[0]] + 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[0] > b[0]: return '>' if a[0] < b[0]: 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.

Answer 1

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[0] <= list[1] 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[0] > b[0]: return '>' if a[0] < b[0]: 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.

Answer 2

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[0]): return ([l[0]] + true_list, false_list) return (true_list, [l[0]] + 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[0] > b[0]: return '>' if a[0] < b[0]: 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).