c++ - 如何使此递归函数从给定的起始位置返回最小的整数？

Question

此递归函数将起始位置作为输入，并从v[start]到v[v.size()-1]返回 vector 中的最小整数。但是程序只是崩溃了。
有人知道我在做什么错吗？
谢谢大家的帮助!

int Select_Smallest(const vector<int>&v, int start) {
    int small;
    if (v.size() == 1) { // if the vector has only 1 element
        return start;
    }   

    if (v.size() > 1) {
        if (start == 0) {
            if (v[start] < v[start + 1]) {
                small = start;
            }
        }
    }
    if (Select_Smallest(v, start + 1)) {
        if (v[start] < v[start + 1]) {
            if (v[start - 1] > v[start]) { // checks if the number before is greater than start
                small = start;
            }
        } else {
            small = small;  // if start == the last element in the vector
        }
    }
    return small;   
}

Answer 1

您的代码中存在多个问题:

当 vector 大小为1时，您返回的start不是 vector 中的值。

您总是使用索引start + 1递归，并在偏移量start处访问 vector ，最终通过访问 vector 的边界导致未定义的行为。

这是一个更简单的方法:

如果start大于或等于 vector 大小，则返回一些常规值，例如INT_MAX。

否则使用Select_Smallest的参数调用start+1，并返回其中的最小值和索引start处的值。

这是一个简单的尝试:

int Select_Smallest(const vector<int>&v, int start) {
    if (start < 0)
        start = 0;
    if (start >= v.size())
        return INT_MAX;
    else
        return min(v[start], Select_Smallest(v, start + 1));
}

此函数不使用尾递归，因此，除非编译器非常聪明，否则可能会导致大型数组的堆栈溢出。