Finding the maximum value in a vector using recursion C++

Question

I am trying to find the maximum value in a vector using recursion but I keep on getting a segmentation fault. I can't figure out the issue. Does anyone know why?

int find_max(vector<int> integer_array, int i) { //variable i just keeps track of the index starting at 0
    
   if(i == integer_array.size()-1) {
       return integer_array[i];
   }
    
    return max(integer_array[i], find_max(integer_array, i++));

}

//Example of a call: find_max(vector_array, 0);

UPDATE: I know it's inefficient but this is just for practicing recursion...

using recursion -- How many items in the vector? If there are thousands of items, you are risking blowing out the stack memory using recursion. And why use such an unorthodox way (recursion) to find the maximum value? There are valid reasons to use recursion, like tree traversal, but to find the max item in a vector?? — PaulMcKenzie
– PaulMcKenzie, Commented Sep 16, 2021 at 2:04
O(N^2) storage complexity + O(N) stack overhead... It's almost like you're trying to find the least efficient way to do this. — paddy
– paddy, Commented Sep 16, 2021 at 2:19

Chen · Accepted Answer · 2021-09-16 13:32:55Z

1

I am assuming the vector always has elements.

In the return statement, should be i+1 instead of i++:

return max(integer_array[i], find_max(integer_array, i+1));.

The problem with i++ is that this form would pass the value i to find_max for the second argument, and then increment. So you end up calling either return max(integer_array[i], find_max(integer_array, i)) or return max(integer_array[i+1], find_max(integer_array, i)), I forgot if the parameters were evaluated in order or not. In either case, it would not finish correctly.

Also I would suggest const ref for find_max 1st argument:

int find_max(const vector<int> &integer_array, int i). Otherwise it would copy the integer_array again and again without needing to modify the content. see reference.

Thanks for the comment from paddy, very helpful in my future drafting answers.

edited Sep 16, 2021 at 13:32

answered Sep 16, 2021 at 1:53

Chen

3303 silver badges14 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

paddy Over a year ago

Avoid instructing what to do without also saying why. Your "suggestion" actually touches on a super-important topic in C++. The way this algorithm has been written is devastating for both performance and memory overhead. You should describe the difference this small bit of syntax would make and why it's important.

Gis B Over a year ago

Thanks for the help! Is it because i++ doesn’t update until later?

Chen Over a year ago

Yes that's right.

Collectives™ on Stack Overflow

Finding the maximum value in a vector using recursion C++

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related