Мне нравится рекурсия. Я думаю, что это упрощает многое. Другой может не согласиться; Я думаю, что это также упрощает чтение кода. Тем не менее, я заметил, что рекурсия не используется так много на таких языках, как С#, поскольку они находятся в LISP (который, кстати, является моим любимым языком из-за рекурсии).
Кто-нибудь знает, есть ли веские причины не использовать рекурсию на таких языках, как С#? Это дороже, чем итерация?
Они дороже, чем итераций?
Да, они есть. Многие варианты Lisp поддерживают идею оптимизации "хвостового вызова", которая позволяет преобразовывать многие вызовы рекурсивной функции в итеративный (это упрощает бит). Если tail-call не поддерживается, то вызов рекурсивной функции будет использовать в стеке все больше памяти.
Они дороже, чем итераций?
Да, они есть. Рекурсия требует создания нового фрейма стека вместе с вызовом и возвратом, тогда как для итерации обычно требуется только сравнение и ветвь, что делает ее значительно быстрее; однако компиляторы могут выполнять оптимизацию хвостового вызова при определенных рекурсивных вызовах (а именно хвостовых вызовах), которые позволяют им повторно использовать фрейм стека, делая рекурсивный вызов намного менее дорогостоящим и эффективно превращая их в итерацию. Схема фактически требует, чтобы компиляторы схемы реализовали оптимизацию хвостового вызова.
Функциональные языки, такие как Lisp и F #, могут реализовывать множество хвостовых рекурсивных функций как циклы и могут избежать накладных расходов на вызов функции. С# не поддерживает хвостовую рекурсию, хотя F # делает.
Компилятор и архитектура современных процессоров могут делать множество оптимизаций с итерацией, которые они не могут сделать с рекурсией. Например, способность процессора делать оптимистичные вычисления. Когда процессор находит итерационное пространство, он знает, сколько времени потребуется. С самого начала не нужно проверять каждый раз перед тем, как начать следующий цикл. Таким образом, они контактируют с операциями. Поскольку большинство ЦП могут выполнять несколько операций одновременно (через конвейерную обработку), вы можете решить итерационное пространство за меньшее время, чем рекурсия. Это даже с оптимизацией хвоста, потому что процессор фактически обрабатывает около 4 циклов за раз (для увеличения производительности x4). Это усиление будет зависеть от архитектуры процессора. Архитектура, вероятно, будет большой частью выигрыша, а процессоры последующих поколений еще больше увеличивают прибыль.
Настоящая проблема с рекурсией заключается в том, что наше оборудование основано на VonNeumann (достижимый вариант машины Тьюринга), а не Lisp, хотя есть несколько специализированных аппаратных средств Lisp, вы не найдете никаких рабочих столов с это:)
Есть много плюсов и минусов в использовании рекурсии. Определенно, простота кода является самой большой, которая также позволяет лучше ремонтировать код и меньше ошибок.
Самая большая опасность для рекурсии - это краевые случаи, когда алгоритм вырывается из-под контроля, чтобы прервать ограничение стека функций. Некоторые языки, язык ABB Progress для одного, имеют параметр для максимально допустимого уровня вложенных вызовов. Они обычно низки, и добавление рекурсии в микс может заставить приложение нарушить этот предел.
Короче говоря, рекурсия всегда должна выполняться с жесткими случаями завершения, иначе ее можно будет очень сложно отладить (из-за непредсказуемости) и может вызвать серьезные проблемы в производственном коде.
Для проблем с памятью и скоростью, если только этот метод не является коротким (временным), вызываемым много раз, это действительно не имеет значения, какова производительность.
Пример. Если вы используете рекурсию для сканирования всех файлов и папок на жестком диске, влияние производительности, которое рекурсия делает, является незначительной, чтобы время, затрачиваемое на попадание на жесткий диск, и получение информации о файловой системе. В этом случае рекурсия, вероятно, предпочтительна для итеративной обработки.
Другой пример. Если вы сканируете узлы древовидной структуры, итеративный процесс может быть более полезным, потому что мы не задействуем стек функций так сильно, что означает, что мы нажимаем меньше памяти и, вероятно, позволяем аппаратным средствам использовать больше кеширования. См. Ответ Роберта Гулда для более подробной информации.
Если алгоритм может быть выражен наиболее естественно в рекурсивной форме, и, если глубина стека мала (в диапазоне log (N), то есть типично < 20), то любыми способами используйте рекурсию. (Любое увеличение производительности за счет итерации будет небольшим постоянным фактором).
Если существует опасность того, что стек увеличится, и если ваша система языка/компилятора/времени выполнения не гарантирует оптимизацию хвостового вызова, вам следует избегать рекурсивных алгоритмов.
Кто-нибудь знает, есть ли веские причины не использовать рекурсию на таких языках, как С#? Это дороже, чем итерация?
Да, потому что С# не поддерживает хвостовая рекурсия. При использовании рекурсии для простой итерации с помощью больших коллекций вы можете легко получить исключение StackOverflowException и свернуть свое приложение, если вы слишком глубоко заработаете.
Выбор основан не только на проблеме, которую нужно решить, но и на используемом языке. В языках C-стиля (Java, С# или что у вас есть) мой коленный рефлекс должен избегать рекурсии, поскольку он выглядит совершенно чуждой мне (и я просто не могу думать рекурсивно), не говоря уже о потенциале стека. Тем не менее, есть некоторые проблемы, для которых почти не имеет смысла использовать что-либо иное, кроме рекурсивного обхода дерева, что является хорошим примером. Итеративное решение вполне правдоподобно, но код будет большим, более грубым и почти наверняка менее читаемым.
Тем не менее, более динамичный язык (например, Lisp или Python) идет на большие длины, чтобы сделать рекурсию более естественной. Мой личный ответ - сначала искать итеративное решение, независимо от того, в чем проблема, но различный пробег делает скачки.
В конце концов, лучшим вариантом, вероятно, просто написать его. Скорее всего, вы будете выбросить его один раз в любом случае.
Если проблему можно свести к итерации, тогда я повторяю.
Если проблема вызывает рекурсию (например, древовидная навигация), я возвращаюсь.
Как я уже сказал, я занимаюсь разработкой бизнес-приложений на С# - я уверен, что научное программирование имеет разные требования.
Схема - единственный диалект Lisp, о котором я знаю, требует оптимизации хвостового вызова, и они, как правило, часто используют рекурсию. В других диалектах Lisp, которые этого не требуют (например, Common Lisp), я не вижу, чтобы рекурсия использовалась больше, чем на любом другом языке.
Рекурсия (невозможно/намного сложнее) для распараллеливания, чем итерация
Современный cpus имеет несколько ядер, поэтому прямая оптимизация с parallel.for (и такие методы) становится намного сложнее, если вы планируете рекурсию.
Однако распараллеливание все еще довольно неясное, и относительно мало кто использует его еще.
Кроме того, я считаю, что рекурсивные альгос легче проектировать и думать, потому что они включают в себя чуть меньше кода и переменных одновременно. Обычно я перехожу на рекурсию, когда нет необходимости в производительности.
Я думаю, что рекурсивные функции должны быть помещены в стек - каждый раз, когда функция вызывает себя, другая копия этой функции переходит в стек функций и т.д. Проблема в том, что в какой-то момент в стеке не хватает места для хранения функций, поэтому, если числа становятся большими, рекурсивное решение может не работать. Я знаю, потому что он укусил меня в задницу - у меня была отличная рекурсивная функция для free() всего моего связанного списка, а затем я проверил ее с самым большим связанным списком, который мог бы сделать, и получил ошибку (я считаю, что это было segfault - определенно должен был переполнение стека:)).
Итерационные функции не имеют этих ошибок - на машинных языках они выражаются как простые "jmp" или "je" или так далее, поэтому они никогда не выходят из комнаты в стеке функций и, как правило, более чисты.
Это полностью субъективный вопрос, но если бы не тот факт, что рекурсия имеет лимит, встроенный в ваш компьютер, я бы сказал, что это гораздо лучшее решение. Некоторые итеративные решения проблем просто выглядят уродливыми, а рекурсивное решение выглядит намного чище и приятнее. Но это жизнь.
Когда речь идет о линейной структуре данных, такой как список или вектор, одна из причин предпочесть итеративную конструкцию над рекурсией, она лучше передает смысл вашего кода. Зачастую для читателя требуется больше усилий, чтобы различать структуру вашей программы, когда рекурсия используется без разбора, когда итерации достаточно.
Я просто выброшу туда, что в XSLT переменные доступны только для чтения после создания. Из-за этого вещи, которые будут выполняться с индексированными для циклов, например
for(int i=0; i < 3; i++) doIt(i);
фактически выполняются с рекурсией. Что-то эквивалентное
public rediculous(i) {
doIt(i);
if (i < 3) rediculous(i + 1);
}
Я бы действительно представил пример XSLT здесь, но все, что печатает, заставляет ребенка Иисуса плакать.