Подтвердить что ты не робот

Рекурсия против циклов

Я столкнулся с проблемой, когда как рекурсия, так и использование цикла кажутся естественными решениями. Существует ли соглашение или "предпочтительный метод" для таких случаев? (Очевидно, это не так просто, как показано ниже)

Рекурсия

Item Search(string desired, Scope scope) {
    foreach(Item item in scope.items)
        if(item.name == desired)
            return item;

    return scope.Parent ? Search(desired, scope.Parent) : null;
}

Loop

Item Search(string desired, Scope scope) {
    for(Scope cur = scope; cur != null; cur = cur.Parent)
        foreach(Item item in cur.items)
            if(item.name == desired)
                return item;

    return null;
}
4b9b3361

ОТВЕТЫ

Ответ 1

Я выступаю за рекурсивные решения, если:

  • Реализация рекурсии намного проще, чем итеративное решение, обычно потому, что она использует структурный аспект проблемы таким образом, что итеративный подход не может

  • Я могу быть уверенным, что глубина рекурсии не вызовет, предполагая, что мы говорим о языке, который реализует рекурсию таким образом.

Условие 1, похоже, не имеет места здесь. Итеративное решение имеет одинаковую степень сложности, поэтому я придерживаюсь итеративного маршрута.

Ответ 2

Если производительность имеет значение, то сравнивайте оба варианта и выбирайте их на рациональной основе. Если нет, выберите вариант, основанный на сложности, с учетом возможного.

Существует классическая классическая книга Элементы стиля программирования (по Kernighan и Plauger), что алгоритм должен следовать структуре данных. То есть рекурсивные структуры часто обрабатываются более четко с помощью рекурсивных алгоритмов.

Ответ 3

Рекурсия используется для выражения алгоритма, который является естественно рекурсивным в более понятной форме. "Естественно рекурсивный" алгоритм - это тот, где ответ строится на ответах на более мелкие подзадачи, которые, в свою очередь, построены из ответов на все более мелкие подзадачи и т.д. Например, вычисление факториала.

В языке программирования, который не работает, итеративный подход почти всегда быстрее и эффективнее рекурсивного подхода, поэтому причиной использования рекурсии является ясность, а не скорость. Если рекурсивная реализация оказывается менее понятной, чем итеративная реализация, то непременно избегайте ее.

В этом конкретном случае я буду судить о том, что итеративная реализация будет более ясной.

Ответ 4

Если вы используете функциональный язык (кажется, не так), перейдите к рекурсии. Если нет, петля, вероятно, будет лучше понятна всем, кто работает над проектом. Конечно, некоторые задачи (например, рекурсивный поиск в каталоге) лучше подходят для рекурсии, чем другие.

Кроме того, если код не может быть оптимизирован для рекурсии хвоста, цикл будет более безопасным.

Ответ 5

Используйте цикл. Легче читать и понимать (код чтения всегда намного сложнее, чем писать), и, как правило, намного быстрее.

Ответ 6

Я бы сказал, что рекурсивная версия лучше понятна, но только с комментариями:

Item Search(string desired, Scope scope) {
    // search local items
    foreach(Item item in scope.items)
        if(item.name == desired)
            return item;

    // also search parent
    return scope.Parent ? Search(desired, scope.Parent) : null;
}

Намного легче объяснить эту версию. Попробуйте написать хороший комментарий к версии цикла, и вы увидите.

Ответ 7

Доказано, что все хвосто-рекурсивные алгоритмы могут быть развернуты в цикл, и наоборот. Вообще говоря, рекурсивная реализация рекурсивного алгоритма более понятна для программиста, чем реализация цикла, а также легче отлаживать. Также, как правило, реальная производительность реализации цикла будет быстрее, так как ветвь/скачок в цикле, как правило, быстрее выполняется, чем нажатие и выскакивание кадра стека.

Лично говоря, для хвостично-рекурсивных алгоритмов я предпочитаю придерживаться рекурсивной реализации во всех ситуациях, кроме наиболее интенсивных.

Ответ 8

