python两路递归求最大值

以下是两种递归方式求最大值的 Python 实现：

1. 分治法

使用分治法求最大值时，将序列分成左右两半，分别递归求出左半部分和右半部分的最大值，然后再比较两个最大值，取其中较大的一个作为整个序列的最大值。

def max_num(arr):
    n = len(arr)
    if n == 1:
        return arr[0]
    else:
        mid = n // 2
        left_max = max_num(arr[:mid])
        right_max = max_num(arr[mid:])
        return max(left_max, right_max)

2. 递归法

使用递归法求最大值时，将序列的第一个元素作为当前最大值，然后递归地比较当前最大值和其余元素，如果遇到比当前最大值更大的元素，则更新当前最大值。

def max_num(arr):
    n = len(arr)
    if n == 1:
        return arr[0]
    else:
        current_max = arr[0]
        rest_max = max_num(arr[1:])
        return max(current_max, rest_max)

以上两种方法的时间复杂度都为 O(nlogn)，其中分治法的空间复杂度稍微优于递归法。

相关问题

python递归求最大值

可以使用递归函数来求列表中的最大值，可以参考如下代码：

def find_max(lst):
    if len(lst) == 1:
        return lst[0]
    else:
        return max(lst[0], find_max(lst[1:]))
    
lst = [3, 5, 1, 8, 2]
print(find_max(lst)) # 输出：8

代码解析：

- `find_max`函数接收一个列表作为参数，使用递归的方法来实现求最大值，当列表长度为1时，直接返回唯一的元素值
- 当列表长度大于1时，使用`max`函数来计算首元素和剩余元素列表的最大值，`find_max(lst[1:])`表示从第二个元素开始的子列表
- 在主函数中，定义一个列表`lst`并调用`find_max`函数来求列表中的最大值

用python递归求数组最大值

可以使用递归的方式来实现求数组的最大值。

首先，我们需要明确递归的终止条件，即当数组只有一个元素时，它的最大值就是它本身。

接着，我们可以将数组分为左右两个部分，递归求出左半部分和右半部分的最大值，然后比较它们的大小，返回较大的值作为整个数组的最大值。

以下是示例代码：

def max_in_array(arr):
    n = len(arr)
    if n == 1:
        return arr[0]
    else:
        mid = n // 2
        left_max = max_in_array(arr[:mid])
        right_max = max_in_array(arr[mid:])
        return max(left_max, right_max)

在这个函数中，我们首先计算数组的长度，如果长度为1，那么直接返回数组唯一的元素。

否则，我们计算数组中间位置，将数组分为左右两半，分别递归求出左半部分和右半部分的最大值。

最后，我们将左半部分的最大值和右半部分的最大值进行比较，返回较大的值作为整个数组的最大值。

示例调用：

arr = [1, 3, 5, 7, 2, 4, 6, 8]
print(max_in_array(arr))  # 输出 8