Каково влияние рекурсии на сервер?

Question

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

Answer 1

Рекурсия может потенциально потреблять больше памяти, чем эквивалентное итеративное решение, поскольку последнее может быть оптимизировано так, чтобы занимать только ту память, которая ему строго необходима, но рекурсия сохраняет все локальные переменные в стеке, таким образом занимая немного больше, чем строго необходимо , Это проблема только в среде с ограниченным объемом памяти (что не редкость) и для потенциально очень глубокой рекурсии (несколько десятков рекурсивных ножек, каждая из которых занимает максимум несколько сотен байт, будут не измеримо повлиять объем памяти сервера), поэтому «последнее средство» является перекупом.

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

Answer 2

Я слышал, что выполнение рекурсивного кода на сервере может повлиять на производительность. Насколько это правда? утверждение?

Это правда, это влияет на производительность, таким же образом создавая переменные, циклы или выполняя почти все остальное.

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

и следует ли использовать рекурсивный метод в качестве крайней меры?

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

Answer 3

Чтобы обсудить производительность, вы должны поговорить об очень специфических сценариях. Использовано соответственно рекурсия в порядке. Если вы используете ненадлежащим образом , вы можете разбить стек или просто использовать слишком много стека. Это особенно верно, если вы каким-то образом получаете рекурсивный хвостовой вызов без его прерывания (как правило, это ошибка, такая как попытка обхода циклического графа), поскольку она даже не взорвет стек (он просто будет работать вечно, сжимая процессор циклов).

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

Answer 4

Хвост -рекурсия также является альтернативой. Это сводится к следующему: просто передайте возвращенную Result в качестве изменяемой ссылки в качестве параметра метода рекурсии. Таким образом, стек не взорвется. Больше на Википедии и на этом сайте .

Answer 5

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

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

Answer 6

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

Большинство современных компиляторов способны оптимизировать некоторые виды рекурсивных вызовов (заменить их внутренне нерекурсивными эквивалентами). Это особенно легко с tail рекурсией, то есть когда рекурсивный вызов является последней инструкцией перед возвратом результата.

Однако есть некоторые проблемы, специфичные для Java. Базовая JVM не предоставляет никаких инструкций goto. Это устанавливает пределы того, что может делать компилятор. Если это хвостовая рекурсия, внутренняя для одной функции, ее можно заменить простым циклом, внутренним для функции, но если вызов терминала выполняется через другую функцию, или если несколько функций вызывают друг друга рекурсивно, это становится довольно трудно сделать, когда нацеливание на байт-код JVM. SUN JVM не поддерживает оптимизацию хвостового вызова, но есть планы изменить это, IBM JVM поддерживает оптимизацию хвостового вызова.

В некоторых языках (функциональных языках, таких как LISP или Haskell) рекурсия также является единственным (или более естественным) способом написания программ. На функциональных языках на основе JVM, таких как Clojure или Scala, отсутствие оптимизации хвостового вызова является проблемой, которая приводит к обходным путям, таким как trampolines в Scala.

Answer 7

Глубокая рекурсия Может вызвать переполнение стека, что является неприятным. Будьте осторожны, так как вам трудно вставать снова, если вам нужно. Небольшие, управляемые куски работы легче обрабатывать и парализовать.

Answer 8

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