Recursive Method To Find The Minimum Number In A List Of Numbers

Given this sample list: [5, 3, 9, 10, 8, 2, 7] How to find the minimum number using recursion? The answer is 2. I found this in a question paper while I was doing recursion exerci

Solution 1:

This is a recursive implementation of min:

l=[5, 3, 9, 10, 8, 2, 7]
def find_min(l,current_minimum = None):
    if not l:
        return current_minimum
    candidate=l.pop()
    if current_minimum==None or candidate<current_minimum:
        return find_min(l,candidate)
    return find_min(l,current_minimum)
print find_min(l)
>>>
2     

Take into account that this should not be used in real programs and should be treated as an exercise. The performance will be worse than the built-in minby several orders of magnitude.

Solution 2:

>>> import random
>>> arr=[random.randint(0,8) for r in xrange(10)]
>>> arr
[8, 2, 5, 1, 2, 4, 0, 3, 1, 1]
>>> def func(arr):
    if len(arr) == 1:
        return arr[0]
    else:
        return min(arr[0],func(arr[1:]))


>>> f(arr)
0

NB the recursion isn't really needed here.

Solution 3:

This answer uses an accumulator to store the min value throughout the recursions.

list = [5, 3, 9, 10, 8, 2, 7]

def min_list(list, min=None):
    if len(list) < 1:
        return min
    return min_list(list[1:], list[0] if min is None or list[0] < min else min)

print(min_list(list))

Solution 4:

Thats also working, but only for lists with a length that is a power of two. For other lengths you just have to tweak the split into smaller arrays. The approach is taken from merge sort.

def findCloseToZero(l):
    if len(l) == 1:
        return l[0]
    else:
        first = findCloseToZero(l[0:int(len(l)/2)])
        sec = findCloseToZero(l[int(len(l)/2):])

        return first if abs(first) < abs(sec) else sec

Solution 5:

def find_smallest_elem(lst):

k=1

while k != len(lst):

    if lst[0] > lst[k]:

        return(find_smallest_elem(lst[k:]))
    else:

        k +=1

return(lst[0])

This seems to works fine