используя только рекурсию для извлечения максимального количества элементов вектора в с ++ - PullRequest
Новая
       10

используя только рекурсию для извлечения максимального количества элементов вектора в с ++

0 голосов
/ 26 сентября 2019

Я пытаюсь извлечь максимальный элемент из вектора в c ++, используя рекурсию только с одним параметром в функции: 

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

Так что я надеялся, что он вернет число 19, но по некоторым причинам, он возвращает мне ноль, т. е. 0.

Поэтому я добавил строку: 

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

, чтобы увидеть, что происходит во время рекурсии, и я получил это: 19 19 19 19 19 19 0

Так что я не уверен, что не так с моим кодом?

Может кто-то укажет на ошибку?

Ответы [ 2 ]

6 голосов
/ 26 сентября 2019

Переместить инструкцию возврата за скобку сразу после нее.

1 голос
/ 26 сентября 2019

Вы можете лучше видеть поток управления в своем коде, улучшив отступ. 

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.
}

Теперь вы можете видеть, что когда v.size() равно 1, ваша функция падает до конца, где естьнет return заявление.Следовательно, ваш код имеет неопределенное поведение.Нет смысла пытаться понять смысл «Почему функция возвращает 0»?Он может вернуть все что угодно, может взорвать программу и т. Д.

Исправление простое, и я подозреваю, что вы бы видели это ясно с правильным отступом.Переместите строку return v[0]; после конца блока if. 

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, улучшение функции будет следующим: 

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