如何仅用递归实现vector数组的maxVal最大值查找函数？

原代码存在的问题 #

• 终止条件错误：当i超过数组最后一个索引时返回1，若数组中有小于1的元素，结果会完全错误。正确的基准情况应该是当i指向最后一个元素时，直接返回该元素。
• 返回值逻辑错误：原代码返回的是布尔值（比较结果转成int的1或0），而非两个值中的较大者，完全不符合函数返回最大值的要求。
• 缺失默认参数：函数定义未添加题目要求的int i = 0默认参数，导致调用时必须传入第二个参数。

修正后的代码 #

#include <iostream>
#include <vector>
using namespace std;

int maxVal(const vector<int> &arr, int i = 0)
{
    // 基准情况：当前是最后一个元素，直接返回它
    if (i == arr.size() - 1)
    {
        return arr[i];
    }

    // 递归获取剩余子数组的最大值，再和当前元素比较返回较大者
    int subMax = maxVal(arr, i + 1);
    return (subMax > arr[i]) ? subMax : arr[i];
}

int main()
{
    vector<int> arr = {3, 7, 1, 9, 4, 6, 2};

    cout << "Max Value (Using Recursion) = " << maxVal(arr);
    return 0;
}

递归逻辑说明 #

递归的核心是将问题拆解为更小的子问题：

1. 当递归到数组最后一个元素时，该元素就是当前子数组的最大值，作为基准返回。
2. 对于当前索引i，先递归计算从i+1开始的子数组的最大值，再将其与arr[i]比较，返回两者中的较大值。通过逐层回溯，最终得到整个数组的最大值。

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