查找列表中的最小元素（递归） - Python

Question

我试图使用递归在整数列表中找到最小值。主要的想法是，如果列表只有一个元素长，这个元素是我的最小值。否则，我将列表分成两个相同大小的较小列表，在两个列表中查找最小值，然后比较哪一个较小。代码如下所示：

def minimum(a,l,p):
    if l == p:
        return a[l]
    else:
        m1 = minimum(a,l, (l+p)/2)
        m2 = minimum(a, (l+p)/2 + 1, p)
        if m1 < m2:
            return m1
        else:
            return m2

这似乎并不困难，但是当我尝试为示例列表运行此函数时，我收到以下错误：“RecursionError：比较时超出了最大递归深度”。算法出了什么问题，或者我应该在其他地方查找这个问题的原因？

Answer 1

您提到的递归策略类似于二元搜索，当遍历树以查找通用值时，它最有效，因为假定树以排序方式构造以获得最大横向效率。但是，如果您真的想用递归来解决问题，那么您可以迭代列表本身：

def minimum(l, val):
  if not l[1:]:
     return val
  return minimum(l[1:], l[0] if l[0] < val else val)

l = [34, 23, 2, 4, 18]
print(minimum(l, l[0]))

输出：

2

Answer 2

最后，我相信这只是一个如何使用递归迭代列表而不是使用循环并用于学习目的的示例。您可以连续将列表拆分为两半，直到获得长度为1的列表，即表面元素时。如果您是出于学习目的而这样做，我建议您添加print()语句以查看列表正在执行的操作。

def minimum(lst):
    if len(lst) == 1:
        return lst[0]
    else:
        m1 = minimum(lst[0:len(lst) / 2])
        m2 = minimum(lst[len(lst) / 2:])
        if m1 < m2:
            return m1
        else:
            return m2


if __name__ == "__main__":
    print(minimum([3, 4, 1, 2, 5]))
    print(minimum([3, 2, 1, 0]))

但正如@HFBrowning在评论中提到的，在现实生活中你应该只使用min(lst)并完成它。

正如@PatrickHaugh在对此答案的评论中提到的那样，除法必须返回一个整数。这意味着，如果你在Python 3上运行它，你应该将len(lst) / 2更改为len(lst) // 2（参见double /？）

Answer 3

def RecursiveMin(L):
if len(L)==2:
    if L[0]<L[1]:
        return L[0]
    else:
        return L[1]
else:
    X= RecursiveMin(L[1:])
    if L[0]<X:
        return L[0]
    else:
        return X

此公式将为您提供列表中的最小值。

L=[99,45,78,34,67,2,34,88]
RecursiveMin(L)
>>> 2