Почему рекурсия должна быть предпочтительнее итерации?

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

Я не могу говорить с Хаскеллом, поскольку я никогда не использовал его, но это касается более общей части вопроса, поставленного в вашем названии.

Haskell не допускает итерации, потому что итерация включает изменяемое состояние (индекс).

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

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

пример:

fib 0 = 0
fib 1 = 1
fib n = fib(n-1) + fib(n-2)

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

вот некоторая информация о плюсах и минусах рекурсии и итерации в c:

http://www.stanford.edu/~blp/writings/clc/recursion-vs-iteration.html

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

итерация - это просто особая форма рекурсии.

несколько вещей:

1. итерация не обязательно быстрее
2. корень всех зол: обнадеживает то, только потому, что это может быть умеренно быстрее преждевременно; есть и другие соображения.
3. рекурсия часто гораздо более лаконично и четко передает ваши намерения
4. избегая изменчивого состояния вообще, функциональные языки программирования легче рассуждать и отлаживать, а рекурсия является примером этот.
5. рекурсия занимает больше памяти, чем итерационные.

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

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

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

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

изменить: Под "вообще" я имею в виду что-то вроде разделения 60/40. Это очень зависит от того, насколько эффективно язык обрабатывает вызовы методов. Я думаю, что компиляция JIT способствует рекурсии, потому что она может выбирать, как обрабатывать встраивание и использовать данные времени выполнения оптимизация. Это очень зависит от алгоритма и компилятора, о котором идет речь. Java, в частности, продолжает становиться умнее в отношении обработки рекурсии.

количественные результаты исследования с Java (PDF link). Обратите внимание, что это в основном алгоритмы сортировки и используют более старую виртуальную машину Java (1.5.x, если я правильно читаю). они иногда получают 2:1 или 4:1 улучшение производительности с помощью рекурсивной реализации, и редко рекурсия значительно замедлившийся. по моему личному опыту, разница не часто так выражена, но 50% улучшение является общим, когда я использую рекурсию разумно.

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

Im работает над мобильным приложением, которое должно выполнять фоновую работу в файловой системе пользователя. Один из фоновых потоков должен время от времени охватывать всю файловую систему, чтобы поддерживать обновленные данные для пользователя. Поэтому, опасаясь переполнения стека, я написал итерационный алгоритм. Сегодня я написал рекурсивный, для той же работы. К моему удивлению, итерационный алгоритм быстрее: рекурсивный -> 37С, iterative - > 34s (работа над одной и той же файловой структурой).

рекурсивные:

private long recursive(File rootFile, long counter) {
            long duration = 0;
            sendScanUpdateSignal(rootFile.getAbsolutePath());
            if(rootFile.isDirectory()) {
                File[] files = getChildren(rootFile, MUSIC_FILE_FILTER);
                for(int i = 0; i < files.length; i++) {
                    duration += recursive(files[i], counter);
                }
                if(duration != 0) {
                    dhm.put(rootFile.getAbsolutePath(), duration);
                    updateDurationInUI(rootFile.getAbsolutePath(), duration);
                }   
            }
            else if(!rootFile.isDirectory() && checkExtension(rootFile.getAbsolutePath())) {
                duration = getDuration(rootFile);
                dhm.put(rootFile.getAbsolutePath(), getDuration(rootFile));
                updateDurationInUI(rootFile.getAbsolutePath(), duration);
            }  
            return counter + duration;
        }

итерационного: - итеративная глубина-первый поиск, с рекурсивным возвратом

private void traversal(File file) {
            int pointer = 0;
            File[] files;
            boolean hadMusic = false;
            long parentTimeCounter = 0;
            while(file != null) {
                sendScanUpdateSignal(file.getAbsolutePath());
                try {
                    Thread.sleep(Constants.THREADS_SLEEP_CONSTANTS.TRAVERSAL);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }

                files = getChildren(file, MUSIC_FILE_FILTER);

                if(!file.isDirectory() && checkExtension(file.getAbsolutePath())) {
                    hadMusic = true;
                    long duration = getDuration(file);
                    parentTimeCounter = parentTimeCounter + duration;
                    dhm.put(file.getAbsolutePath(), duration);
                    updateDurationInUI(file.getAbsolutePath(), duration);
                }

                if(files != null && pointer < files.length) {
                    file = getChildren(file,MUSIC_FILE_FILTER)[pointer];
                }
                else if(files != null && pointer+1 < files.length) {
                    file = files[pointer+1];
                    pointer++;
                }
                else {
                    pointer=0;
                    file = getNextSybling(file, hadMusic, parentTimeCounter);
                    hadMusic = false;
                    parentTimeCounter = 0;
                }
            }
        }

private File getNextSybling(File file, boolean hadMusic, long timeCounter) {
            File result= null;
            //se o file é /mnt, para
            if(file.getAbsolutePath().compareTo(userSDBasePointer.getParentFile().getAbsolutePath()) == 0) {
                return result;
            }
            File parent = file.getParentFile();
            long parentDuration = 0;
            if(hadMusic) { 
                if(dhm.containsKey(parent.getAbsolutePath())) {
                    long savedValue = dhm.get(parent.getAbsolutePath());
                    parentDuration = savedValue + timeCounter;
                }
                else {
                    parentDuration = timeCounter; 
                }
                dhm.put(parent.getAbsolutePath(), parentDuration);
                updateDurationInUI(parent.getAbsolutePath(), parentDuration);
            }

            //procura irmao seguinte
            File[] syblings = getChildren(parent,MUSIC_FILE_FILTER);
            for(int i = 0; i < syblings.length; i++) {
                if(syblings[i].getAbsolutePath().compareTo(file.getAbsolutePath())==0) {
                    if(i+1 < syblings.length) {
                        result = syblings[i+1];
                    }
                    break;
                }
            }
            //backtracking - adiciona pai, se tiver filhos musica
            if(result == null) {
                result = getNextSybling(parent, hadMusic, parentDuration);
            }
            return result;
        }

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

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

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

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

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

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

рекурсия является типичной реализацией итерации. Это просто более низкий уровень абстракции (по крайней мере в Python):

class iterator(object):
    def __init__(self, max):
        self.count = 0
        self.max = max

    def __iter__(self):
        return self

    # I believe this changes to __next__ in Python 3000
    def next(self):
        if self.count == self.max:
            raise StopIteration
        else:
            self.count += 1
            return self.count - 1

# At this level, iteration is the name of the game, but
# in the implementation, recursion is clearly what's happening.
for i in iterator(50):
    print(i)

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

меня очень впечатлило доказательство сложности для рекурсии, которая вычисляет числа Фибоначчи здесь. Рекурсия в этом случае имеет сложность O((3/2)^n), в то время как итерация просто O(n). Вычисление n=46 с рекурсией, написанной на c#, занимает полминуты! Круто...

ИМХО рекурсия должна быть используется только в том случае, если природа сущностей хорошо подходит для рекурсии (деревья, синтаксический разбор,...) и никогда из-за эстетики. Производительность и потребление ресурсов любого "божественного" рекурсивного кода должны быть тщательно изучены.

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

вот где стоит быть ученым (проверка гипотез) и знать свои инструменты...

итерация более эффективна, чем рекурсия, верно?

да.

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

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

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

рекурсия когда-либо быстрее, чем цикл?

на ntfs UNC max path as is 32K
C:\A\B\X\C.... можно создать более 16K папок...

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

только хороший легкий итерационный код должен использоваться для профессионального сканирования папок.

Верьте или нет, большинство лучших антивирусов не может сканировать максимальную глубину папок UNC.