递归实现最长相邻递增子序列长度：输出错误调试求助

看起来你对递归的思路有点走偏了，现在的increasing_sequences_recursive函数逻辑完全没有贴合“相邻递增子序列”的需求，这才导致输出结果完全不对。咱们一步步来分析问题，然后修正代码：

问题出在哪？ #

你的当前实现有几个核心错误：

• 递归逻辑方向错误：你现在的代码是把递归返回的结果累加，这会让最终结果变成所有元素的数量总和（比如你输入了12个元素，就输出12），完全不是在统计最长递增序列的长度。
• 错误的比较对象：你调用largestElement拿前n个元素的最大值和当前元素比较，但相邻递增只需要比较当前元素和它的前一个元素，和整个前n个的最大值没有任何关系。
• maxCounter维护失效：每次递归都把maxCounter初始化为0，没办法正确跟踪整个递归过程中出现的最长序列长度。

正确的递归思路 #

最长相邻递增子序列的核心是连续的元素对是否递增，递归的逻辑应该围绕这个点展开：

1. 我们可以定义递归函数的作用：返回从数组开头到第idx个元素时，当前正在延续的递增序列长度，同时通过引用传递一个变量来跟踪整个过程中的最大值。
2. 递归终止条件：当idx == 0时，只有一个元素，当前序列长度是1，最大值也是1。
3. 递归步骤：
   • 先递归处理前idx-1个元素，得到前一个位置的当前序列长度
   • 如果当前元素numbers[idx] > numbers[idx-1]，那么当前序列长度就是前一个长度+1
   • 否则，当前序列长度重置为1
   • 更新全局最大值（如果当前序列长度比最大值大）

修正后的代码 #

首先修正主函数里的小问题（你之前把startIdx设为numbers.size()，这会导致索引越界，应该从最后一个元素的索引numbers.size()-1开始）：

#include <iostream>
#include <vector>
#include "increasing_sequences_recursive.hpp"

// 辅助递归函数，currentLen是当前延续的递增序列长度，maxLen是跟踪的最大值
void helper(const std::vector<int>& numbers, int idx, int& currentLen, int& maxLen) {
    if (idx == 0) {
        currentLen = 1;
        maxLen = 1;
        return;
    }
    // 先递归处理前一个元素
    helper(numbers, idx - 1, currentLen, maxLen);
    
    // 比较当前元素和前一个元素
    if (numbers[idx] > numbers[idx - 1]) {
        currentLen++;
        // 更新最大值
        if (currentLen > maxLen) {
            maxLen = currentLen;
        }
    } else {
        // 递增中断，重置当前长度
        currentLen = 1;
    }
}

// 对外的递归函数，封装helper
int increasing_sequences_recursive(const std::vector<int>& numbers) {
    if (numbers.empty()) {
        return 0;
    }
    int currentLen = 0;
    int maxLen = 0;
    helper(numbers, numbers.size() - 1, currentLen, maxLen);
    return maxLen;
}

// 你的largestElement函数是正常的，这里保留
int largestElement(std::vector<int> &numbers, int n) {
    if (n == 1) return numbers[n - 1];
    int res = largestElement(numbers, n - 1);
    if (res > numbers[n - 1]) return res;
    return numbers[n - 1];
}

int main() {
    std::vector<int> numbers;
    int input;
    std::cout << "Enter a set of numbers (0 to stop): " << std::endl;
    while (true) {
        std::cin >> input;
        if (input != 0) {
            numbers.push_back(input);
        } else {
            break;
        }
    }
    if (numbers.empty()) {
        std::cout << "Length of longest sequence: 0" << std::endl;
    } else {
        std::cout << "Length of longest sequence: " << increasing_sequences_recursive(numbers) << std::endl;
    }
    return 0;
}

逻辑解释 #

• 新增的helper递归函数负责逐个处理元素，通过引用传递currentLen和maxLen，确保递归过程中能持续跟踪当前递增序列长度和全局最长长度。
• 递归从最后一个元素往前推进，每次先处理前一个元素，再判断当前元素是否能延续递增序列，以此更新长度值。
• 主函数补充了空数组的边界处理，避免递归出现异常。

比如输入测试序列1,2,3,2,4,5,6，程序会输出4，完全符合你的预期。

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