using recursion only to extract the maximum elements in a vector in c++

Question

I am trying to extract the maximum element in a vector in c++ using recursion with only one parameter in the function:

int maxR(vector<int> v) {
    if (v.size() != 1) {
        if (v[v.size()-1] > v[v.size()-2]) {
            v[v.size()-2] = v[v.size()-1];
            v.pop_back();
  /*check what happens to v during recursion: cout << v[v.size()-1] <<endl;*/
            return maxR(v);
        }
        else {
            v.pop_back();
            return maxR(v);
        }
        return v[0];
    }
    }

int main() {
    vector<int> v = { 3,16,2,4,7,11,19 };
    cout << maxR(v);
}

So I was hoping it would return the number 19, but for some reasons, it return me a zero i.e 0.

So I added the line:

cout << v[v.size()-1] <<endl;

to see what is happening during recursion, and I got this: 19 19 19 19 19 19 0

So I am not sure what is wrong with my code?

could someone points out the error?

When your compiler give you a warning that a path does not returns a value, **fix it** when it is obvious that the code is wrong! — Phil1970, Sep 26 '19 at 03:52
Hey Phil1970, sorry what do you mean by the "path does not returns a value"? — john_w, Sep 26 '19 at 03:53
Learn to use a debugger! In less time that it took you to wrote the question, you should be able to understand what the code is doing. You main problem is because of the wrong placement of the return statement, you have an undefined behavior because you exit the function without calling return. A possible undefined behavior is that the returned value would be whatever happen to be in the register used to return a value. — Phil1970, Sep 26 '19 at 03:59
When the size of the vector is one, there is no return statement that can be reached in your function. Also, if you were properly indenting your code, such mistake could be found in less than 5 seconds. — Phil1970, Sep 26 '19 at 04:01
Please read [this](https://stackoverflow.com/questions/57842756/why-should-i-always-enable-compiler-warnings/) — n. m. could be an AI, Sep 26 '19 at 05:31

score 6 · Accepted Answer · edited Sep 26 '19 at 03:51

6

Move the return statement past the bracket just after it.

edited Sep 26 '19 at 03:51

Eugene

6,194
1
20
31

answered Sep 26 '19 at 03:41

גלעד ברקן

23,602
3
25
61

wow, thanks it works. But may I know what is wrong with my original code? like what was I outputting during the final step of recursion? why did I get 0 when I return v[0] in the "incorrect" code here? – john_w Sep 26 '19 at 03:51
@john_w I'm not too much of an expert on C++. I would read about how the compiler might handle no return statement for a function that's supposed to return an `int`. When the code reaches beyond the bracket for the case with only one element in the vector, there are no instructions. We might see behaviour different than zero across different setups. – גלעד ברקן Sep 26 '19 at 04:15

R Sahu · Answer 2 · 2019-09-26T04:13:08.260

You can see the flow of control in your code better by better indenting .

int maxR(vector<int> v) {
   if (v.size() != 1) {
      if (v[v.size()-1] > v[v.size()-2]) {
         v[v.size()-2] = v[v.size()-1];
         v.pop_back();
         return maxR(v);
      }
      else {
         v.pop_back();
         return maxR(v);
      }
      return v[0];
   }
   // No return statement when v.size() is equal to 1.
}

Now you can see that when v.size() is equal to 1, your function drops to the end where there is no return statement. Consequently, your code has undefined behavior. There is no point trying to make sense of "Why does the function return 0"? It can return anything, it can blow up the program, etc.

The fix is simple, and I suspect you would've seen it clearly with proper indenting. Move the return v[0]; line after the end of the if block.

int maxR(vector<int> v) {
   if (v.size() != 1) {
      if (v[v.size()-1] > v[v.size()-2]) {
         v[v.size()-2] = v[v.size()-1];
         v.pop_back();
         return maxR(v);
      }
      else {
         v.pop_back();
         return maxR(v);
      }
   }

   // The correct place for the return statement.
   return v[0];
}

FWIW, an improvement to the function would be:

int maxR(vector<int> v) {
   if (v.size() != 1) {
      if (v[v.size()-1] > v[v.size()-2]) {
         v[v.size()-2] = v[v.size()-1];
      }

      // No need to duplicate these lines.
      v.pop_back();
      return maxR(v);
   }

   // The correct place for the return statement.
   return v[0];
}

using recursion only to extract the maximum elements in a vector in c++

2 Answers2