C语言递归求数组最大值：分治法和线性递归实现

本文将介绍两种使用递归方法求数组最大值的实现方式：分治法和线性递归。

函数接口定义

int amax(int a[], int n);

其中 a 和 n 都是用户传入的参数。函数使用递归方法求数组 a 的最大值。

代码实现

#include <stdio.h>

// 方法一：分治法
int amax(int a[], int l, int n) {
    if (n == 1) return a[l]; // 只有一个元素，直接返回
    int mid = l + n / 2;
    int left_max = amax(a, l, mid); // 递归求左半部分最大值
    int right_max = amax(a, mid, n - mid); // 递归求右半部分最大值
    return left_max > right_max ? left_max : right_max; // 取左右部分的最大值
}

// 方法二：线性递归
int amax(int a[], int l, int n) {
    if (n == 1) return a[l]; // 只有一个元素，直接返回
    int max = amax(a, l, n - 1); // 递归求前n-1个元素的最大值
    return max > a[l + n - 1] ? max : a[l + n - 1]; // 取前n-1个元素的最大值和第n个元素的较大值
}

int main() {
    int a[10], i, max;
    for (i = 0; i < 10; i++) {
        scanf("%d", &a[i]);
    }
    max = amax(a, 0, 10);
    printf('max=%d\n', max);
    return 0;
}

解释

方法一：分治法

**递归基准情况：**当数组只有一个元素时，直接返回该元素。
递归步骤：
- 将数组分成左右两部分。
- 递归调用 amax() 函数分别求解左右两部分的最大值。
- 返回左右两部分最大值中较大的那个。

方法二：线性递归

**递归基准情况：**当数组只有一个元素时，直接返回该元素。
递归步骤：
- 递归调用 amax() 函数求解前 n-1 个元素的最大值。
- 将第 n 个元素与前 n-1 个元素的最大值进行比较，返回较大的那个。

总结

本文介绍了两种使用递归方法求数组最大值的实现方式：分治法和线性递归。分治法将问题分解为更小的子问题，然后递归解决子问题，最后合并结果。线性递归则通过逐个比较元素来找到最大值。两种方法各有优劣，您可以根据实际情况选择合适的实现方式。

注意： 以上代码示例仅供参考，您可能需要根据实际需求进行修改和完善。