python minmax using only recursion

Question

I am trying to build a function that takes in a list and returns a tuple of (min, max).

For example,

[2,1,4,9,4.5]

would return

(1, 9)

I am trying to use only recursion and want to perform this task without using other things that would make this very easy (such as min(),max(),sort(),sorted(),loop..etc)

So far, I have been able to create function that find maximum

def findmax(alist):
  if len(alist) <= 1:
    return tuple(alist)
  elif len(alist) == 2:
    if alist[0] >= alist[1]:
        return findmax([alist[0]])
    elif alist[0] <= alist[1]:
        return findmax([alist[1]])
  elif len(alist) > 2:
    if alist[0] >= alist[1]:
        return findmax([alist[0]] + alist[2:])
    elif alist[0] <= alist[1]:
        return findmax(alist[1:])

which

findmax([2,1,4,9,4.5])

returns

(9,)

and a function that find minimum (which is not too different)

def findmin(alist):
  if len(alist) <= 1:
    return tuple(alist)
  elif len(alist) == 2:
    if alist[0] >= alist[1]:
        return findmin([alist[1]])
    elif alist[0] <= alist[1]:
        return findmin([alist[0]])
  elif len(alist) > 2:
    if alist[0] >= alist[1]:
        return findmin(alist[1:])
    elif alist[0] <= alist[1]:
        return findmin([alist[0]] + alist[2:])

which

findmin([2,1,4,9,4.5])

returns

(1,)

Is there a way to put this two separate functions into one using only recursion so that it would return a desired result of

(1, 9)

Any help would really be appreciated.

Answer 1

I find that these sorts of problems tend to be simpler than you expect. Let the recursion do the work:

def find_min_max(a_list):

    if a_list:
        head, *tail = a_list

        if tail:
            minimum, maximum = find_min_max(tail)

            return [head, minimum][minimum < head], [head, maximum][maximum > head]

        return head, head

    return a_list

USAGE

>>> find_min_max([2, 1, 4, 9, 4.5])
(1, 9)
>>> find_min_max('elephant')
('a', 't')
>>> 

This solution is Python 3 specific but can be easily modified for Python 2 & 3 compatibility.

Answer 2

To find either max or min separately is easy. What is difficult is to find both max and min through recursive calls. Tail recursion is exactly for this (maintain and update status of variables through recursive calls) and is usually straightforward to write:

def findminmax(L):
    def inner(L1, min, max):
        if L1 == []:
            return (min, max)
        elif L1[0] > max:
            return inner(L1[1:], min, L1[0])
        elif L1[0] < min:
            return inner(L1[1:], L1[0], max)
        else:
            return inner(L1[1:], min, max)
    return inner(L[1:], L[0], L[0])

findminmax([2,1,4,9,4.5])
# => (1, 9)

No need for assignment and fancy list indexing. Only the most basic list operation is needed. The recursion structure is clear and very standard (obviously see base case, reduction and function recursive call) and the code is also very readable as plain English.

Update

A little modification to handle the string input and empty list or string input:

def findminmax(LS):
    def inner(LS1, min, max):
        if not LS1:
            return (min, max)
        elif LS1[0] > max:
            return inner(LS1[1:], min, LS1[0])
        elif LS1[0] < min:
            return inner(LS1[1:], LS1[0], max)
        else:
            return inner(LS1[1:], min, max)
    try:
        return inner(LS[1:], LS[0], LS[0])
    except IndexError:
        print("Oops! That was no valid input. Try again...")

findminmax([2,1,4,9,4.5])
# => (1, 9)

findminmax([2])
# => (2, 2)

findminmax('txwwadga')
# => ('a', 'x')

findminmax('t')
# => ('t', 't')

findminmax([]) # empty list
# => Oops! That was no valid input. Try again...

findminmax('') # empty string
# => Oops! That was no valid input. Try again...

Answer 3

Below, minmax is expressed using continuation-passing style. In this style, it's as if our state variables are pulled out of the aether. For additional examples of other programs written using this style, please see this answer.

from math import inf

def first (xs):
  return xs[0]

def rest (xs):
  return xs[1:]

def tuple2 (a, b):
  return (a, b)

def minmax (xs = [], then = tuple2):
  if not xs:                 # base case: no `x`
    return then (inf, -inf)
  else:                      # inductive case: at least one `x`
    return minmax \
      ( rest(xs)
      , lambda a, b:
          then \
           ( min (a, first (xs))
           , max (b, first (xs))
           )
      )

print (minmax ([ 2, 1, 4, 9, 4.5 ]))
# (1, 9)

print (minmax ([]))
# (inf, -inf)

min and max are defined as

def min (a, b)
  if a < b:
    return a
  else:
    return b

def max (a, b)
  if a > b:
    return a
  else:
    return b

Answer 4

You can add another def (read comments):

def f(l):
    return findmin(l)+findmax(l) # Also you can do: `(findmin(l)[0],findmax(l)[0])`

Now to call it, do:

print(f([2,1,4,9,4.5]))

Output would be:

(1, 9)

Answer 5

You're definitely over-complicating the recursive function. Both minimum and maximum can be returned in a tuple with the following recursive code.

my_list = [2,1,4,9,4.5]

def recursive_min_max(list_a, pos, biggest, smallest):
    if pos != len(list_a) - 1:
        biggest_new = list_a[pos] if biggest == None else list_a[pos] if list_a[pos] > biggest else biggest
        smallest_new = list_a[pos] if smallest == None else list_a[pos] if list_a[pos] < smallest else smallest
        return recursive_min_max(list_a, pos + 1, biggest_new, smallest_new)
    return (biggest,smallest)


print(recursive_min_max(my_list, 0, None, None))

At each step, the current list item is being compared to the current biggest and smallest elements. If they are bigger/smaller, the current value replaces them.