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

Question

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

Answer 1

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

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

Answer 2

Рекурсия - это типичная реализация итерации. Это просто более низкий уровень абстракции (по крайней мере, в 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)

Answer 3

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

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

Answer 4

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

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

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

Answer 5

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

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

Answer 6

в ntfs UNC макс. Путь как 32K
C: \ A \ B \ X \ C .... можно создать более 16K папок ...

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

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

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

Answer 7

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

Да.

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

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

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

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

Answer 8

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

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