CODEWITHSUNDEEP
c++recursion
john_w
john_w

Reputation: 701

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

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?

Upvotes: 0

Views: 269

Answers (2)

R Sahu
R Sahu

Reputation: 206727

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];
}

Upvotes: 1

גלעד ברקן
גלעד ברקן

Reputation: 23955

Move the return statement past the bracket just after it.

Upvotes: 6

Related Questions