3
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 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.) \$\endgroup\$ Feb 8, 2015 at 14:18
  • \$\begingroup\$ @200_success- WIll do. I know I missed the point of the exercise, but that's what I needed help with. \$\endgroup\$
    – LucyBen
    Feb 8, 2015 at 15:56

2 Answers 2

3
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ @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[0] <= list[1] and is_sorted(list[1:])) TypeError: object of type 'type' has no len() \$\endgroup\$
    – LucyBen
    Feb 8, 2015 at 16:03
  • \$\begingroup\$ @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. \$\endgroup\$
    – LucyBen
    Feb 8, 2015 at 16:04
  • \$\begingroup\$ @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. \$\endgroup\$ Feb 8, 2015 at 18:53
  • \$\begingroup\$ How is it possible that compare('', '') returns '<'? That's handled by the first conditional, which I didn't change at all. \$\endgroup\$ Feb 8, 2015 at 18:54
  • \$\begingroup\$ @200_success- nm..I made some minor errors in transcribing the code. It works perfectly. Thank you. \$\endgroup\$
    – LucyBen
    Feb 8, 2015 at 19:52
3
\$\begingroup\$

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).

\$\endgroup\$
3
  • \$\begingroup\$ @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. \$\endgroup\$
    – LucyBen
    Feb 8, 2015 at 16:01
  • \$\begingroup\$ @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? \$\endgroup\$
    – Alice
    Feb 9, 2015 at 8:56
  • \$\begingroup\$ @Alice- I made some minor errors in transcribing the code. It works perfectly. Thank you. any suggestions for sort function?? \$\endgroup\$
    – LucyBen
    Feb 9, 2015 at 9:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.