Find minimum and maximum with recursion efficiently

Question

Is there a way to to recursively find both minimum and maximum in a list efficiently? I wrote this with python, but it's hugely badly efficient, as is call the function with the same list both for max and both for min each time.

def f(l):
    if len(l)==1 : return [l[0],l[0]]
    return [max(l[0],f(l[1:])[0]),min(l[0],f(l[1:])[1])]

l=[1,3,9,-3,-30,10,100]
print(f(l))

output: [100, -30]

--

Have you any idea on how to improve it? Is it possible to do it even without passing any other variable to the function?

Answer 1

In Python, a recursive implementation will in any case be much slower than iterative one because of:

• call overhead
• object creation, incl. partial list construction
• not using some of Python's efficient constructs like for .. in loop

You cannot eliminate the former if you're specifically required to do a recursive algorithm, but you can cut on object construction. The list construction is especially taxing since all the elements are copied each time.

• instead of constructing a new list each iteration, pass the same list and the current index in it

  • and in your function, you are constructing a new list not once but twice!

• You're also making two recursive calls each iteration. Each of them will also make two calls etc, resulting in a total number of calls a whopping 1+2+4+...+2**(N-1) = 2**N-1! To add insult to injury, the two calls are completely redundant since they both produce the same result.

• since the current list element is used multiple times, a few microsecods can also be cut off by caching it in a variable instead of retrieving each time.

def rminmax(l,i=0,cmin=float('inf'),cmax=float('-inf')):
    e=l[i]

    if e<cmin: cmin=e
    if e>cmax: cmax=e
    if i==len(l)-1:
        return (cmin,cmax)
    return rminmax(l,i+1,cmin,cmax)

Also note that due to CPython's stack size limit, you won't be able to process lists longer than a number slightly lower than sys.getrecursionlimit() (slightly lower because the interactive loop machinery also takes up some call stack frames). This limitation may not apply in other Python implementations.

Here's some performance comparison on my machine on sample data:

In [18]: l=[random.randint(0,900) for _ in range(900)]

In [29]: timeit rminmax(l)
1000 loops, best of 3: 395 µs per loop

# for comparison:

In [21]: timeit f(l)    #your function
# I couldn't wait for completion; definitely >20min for 3 runs

In [23]: timeit f(l)    #sjf's function
100 loops, best of 3: 2.59 ms per loop

Answer 2

I am not sure why you want to use recursion to find the min and max as you can simply pass a list to min and max.

def f(l):
  return min(l), max(l)

If you are trying to do this as an exercise in recursion, I don't see a way to solve it without passing the min and max down the recursive call.

def f(l, min_=None, max_=None):
  if not l:
    return min_,max_
  min_ = l[0] if min_ is None else min(l[0], min_)
  max_ = l[0] if max_ is None else max(l[0], max_)
  return f(l[1:], min_, max_)

Answer 3

There is a way to do this (And recursion in python really is very slow; see the other answers if you want a robust implementation). Think about your recursive formulation from left to right: at each level of recursion, take the min/max of the current item in the list and the result returned from the next level of recursion. Then (for python>= 2.5, we can use the ternary operator):

def find_min(ls, idx):
    return ls[idx] if idx == len(ls) - 1 else min(ls[idx], find_min(ls, idx+1))

find_max is analogous; you can just replace min with max. If you want a simpler definition, you can wrap a function that only accepts ls around find_min/find_max and make that function call find_min(ls, 0) or find_max(ls, 0).

Answer 4

Why recursively ?

This would work fine and is about 10 times faster than the best recursive algorithm:

def minMax(array): return min(array),max(array)

To avoid having each recursion call itself twice, you could write the function like this:

def minMax(array):
    first,*rest = array  # first,rest = array[0],array[1:]
    if not rest : return first,first
    subMin,subMax = minMax(rest)
    return min(first,subMin), max(first,subMax)

If you want to avoid the maximum recursion limit (i.e. on large list) you could use a binary approach splitting the array in left and right parts. this will only use log(n) levels of recursion (and also reduce some of the processing overhead):

def minMax(array):
    size = len(array)
    if size == 1 : return array[0],array[0]
    midPoint = size // 2
    leftMin,leftMax   = minMax(array[:midPoint])
    rightMin,rightMax = minMax(array[midPoint:])
    return min(leftMin,rightMin), max(leftMin,rightMin)

If you want to reduce the overhead of array creation and function calls, you could pass down the index and avoid min(),max() and len() (but then you're using recursion as a for loop which pretty much defeats the purpose):

def minMax(array, index=None):
    index = (index or len(array)) - 1
    item = array[index]
    if index == 0 : return item,item
    subMin,subMax = minMax(array,index)
    if item < subMin: return item,subMax
    if item > subMax: return subMin,item
    return subMin,subMax

You can combine the previous two to reduce overhead and avoid recursion limit, but it is going lose a bit of performance:

def minMax(array, start=0, end=None):
    if end is None : end = len(array)-1
    if start >= end - 1:
        left,right = array[start],array[end]
        return (left,right) if left < right else (right,left)
    middle = (start + end) >> 1
    leftMin,leftMax   = minMax(array, start,middle)
    rightMin,rightMax = minMax(array, middle+1,end)
    return ( leftMin if leftMin < rightMin else rightMin ), \
           ( leftMax if leftMax > rightMax else rightMax )