求数字列表中最小数的递归方法

Question

鉴于这份样本清单：

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

如何使用递归找到最小数目？答案是2。

我在做递归练习的时候在一份试题中发现了这一点。我想不出解决这个问题的办法。要找到它，我必须先对列表进行排序，然后就没有什么可递归处理的了。有人能给我指明一条路吗？

Answer 1

这是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     

考虑到这一点不应在实际程序中使用，而应被视为一种练习。性能将比内置min差几个数量级。

Answer 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，，这里并不真正需要递归。

Answer 3

此答案使用累加器在递归过程中存储min值。

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))