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

Question

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

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

代码中存在多个问题：

• 当向量大小为 1 时，返回start它不是向量中的值。
• 您总是使用索引start + 1递归并在偏移量start处访问向量，最终通过超出向量边界的访问而导致未定义的行为。

这是一个更简单的方法：

• 如果start大于或等于向量大小，则返回一些常规值，例如INT_MAX。
• 否则，使用start+1参数调用Select_Smallest并返回其中最小的值和索引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));
}

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