Рекурсия или итерация?

Question

Я люблю рекурсию. Я думаю, что это сильно упрощает вещи. Другой может не согласиться; Я думаю, что это также делает код намного проще для чтения. Тем не менее, я заметил, что рекурсия не так часто используется в таких языках, как C #, как в LISP (что, кстати, является моим любимым языком из-за рекурсии).

Кто-нибудь знает, есть ли веские причины не использовать рекурсию в таких языках, как C #? Это дороже, чем итерация?

Answer 1

Они дороже, чем Итерации?

Да, они есть. Многие варианты Lisp поддерживают идею «оптимизации хвостового вызова», которая позволяет преобразовывать многие виды использования рекурсивного вызова функции в итеративный (это немного упрощает). Если хвостовой вызов не поддерживается, то рекурсивный вызов функции будет постепенно увеличивать объем памяти в стеке.

Answer 2

Они дороже, чем Итерации?

Да, они есть. Рекурсия требует создания нового стекового фрейма вместе с вызовом и возвратом, тогда как итерация обычно требует только сравнения и ветвления, что делает его существенно быстрее; однако компиляторы могут выполнять оптимизацию хвостовых вызовов для определенных рекурсивных вызовов (а именно хвостовых вызовов), которые позволяют им повторно использовать кадр стека, делая рекурсивный вызов намного менее дорогостоящим и эффективно превращая их в итерацию. Схема фактически требует, чтобы компиляторы схемы реализовали оптимизацию хвостового вызова.

Answer 3

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

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

Answer 4

Функциональные языки, такие как Lisp и F #, могут реализовывать многие хвостовые рекурсивные функции внутри себя в виде циклов и могут избежать затрат на стек при вызове функции. C # не поддерживает хвостовую рекурсию, хотя F # поддерживает.

Answer 5

Есть много плюсов и минусов в использовании рекурсии. Определенно, простота кода - самая большая, которая также обеспечивает лучшую поддержку кода и меньше ошибок.

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

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

Что касается проблем с памятью и скоростью, если этот метод сам по себе не является кратким (с точки зрения времени), который вызывается много раз, на самом деле не имеет значения, какова производительность.

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

Другой пример: если вы сканируете узлы древовидной структуры, итерационный процесс может оказаться более полезным, поскольку мы не задействуем столько стека функций, что означает, что мы используем меньше памяти и, возможно, позволяем оборудованию использовать больше кэширования. См. Ответ Роберта Гулда для более подробной информации.

Answer 6

Если алгоритм может быть наиболее естественно выражен в рекурсивной форме, и , если глубина стека мала (в диапазоне log (N), то есть обычно <20), то любым способом используйте рекурсию , (Любое увеличение производительности за счет итерации будет небольшим постоянным фактором). </p>

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

Answer 7

Кто-нибудь знает, есть ли веские причины не использовать рекурсию в таких языках, как C #? Это дороже, чем итерация?

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

Answer 8

Выбор зависит не только от решаемой проблемы, но и от используемого языка. В языках стиля C (Java, C # или что у вас есть) мой ответ колен дергается, чтобы избежать рекурсии, поскольку это выглядит совершенно чуждо мне (и я просто не могу думать рекурсивно), чтобы не говоря уже о возможности злоупотребления стека. Однако есть некоторые проблемы, для которых практически нет смысла использовать что-либо , отличное , кроме рекурсии - хороший пример - обход дерева. Итеративное решение вполне правдоподобно, но код будет больше, объемнее и почти наверняка менее читабелен.

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

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

Answer 9

рекурсия (невозможно / намного сложнее) распараллелить, чем итерация

Современные процессоры имеют многоядерные процессоры, поэтому прямая оптимизация с parallel.for (и такими методами) становится намного сложнее, если вы спроектировали для рекурсии.

Однако распараллеливание все еще довольно неясно, и лишь немногие его используют.

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

Answer 10

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