递归函数溢出

Question

所以我正在编写这个使用递归计算向量最大值的练习代码，由于某种原因，我在 return 语句上溢出。

代码如下：

template<typename T>
T max_helper(vector<T> v, T max, int i){
    T m = v[i];
    cout << "Max: " << max << "\n";
    if (i < v.size()-1) {
        if (m > max) max_helper(v, m, ++i);
        else max_helper(v, max, ++i);
    }
    else {
        cout << "Max2: " << max;
        return max;
    }
}

template<typename T>
T maximum(vector<T> v){
    T max = max_helper(v, 0, 0);
    cout << "\nMax3: " << max;
    if (max > v[v.size()-1]) return max;
    else return v[v.size()-1];
}

int main() {
    int seed = static_cast<int>(time(0));
    srand(seed);
    vector<int> v(20);
    for(unsigned int i=0; i<v.size(); i++){
        v[i] = 1+rand() % 100;
    }

    int r = maximum(v);
    cout << "\n";
    for (auto i: v) cout << i << " ";
    cout << "\nLargest element: " << r;

    return 0;
}

return 语句：

Max: 97
Max2: 97
Max3: 6421696
5 19 24 9 85 78 59 1 15 31 36 54 13 19 80 84 56 42 97 21
Largest element: 6421696

知道为什么会这样吗？

Answer 1

如果 i < v.size()-1) 是 true，max_helper 没有 return 任何值，因此您的程序具有未定义的行为。

你应该return一些东西。示例：

template<typename T>
T max_helper(vector<T> v, T max, int i){
    T m = v[i];
    cout << "Max: " << max << "\n";
    if (i < v.size()-1) {
        if (m > max) return max_helper(v, m, ++i); // return added
        else return max_helper(v, max, ++i);       // return added
    }
    else {
        cout << "Max2: " << max;
        return max;
    }
}

Demo

递归函数溢出

Overflow in recursive function

c++

recursion

overflow