Minimum element in a tuple

Question

I'm solving exercise 2 from lecture 3 of Berkeley's CS 61A (2012):

Write a function min_element that returns the minimum element in a tuple.

def min_element(tup):
    """ Returns the minimum element in tup.
    >>> a = (1, 2, 3, 2, 1)
    >>> min_element(a)
    1
    """

I know that Python has a built-in min function, but at this point in the course, the only operations on tuples that we have studied are indexing [1] [-1], slicing [1:], and concatenation +, so my solution needs to restrict itself accordingly.

My solution:

def min_element(tup):
    """ Returns the minimum element in tup.
    >>> a = (1, 2, 3, 2, 1)
    >>> min_element(a)
    1
    """
    def find_min(tup, min):
        if not tup:
           return min
        else:
           min = tup[0] if tup[0] < min else min
           return min_element(tup[1:], min)
    if tup:
        return find_min(tup[1:], tup[0])

Can this solution be improved?

Answer 1

You can simplify the recursive version of your code by dropping elements until you are left with just one, and then comparing pairs sequential pairs:

def min_element_recur(tup):
    if len(tup) == 1:
        return tup[0]
    elif len(tup) >= 2:
        a = tup[0]
        b = min_element_recur(tup[1:])
        return a if a<b else b

If you have learned reduce and lambda expressions, you can implement the operation by reducing on the minimum of two elements (if you are using python 3, you need from functools import reduce). This is basically the same as Danny's approach.

def min_element_reduce(tup):
   return reduce(lambda x, y: x if x<y else y, (1,2,3,4,-1,5))

Finally, this is a bit too simple so it may not be allowed, but you can take the first elements of the sorted version of the tuple:

def min_element_sorted(tup):
   return sorted(tup)[0]

Danny's solution is probably the most straightforward, though.

Answer 2

Berkeley CS61A alum here. Your solution looks fine. Having sat through many a lecture where the prof would go through problems like this, I can pretty much guarantee this is the solution that would have been given:

def min_element(tup):
    min = tup[0]
    for element in tup[1:]:
        if element < min:
            min = element
    return min

So this solution might be considered by someone really pedantic to be a bit "better" than yours since it is less verbose and because, in general, recursion tends to be slower than iteration. Your solution works just fine though :)

Answer 3

If I pass the empty tuple to your function, what happens? The condition if tup: fails, so control reaches the end of the function. As it happens, reaching the end of a function is equivalent to return None, but it's a bad idea to rely on this (because it's not clear to the reader what happens in this case; also, it's deprecated in the Python style guide (PEP8)).

The result is the same as if the function succeeds and found that None is the minimum element of the tuple, as if you'd called min_element((None,)), so it could potentially lead to errors elsewhere in a program.

It would be better to raise an exception in this case. The built-in min raises ValueError:

>>> min(())
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: min() arg is an empty sequence