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

Question

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

Рекурсия

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

Answer 1

Я предпочитаю рекурсивные решения, когда:

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

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

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

Answer 2

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

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

Answer 3

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

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

В этом конкретном случае я бы оценил итеративную реализацию как более понятную.

Answer 4

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

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

Answer 5

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

Answer 6

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

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

Я использую стеки (схему 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);
   }                
}

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

Answer 7

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

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

Answer 8

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

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

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

Answer 9

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

Answer 10

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

Короче говоря:

Всегда избегайте рекурсий, если вы можете сделать ту же самую единицу, которая будет производиться петлями!

Как работает рекурсия?

• Кадр в стековой памяти выделяется для одного вызова функции

• Кадр содержит ссылку на фактический метод

• Если у метода есть объекты, объекты помещаются в память кучи, а кадр будет содержать ссылку на эти объекты в памяти кучи.

• Эти шаги выполняются для каждого вызова метода!

Риски:

• StackOverFlow, когда в стеке нет памяти для размещения новых рекурсивных методов.

• OutOfMemory, когда у кучи нет памяти для размещения рекурсивных хранимых объектов.

Как работает цикл?

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

Риски:

• Единственный риск внутри цикла, когда ваше состояние просто никогда не будет существовать ... Ну, это не вызовет никаких сбоев или чего-либо еще, это просто не выйдет из цикла, если вы наивно делаете while(true):)

Тест:

Сделайте следующее в вашем программном обеспечении:

private Integer someFunction(){

return someFunction();
}

Вы получите StackOverFlow исключение в секунду и, возможно, OutOfMemory тоже

сделать второй:

while(true){

}

Программное обеспечение просто зависнет, и сбой не произойдет:

Последнее, но не менее важное - for петли:

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

Ссылка:

Распределение памяти на основе стека