current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 0 down vote favorite

I am working with a some small functions to test recursion. I am fairly new to Python and am wondering if there is a cleaner way to get the job done.

def count(t,p):

    ''' recursive function when passed a binary tree (it doesn’t matter if it is a 
    binary search tree) and a predicate as arguments; it returns a count of all the 
    values in the tree for which the predicate returns True. '''
    if t == None or t.value == None:
        return 0
    elif p(t.value):
        return 1 + count(t.right, p) + count(t.left, p)
    else:
        return count(t.right, p) + count(t.left, p)



def equal(ll1,ll2):

    ''' recursive function when passed two linked lists; it returns whether or not 
    the linked lists contain exactly the same values in the same order. '''
    if ll1 == None and ll2 == None:
        return True
    if (ll1 != None and ll2 == None) or\
        (ll2 != None and ll1 == None):
        return False
    elif ll1.value == ll2.value:
        return equal(ll1.next, ll2.next)
    else:
        return False


def min_max(ll):

    ''' a recursive when passed a linked list; it returns a 2-tuple containing the 
    minimum value followed by the maximum value. If the linked list is empty, return 
    (None, None) '''
    if ll == None:
        return None, None
    maybe_min, maybe_max  = min_max(ll.next)
    if maybe_min == None or ll.value < maybe_min:
        least = ll.value
    if maybe_min != None and ll.value > maybe_min:
        least = maybe_min
    if maybe_max == None or ll.value >= maybe_max:
        most = ll.value
    if maybe_max != None and ll.value < maybe_max:
        most = maybe_max
    return least, most
share|improve this question
1  
Please quit starting titles with "clean code". The desire for clean code is already implied on this site, so it adds nothing. –  Jamal♦ Feb 23 at 4:00

2 Answers 2

up vote 2 down vote accepted

It is better to test for x is None rather than x == None.

Avoid using single-letter variable names — they may make sense to you, but not to anyone else.

I don't see any reason why a node should be automatically not counted if its value is None. Shouldn't it be up to the predicate to decide whether nodes with None as a value are counted or not?

You can eliminate a case by taking advantage of the fact that int(False) is 0 and int(True) is 1.

def count(tree_node, predicate):
    """Counts the tree_node and its descendants whose value satisfies the predicate."""
    if tree_node is None:
        return 0
    else:
        return int(predicate(tree_node.value)) + \
               count(tree_node.left, predicate) + \
               count(tree_node.right, predicate)

Stylistically, it would be better to consistently use either one long if… elif chain or just ifs with early returns. I also suggest putting the recursive case at the end of the function.

(ll1 != None and ll2 == None) or (ll2 != None and ll1 == None) can be simplified.

def equal(ll1, ll2):
    """Recursively checks whether two linked lists contain the same values
    in the same order."""
    if ll1 is None and ll2 is None:
        return True
    if ll1 is None or ll2 is None:
        return False
    if ll1.value != ll2.value:
        return False
    return equal(ll1.next, ll2.next)

Assuming that the linked list contains no None data values, the logic can be simplified.

def min_max(ll):
    """Returns a 2-tuple of the minimum and maximum values.
    If ll is empty, returns (None, None)."""
    if ll is None:
        return None, None
    if ll.next is None:
        return ll.value, ll.value
    least, greatest = min_max(ll.next)
    return min(ll.value, least), max(ll.value, greatest)
share|improve this answer
up vote 1 down vote

Python not my favorite language (but recursion is).

I would personally move the recursion out of the tests. Thus you do the test for return and other things first. Then the final statement is just a recursive call. This is because a lot work has gone into optimizing tail recursion and you can get significant benifits from it.

So:

def count(t,p):

    if t == None or t.value == None:
        return 0

    result = 1 if p(t.value) else 0

    return result + count(t.right, p) + count(t.left, p)

and

def equal(ll1,ll2):

     if ll1 == None and ll2 == None:
        return True
    if (ll1 != None and ll2 == None) or\
        (ll2 != None and ll1 == None):
        return False
    elif ll1.value != ll2.value:
        return False

    return equal(ll1.next, ll2.next)
share|improve this answer
    
@LokiAstari- Thanks. Any input on the min_max function? –  LucyBen Feb 23 at 6:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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