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[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) &lt;= 1:
        return True
    elif s[0] &lt; 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 &lt; 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: '&lt;’, '=’, or '&gt;’ which indicates the relationship between the 
    first and second parameter.'''
    if a == '' and b == '':
        return '='
    if a == '' and b != '':
        return '&lt;'
    if a != '' and b == '':
        return '&gt;'
    if a[0] &gt; b[0]:
        return '&gt;'
    if a[0] &lt; b[0]:
        return '&lt;'
    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.
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 '&lt;'
    if a != '':
        if b == '':
            return '&gt;'
    if a[0] &gt; b[0]:
        return '&gt;'
    if a[0] &lt; b[0]:
        return '&lt;'
    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).