Рекурсия или повторение?

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

29
задан z - 26 January 2009 в 21:20
поделиться

14 ответов

они более дорогой, чем повторения?

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

18
ответ дан 28 November 2019 в 01:00
поделиться

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

for(int i=0; i < 3; i++) doIt(i);

на самом деле сделаны с рекурсией. Что-то эквивалентное

public rediculous(i) {
    doIt(i);
    if (i < 3) rediculous(i + 1);
}

я на самом деле обеспечил бы пример XSLT здесь, но весь этот ввод заставляет Ребенка Jesus кричать.

0
ответ дан 28 November 2019 в 01:00
поделиться

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

0
ответ дан 28 November 2019 в 01:00
поделиться

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

Повторяющиеся функции не имеют этих ошибок - на машинном языке, они выражаются как или 'je's простого 'jmp или так на, таким образом, они никогда не выбегают из комнаты на функциональном стеке и являются, эффективно, инструментом для очистки.

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

0
ответ дан 28 November 2019 в 01:00
поделиться

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

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

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

2
ответ дан 28 November 2019 в 01:00
поделиться

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

1
ответ дан 28 November 2019 в 01:00
поделиться

Если проблема может быть уменьшена до повторения, то я выполняю итерации.

, Если проблема призывает к рекурсии (например, древовидная навигация) затем, я рекурсивно вызываю.

, Что, будучи сказанным я основной делаю приложения направления деятельности в C# - я уверен, что научное программирование имеет другой набор требований.

1
ответ дан 28 November 2019 в 01:00
поделиться

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

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

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

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

1
ответ дан 28 November 2019 в 01:00
поделиться

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

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

6
ответ дан 28 November 2019 в 01:00
поделиться

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

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

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

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

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

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

8
ответ дан 28 November 2019 в 01:00
поделиться

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

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

11
ответ дан 28 November 2019 в 01:00
поделиться

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

11
ответ дан 28 November 2019 в 01:00
поделиться

они более дорогой, чем повторения?

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

15
ответ дан 28 November 2019 в 01:00
поделиться

кто-либо знает, существуют ли какие-либо серьезные основания не, используют рекурсию на языках, таких как C#? Действительно ли это более дорого, чем повторение?

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

3
ответ дан 28 November 2019 в 01:00
поделиться
Другие вопросы по тегам:

Похожие вопросы: