Как превратить итеративный список STL для функции цикла в рекурсию? - PullRequest
Новая
       38

Как превратить итеративный список STL для функции цикла в рекурсию?

0 голосов
/ 04 октября 2018

Итак, у меня есть простой цикл for внутри функции члена класса, который печатает имена студентов, которым университет хочет предложить поступление.StudentPreferenceList и SchoolName являются переменными-членами класса, а ostr - это файл, в который я хочу записать вывод. 

void School::printSchoolPreferences(std::ostream &ostr) const{

    std::list<std::string>::const_iterator name;
    ostr << SchoolName + " preference list:"<< std::endl;
    int rank = 1;

    for (name = SchoolPreferenceList.begin(); name != 
         SchoolPreferenceList.end(); name++){

         ostr << "  " << rank << ". " << *name << std::endl;
         rank++;
    }

}

Я пытаюсь теперь преобразовать эту функцию в рекурсивную функцию, и это то, что у меня есть до сих пор.Моя текущая попытка ниже приводит к множеству ошибок компиляции, и я буду очень признателен, если вы поможете мне разобраться, как это исправить.Спасибо. 

void School::func(int rank, std::list<std::string>::const_iterator 
                  name_rank, std::ostream &ostr){

     if (rank < SchoolPreferenceList.size()){
         ostr << "  " << rank << ". " << *name_rank << std::endl;
         func(rank++, name_rank++, ostr);
     }
}

void School::printSchoolPreferences(std::ostream &ostr) const{

    std::list<std::string>::const_iterator name;
    ostr << SchoolName + " preference list:"<< std::endl;

    int rank = 1;
    func(rank, name_rank, ostr);
}

Это ожидаемый результат: 

 university_of_michigan preference list:
   1. erin_jones
   2. john_smith
   3. joe_miller
   4. dave_roberts

1 Ответ

0 голосов
/ 04 октября 2018

Вот общая схема с короткими именами-заполнителями.

При следующей итерации: 

void do_something(const Container& c)
{
    // preamble
    for (auto it = c.begin(); it != c.end(); ++it)
    {
        // per-loop action on *it
    }
}

Вы можете написать следующую рекурсию: 

void do_aux(Container::const_iterator first, Container::const_iterator last)
{
    if (first == last) return;

    // per-loop action on *first

    ++first;
    return do_aux(first, last);
}

void do_something(const Container& c)
{
    // preamble
    do_aux(c.begin(), c.end());
}

Обратите внимание, что это хорошо хвостовая рекурсия, которая показывает существенную эквивалентность итерации и хвостовой рекурсии.Вспомогательная функция do_aux занимает место цикла, включая проверку состояния цикла и разрыв.Дополнительное состояние из преамбулы, которое необходимо в теле цикла, можно передать с помощью дополнительных аргументов do_aux.

...