如何用递归实现Python中的“数组求最大值”？

Question

如何用递归实现Python中的“数组求最大值”？

下面是我编写的一个简单的测试代码

我想通过递归来实现

我在学习算法，学习递归。你知道吗

非常感谢！你知道吗

def max(list):
    if list == []:
        msg = "List: ..."    
        return msg

    max = list[0]
    for item in list[1:]:
        if item > max:
            max = item
    return max

data = [8,2,-690,4,12,-320,0, 98]
print(max(data))

Answer 1

如果您想使用递归，那么仔细地定义结束情况是非常重要的。你知道吗

很明显，列表中元素的最大值不是第一个元素就是其余元素的最大值：它是两个值中的最大值。这实际上就是您要寻找的递归。你知道吗

但是如果没有第一个元素会发生什么呢？您有一个空列表和一个未定义的行为。为什么不maximum([]) = 0？因为这会导致一些不一致：maximum([-1]) = greatest(-1, maximum([])) = greatest(-1, 0) = 0。（您也可以尝试maximum([]) == -math.inf，但这不是很直观！）你知道吗

如果列表的其余部分是空的呢？没问题，你只有一个元素，它是最大值。你知道吗

只需将此分析转化为代码：

def maximum(xs):
    if len(xs) == 0:
        raise ValueError()
    elif len(xs) == 1:
        return xs[0]
    else:
        u = xs[0]
        v = maximum(xs[1:])
        return u if u >= v else v # greatest(u, v)

更多关于maximum([])

我将尝试给maximum([])一个值。我重复上面的论点。对于任何给定的n，maximum([n]) = greatest(n, maximum([])) = n。这意味着，对于每个n，maximum([]) <= n。满足此条件的唯一值是-math.inf。为什么不定义maximum([]) == -math.inf？假设您创建了一个minimum函数。出于对称的原因，您必须定义minimum([]) == math.inf。因此它存在一个列表l0 = []，这样minimum(l0) > maximum(l0)。没有人会接受这种可能性。你知道吗

我们现在该怎么办？主要有两种可能性：防御性编程或使用合同。在防御性编程中，函数将检查它接收到的参数，如果其中一个参数不正确，函数将失败。我就是这么做的：

def maximum(xs):
    if len(xs) == 0:
           raise ValueError()
    ...

如果你使用契约，你基本上会说：如果你给这个函数一个空列表，那么行为是未定义的。它可能返回任何值，崩溃，循环永远。。。。在这里，你会有这样的东西：

def maximum(xs):
    """!!! xs must not be empty !!!"""
    ...

看起来是一样的，但是有很大的不同。您可以使用，作为maximum([])的返回值，因为现在很明显，它没有任何意义。一个试图检查minimum(l0) <= maximum(l0)是否l0 = []的人显然违反了合同，并且不会对结果感到惊讶。当然，如果你想让它变得健壮，你会写：

def maximum(xs):
    """PRECONDITION: xs must not be empty"""
    assert len(xs) != 0 # can be disabled at runtime at your own risks
    _maximum(xs)

def _maximum(xs):
    """no precondition here"""
    if len(xs) == 0:
        return -math.inf
    else:
        u = xs[0]
        v = _maximum(xs[1:])
        return u if u >= v else v # greatest(u, v)

Answer 2

尝试以下操作（根据OP的请求，使用递归）：

def largest(arr):
    if len(arr) == 2:
        return arr[1] if arr[1] > arr[0] else arr[0]
    else:
        return largest([arr[0], largest(arr[1:])])

没有使用内置函数（例如max），因为OP声明它们不希望使用任何内置函数。你知道吗

函数return的else部分要么是list的第一个元素，要么是列表中最大的数字（不包括第一个元素），具体取决于哪个数字较大。你知道吗

每次执行else部分时，largest(arr[1:])位检查没有第一个元素的arr中哪个数字最大。这意味着，在某一点上，arr将包含两个元素。当它这样做时，一行if语句用于比较这两个元素，return是较大的元素。你知道吗

最后，代码返回到第一级，return是最大的元素。你知道吗

Answer 3

我会写max和max_all

from math import inf

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

def max_all (x = -inf, *xs):
  if not xs:
    return x
  else:
    return max (x, max_all (*xs))

max_all可以用任意数量的参数调用

print (max_all (8, 2, -690, 4, 12, -320, 0, 98))
# 98

或者使用*到unpack arguments

data = [ 8, 2, -690, 4, 12, -320, 0, 98 ]

print (max_all (*data))
# 98

它甚至可以在0输入时工作

print (max_all ())
# -inf