Я предпочитаю циклы как

  • Рекурсия подвержена ошибкам
  • Весь код остается в одной функции/методе
  • Экономия памяти и скорости

Я использую стеки (схему LIFO), чтобы заставить петли работать

В java стеки покрываются интерфейсом Deque

// Get all the writable folders under one folder
// java-like pseudocode
void searchWritableDirs(Folder rootFolder){
    List<Folder> response = new List<Folder>(); // Results
    Deque<Folder> folderDeque = new Deque<Folder>(); // Stack with elements to inspect
    folderDeque.add(rootFolder);
    while( ! folderDeque.isEmpty()){
        Folder actual = folder.pop(); // Get last element
        if (actual.isWritable()) response.add(actual); // Add to response
        for(Folder actualSubfolder: actual.getSubFolder()) { 
            // Here we iterate subfolders, with this recursion is not needed
            folderDeque.push(actualSubfolder);
        } 
    } 
    log("Folders " + response.size());
 }

Менее сложный, более компактный, чем

// Get all the writable folders under one folder
// java-like pseudocode
void searchWritableDirs(Folder rootFolder){
    List<Folder> response = new List<Folder>(); // Results
    rec_searchWritableDirs(actualSubFolder,response);
    log("Folders " + response.size());
}

private void rec_searchWritableDirs(Folder actual,List<Folder> response) {
   if (actual.isWritable()) response.add(actual); // Add to response
   for(Folder actualSubfolder: actual.getSubFolder()) {
       // Here we iterate subfolders, recursion is needed
       rec_searchWritableDirs(actualSubFolder,response);
   }                
}

У последнего меньше кода, но две функции, и сложнее понять код, ИМХО.

Ответ 9

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

Ответ 10

Я обычно предпочитаю использование петель. Большинство хороших конструкций ООП позволят вам использовать циклы, не используя рекурсию (и, таким образом, останавливать программу от нажатия всех этих неприятных параметров и адресов в стек).

Он более полезен в процедурном коде, где логичнее думать рекурсивным образом (из-за того, что вы не можете легко сохранить состояние или метаданные (информацию?) и, таким образом, вы создаете больше ситуаций что было бы полезно использовать).

Рекурсия хороша для прототипа функции и/или записи базы, но после того, как вы знаете, что код работает, и вы возвращаетесь к нему во время фазы оптимизации, попробуйте заменить его на цикл.

Опять же, это все упрямо. Пойдите с тем, что лучше всего подходит вам.

Ответ 11

Если ваш код скомпилирован, это, скорее всего, мало изменит. Проведите некоторое тестирование и посмотрите, сколько памяти используется и как быстро оно работает.

Ответ 12

Если система, в которой вы работаете, имеет небольшой стек (встроенные системы), глубина рекурсии будет ограничена, поэтому выбор алгоритма на основе цикла будет желательным.

Ответ 13

Вы также можете написать цикл в более читаемом формате. C for(init;while;increment) имеют некоторые недостатки читаемости, так как команда increment упоминается в начале, но выполняется в конце цикла.

Также ВАШИ ДВА ОБРАЗЦОВ НЕ ЭКВИВАЛЕНТЫ. Рекурсивный образец не сработает, и цикл не будет, если вы его называете: Search(null,null). Это делает версию цикла лучше для меня.

Вот образцы, измененные (и предполагая, что значение null ложно)

Рекурсия (оптимизирован с фиксированным и хвостовым вызовами)

Item Search(string desired, Scope scope) {

    if (!scope) return null

    foreach(Item item in scope.items)
        if(item.name == desired)
            return item;

    //search parent (recursive)
    return Search(desired, scope.Parent);
}

Loop

Item Search(string desired, Scope scope) {
    // start
    Scope cur = scope;

    while(cur) {
        foreach(Item item in cur.items)
            if(item.name == desired)
                return item;

        //search parent
        cur = cur.Parent;

    } //loop

    return null;
}

Ответ 14

Избегайте рекурсии. Скорее всего, часть кода должна быть сохранена в конце концов в какой-то момент, и это будет легче, если это не будет сделано с рекурсией. Во-вторых, у него, скорее всего, будет более медленное время выполнения.