如何证明递归查找数组最大值代码的正确性？寻求合适实现方案

一、正确性证明（数学归纳法） #

你的函数可以通过数学归纳法证明其正确性：

1. 基础情况：当数组长度为1时，直接返回唯一元素，显然是该数组的最大值，逻辑成立。
2. 归纳假设：假设对于所有长度为k（k≥1）的数组，函数能正确返回最大值。
3. 归纳步骤：考虑长度为k+1的数组：
   • 函数会比较前两个元素，移除其中较小的那个，得到一个长度为k的新数组。
   • 根据归纳假设，这个长度为k的数组的最大值能被正确返回。
   • 由于移除的是前两个元素中的较小值，原数组的最大值必然保留在新数组中，因此最终返回的结果就是原数组的最大值。
     综上，对于所有长度≥1的数组，函数都能正确返回最大值。

二、关于pop的使用问题 #

你的实现里用pop存在明显的副作用：它会直接修改传入的原数组。比如调用函数后，原本的数组会被截断，后续再使用这个数组时数据已经丢失。这种修改输入参数的做法不符合常规编程规范，会降低代码的可维护性，还容易引发意外bug——这也是你在网上找不到类似实现的核心原因。

三、更合适的递归实现方案 #

推荐几种无副作用的递归实现，均不会修改原数组：

方案1：分治法（高效易理解） #

将数组分成两部分，分别查找每部分的最大值，再比较两者：

def max_recursive(items):
    if len(items) == 1:
        return items[0]
    mid = len(items) // 2
    left_max = max_recursive(items[:mid])
    right_max = max_recursive(items[mid:])
    return left_max if left_max >= right_max else right_max

方案2：基于索引的递归（无额外空间开销） #

通过传入起始和结束索引遍历数组，避免创建新数组：

def max_recursive(items, start=0, end=None):
    if end is None:
        end = len(items) - 1
    if start == end:
        return items[start]
    mid = (start + end) // 2
    left_max = max_recursive(items, start, mid)
    right_max = max_recursive(items, mid + 1, end)
    return left_max if left_max >= right_max else right_max

方案3：逐步比较法（极简递归） #

每次比较第一个元素和剩余数组的最大值：

def max_recursive(items):
    if not items:
        raise ValueError("空数组无最大值")
    if len(items) == 1:
        return items[0]
    rest_max = max_recursive(items[1:])
    return items[0] if items[0] >= rest_max else rest_max

内容的提问来源于stack exchange，提问作者Thomas