Need to combine two functions into one (Python)

Question

Here is my code-

def Max(lst):
    if len(lst) == 1:
        return lst[0]
    else:
        m = Max(lst[1:])
        if m > lst[0]: 
            return m
        else:
            return lst[0]
def Min(lst):
    if len(lst) == 1:
        return lst[0]
    else:
        m = Min(lst[1:])
        if m < lst[0]: 
            return m
        else:
            return lst[0]
print("Max number:",Max([5,4,100,0,2]))
print("Min number:",Min([5,4,100,0,2]))

Basically I need a single function that returns both the largest and smallest number and it needs to be recursively. How would would I change this code?

Answer 1

Some types of recursive algorithms/implementations operating on a list input are very quite easy to come up with, if you know the "trick". That trick being:

Just assume you already have a function that can do what you want.

Wait, no, that doesn't really make sense, does it? Then we'd already be done.

Let's try that again:

Just assume you already have a function that can do what you want (but only for inputs 1 element smaller than you need).

There, much better. While a bit silly, that's an assumption we can work with.

So what do we want? In your example, it's returning the minimum and maximum elements of a list. Let's assume we want them returned as a 2-tuple (a.k.a. a "pair"):

lst = [5, 4, 100, 0, 2]

# Well, actually, we can only do this for a smaller list,
# as per our assumption above.
lst = lst[1:]

lst_min, lst_max = magic_min_max(lst)  # I want a pony!

assert lst_min == 0   # Wishful thinking
assert lst_max == 100 # Wishful thinking

If we have such a magic function, can we use it to solve the problem for the actual input size? Let's try:

def real_min_max(lst):
    candidate = lst[0]
    rest_of_the_list = lst[1:]
    min_of_rest, max_of_rest = magic_min_max(rest_of_the_list) # Allowed because
                                                               # smaller than lst
    min_of_lst = candidate if candidate < min_of_rest else min_of_rest
    max_of_lst = candidate if candidate > max_of_rest else max_of_rest
    return min_of_lst, max_of_lst

Not exactly easy, but pretty straight forward, isn't it? But let's assume our magic function magic_min_max has an additional restriction: It cannot handle empty lists. (After all, an empty list doesn't have neither a minimum nor a maximum element. Not even magic can change that.)

So if lst has size 1, we must not call the magic function. No problem for us, though. That case is easy to detect and easy to circumvent. The single element is both minimum and maximum of its list, so we just return it twice:

def real_min_max(lst):
    candidate = lst[0]
    if len(lst) == 1:
        return candidate, candidate  # single element is both min & max
    rest_of_the_list = lst[1:]
    min_of_rest, max_of_rest = magic_min_max(rest_of_the_list) # Allowed because
                                                               # smaller than lst
                                                               # but (if we get
                                                               # here) not empty
    min_of_lst = candidate if candidate < min_of_rest else min_of_rest
    max_of_lst = candidate if candidate > max_of_rest else max_of_rest
    return min_of_lst, max_of_lst

So that's that.

But wait ... there is no magic. If we want to call a function, it has to actually exist. So we need to implement a function that can return the minimum and maximum of a list, so we can call it in real_min_max instead of magic_min_max. As this is about recursion, you know the solution: real_min_max is that function (once it's fixed by calling a function that does exist) so we can have it call itself:

def real_min_max(lst):
    candidate = lst[0]
    if len(lst) == 1:
        return candidate, candidate  # single element is both min & max
    rest_of_the_list = lst[1:]
    min_of_rest, max_of_rest = real_min_max(rest_of_the_list) # No magic needed,
                                                              # just recursion!
    min_of_lst = candidate if candidate < min_of_rest else min_of_rest
    max_of_lst = candidate if candidate > max_of_rest else max_of_rest
    return min_of_lst, max_of_lst

Let's try it:

lst = [5, 4, 100, 0, 2]
real_min_max(lst)  # returns (0, 100)

It works!