Итерация более эффективна, чем рекурсия, правильно? Тогда почему некоторые люди утверждают, что рекурсия лучше (более элегантная, по их словам), чем итерация? Я действительно не понимаю, почему некоторые языки, такие как Haskell, не позволяют итерации и поощряют рекурсию? Разве это не абсурдно поощрять то, что имеет плохую производительность (и это тоже, когда доступен более эффективный вариант, то есть рекурсия)? Прошу пролить свет на это. Спасибо.
Почему рекурсия должна быть предпочтительнее итерации?
Ответ 1
Итерация более эффективна, чем рекурсия, правильно?
Не обязательно. Эта концепция исходит из многих C-подобных языков, где вызов функции, рекурсивный или нет, имел большие накладные расходы и создал новый стековый фрейм для каждого вызова.
Для многих языков это не так, и рекурсия одинаково или более эффективна, чем итеративная версия. В наши дни даже некоторые компиляторы C переписывают некоторые рекурсивные конструкции в итеративную версию или повторно используют фрейм стека для хвостового рекурсивного вызова.
Ответ 2
Попробуйте выполнить поиск по глубине и рекурсивно и скажите, какой из них дал вам более легкое время. Или соберите сортировку. Для многих проблем сводится к тому, что явным образом поддерживаю ваш собственный стек и оставляю ваши данные в стеке функций.
Я не могу разговаривать с Haskell, поскольку я никогда не использовал его, но это касается более общей части вопроса, поставленного в вашем названии.
Ответ 3
Haskell не разрешает итерацию, потому что итерация включает изменяемое состояние (индекс).
Ответ 4
Как утверждали другие, в рекурсии нет ничего менее впечатляющего. Есть несколько языков, где он будет медленнее, но это не универсальное правило.
Говоря, для меня рекурсия - это инструмент, который будет использоваться, когда это имеет смысл. Есть некоторые алгоритмы, которые лучше представлены как рекурсия (как некоторые из них лучше с помощью итерации).
Пример:
fib 0 = 0
fib 1 = 1
fib n = fib(n-1) + fib(n-2)
Я не могу представить себе итерационное решение, которое могло бы сделать цель более ясной, чем это.
Ответ 5
Вот некоторая информация о плюсах и минусах рекурсии и итерации в c:
http://www.stanford.edu/~blp/writings/clc/recursion-vs-iteration.html
В основном для меня рекурсия иногда легче понять, чем итерация.
Ответ 6
Несколько вещей:
- Итерация не обязательно быстрее
- Корень всего зла: поощрение чего-то только потому, что оно может быть умеренно быстрее, преждевременно; есть и другие соображения.
- Рекурсия часто намного более лаконично и четко передает ваши намерения.
- Отключив изменяемое состояние, как правило, функциональные языки программирования легче рассуждать и отлаживать, а рекурсия - пример этого.
- Рекурсия занимает больше памяти, чем итерация.
Ответ 7
Итерация - это просто особая форма рекурсии.
Ответ 8
Я не думаю, что в рекурсии есть что-то по своей сути менее результативное - по крайней мере, в абстрактном. Рекурсия - это особая форма итерации. Если язык предназначен для поддержки рекурсии, возможно, он может выполнять так же хорошо, как итерацию.
В общем случае рекурсия делает явным представление о состоянии, которое вы выдвигаете на следующей итерации (это параметры). Это может облегчить параллелизацию исполнения языковыми процессорами. По крайней мере, это направление, которое разработчики языка пытаются использовать.
Ответ 9
В Java рекурсивные решения обычно превосходят нерекурсивные. В C он имеет тенденцию быть наоборот. Я думаю, что в целом это относится к адаптированным скомпилированным языкам или сравнению с компилируемыми языками.
Изменить: Под "вообще" я подразумеваю что-то вроде разделения 60/40. Это очень зависит от того, насколько эффективно язык обрабатывает вызовы методов. Я думаю, что компиляция JIT способствует рекурсии, потому что она может выбирать, как обрабатывать inline и использовать данные времени исполнения в оптимизации. Это очень зависит от алгоритма и компилятора, о котором идет речь. Java, в частности, продолжает усваивать обработку рекурсии.
Количественные результаты исследования с Java (ссылка в формате PDF). Обратите внимание, что это в основном алгоритмы сортировки и используются более старая виртуальная машина Java (1.5.x, если я правильно прав). Они иногда получают улучшение производительности 2: 1 или 4: 1, используя рекурсивную реализацию, и редко рекурсия значительно медленнее. В моем личном опыте разница не часто выражается, но 50 % улучшение является обычным явлением, когда я использую рекурсию разумно.
Ответ 10
Рекурсия - одна из тех вещей, которые кажутся элегантными или эффективными в теории, но на практике, как правило, менее эффективны (если компилятор или динамический рекомпилятор) не меняют то, что делает код. В общем, все, что вызывает ненужные вызовы подпрограмм, будет медленнее, особенно когда выкладывается/выскакивается более одного аргумента. Все, что вы можете сделать, чтобы удалить процессорные циклы, то есть инструкции, которые процессор должен пережевывать, - это честная игра. Составители могут сделать довольно хорошую работу в эти дни в целом, но всегда хорошо знать, как писать эффективный код вручную.
Ответ 11
Я думаю, что это поможет понять, что такое производительность. Эта ссылка показывает, как совершенно разумно закодированное приложение действительно имеет много возможностей для оптимизации, а именно 43-го! Ничего из этого не имело ничего общего с итерацией или рекурсией.
Когда приложение настроено так далеко, оно доходит до того момента, когда циклы, сохраненные путем итерации, против рекурсии могут действительно иметь значение.
Ответ 12
Как низкоуровневый ITERATION имеет дело с реестром CX для подсчета циклов и, конечно, реестров данных. RECURSION не только имеет дело с тем, что он также добавляет ссылки на указатель стека, чтобы сохранить ссылки на предыдущие вызовы, а затем, как вернуться.-
Мой преподаватель университета сказал мне, что все, что вы делаете с рекурсией, может быть выполнено с помощью Iterations и viceversa, однако иногда проще сделать это путем рекурсии, чем Iteration (более элегантный), но на уровне производительности лучше использовать итерации.-
Ответ 13
Рекурсия - это типичная реализация итерации. Это просто более низкий уровень абстракции (по крайней мере, на 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 happening.
for i in iterator(50):
print(i)
Ответ 14
Я бы сравнил рекурсию со взрывчаткой: вы можете достичь большого результата в кратчайшие сроки. Но если вы используете его без предосторожности, результат может быть катастрофическим.
Я был очень впечатлен, доказав сложность рекурсии, которая вычисляет числа Фибоначчи здесь. Рекурсия в этом случае имеет сложность O ((3/2) ^ n), а итерация - только O (n). Вычисление n = 46 с рекурсией, написанной на С#, занимает половину минуты! Ничего себе...
Рекурсия IMHO должна использоваться только в том случае, если природа объектов подходит для рекурсии (деревья, синтаксический анализ,...) и никогда из-за эстетики. Производительность и потребление ресурсов любого "божественного" рекурсивного кода необходимо тщательно изучить.
Ответ 15
Мне трудно рассуждать, что каждый лучше другого.
Im работает над мобильным приложением, которое должно выполнять фоновые работы с файловой системой пользователя. Один из фоновых потоков должен время от времени подметать всю файловую систему, чтобы поддерживать обновленные данные пользователю. Поэтому, опасаясь, я написал итеративный алгоритм. Сегодня я написал рекурсивный, для той же работы. К моему удивлению, итеративный алгоритм быстрее: рекурсивный → 37s, итеративный → 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-х алгоритмов выше, итерационный будет одним из конечного продукта.
Ответ 16
Итерация более эффективна, чем рекурсия, правильно?
Да.
Однако , когда у вас есть проблема, которая идеально соответствует рекурсивной структуре данных, лучшее решение всегда рекурсивно.
Если вы притворитесь, что решили проблему с итерациями, вы в конечном итоге изобретаете стек и создаете беспорядочный и уродливый код по сравнению с изящной рекурсивной версией кода.
Тем не менее Итерация всегда будет быстрее Рекурсии. (в архитектуре фон Неймана), поэтому, если вы всегда используете рекурсию, даже если цикл будет достаточным, вы заплатите штраф за производительность.
Ответ 17
"Итерация более результативна, чем рекурсия" на самом деле специфична для языка и/или для компилятора. Случай, который приходит в голову, - это когда компилятор делает цикл-разворачивание. Если вы внедрили рекурсивное решение в этом случае, это будет немного медленнее.
Здесь платит быть ученым (проверяя гипотезы) и знай свои инструменты...
Ответ 18
на пути ntfs UNC max как 32K
C:\A\B\X\C.... может быть создано более 16K папок...
Но вы даже не можете подсчитать количество папок с любым рекурсивным методом, рано или поздно все вызовут переполнение стека.
Для сканирования папок профессионально используется только хороший итеративный код с легким весом.
Верьте или нет, большинство лучших антивирусов не могут сканировать максимальную глубину UNC-папок.