Накладные расходы на рекурсию - насколько это серьезно?

Question

Можно создать дубликат:
Is recursion ever faster than looping?

Я был первым обучен программы серьезно C, около 15 лет назад. Мой работодатель хотел получить очень оптимизированный код для сложных вычислительных задач. Я помню, что мне не раз советовали переписывать рекурсии как циклы, даже при дорогостоящей читабельности, чтобы избежать «накладных расходов на рекурсию». Как я понял, тогда накладные расходы рекурсии были дополнительным усилием, необходимым для того, чтобы выталкивать данные в стек, а затем выталкивать их.

Теперь я код на C, Python, Perl, а иногда и на Java, и иногда мне интересно узнать о рекурсиях. Есть ли еще что-то, что можно получить, переписав их? Что, если это хвостовые рекурсии? Неужели современные компиляторы задали все эти проблемы? Являются ли такие проблемы неуместными для интерпретируемых языков?

Answer 1

Рекурсия может привести к значительным накладным расходам, если ядро ​​рекурсивной функции меньше вычислительно дорого, чем код ввода/выхода функции, а также стоимость самого вызова. Лучший способ выяснить - просто профилировать две версии кода - один рекурсивный, а другой нет.

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

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

Answer 2

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

Однако еще одна вещь, которую вы должны учесть, это то, что компьютеры стали порядками величин быстрее, чем они были 15 лет назад, поэтому сейчас гораздо реже, прежде чем вам нужно беспокоиться о микро-оптимизации. Программа, которая 15 лет назад, возможно, потребовала тщательной оптимизации рук на ассемблере, чтобы получить достойную производительность, может быстро развиваться на современном компьютере, даже если она написана на языке более высокого уровня, таком как Java. Это не означает, что производительность больше не проблема, но вы должны сосредоточиться на правильном алгоритме и при написании читаемого кода. Сделайте только микро-оптимизацию после того, как вы измерили производительность, и вы увидите, что этот код является узким местом.

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

Answer 3

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

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

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

def sum1through (n): 
    if n == 0 return 0 
    return n + sum1through (n-1) 

так делать, что для n двадцати миллионов не будет здоровым для стека.

Answer 4

Проблема все еще существует. Рекурсия занимает много места в стеке, так как каждый раз, когда метод вызывает себя, указатель на него и его локальные переменные генерируются снова. Количество вызовов функций, выполняемых во время рекурсии, делает использование памяти O (n); по сравнению с O (1) нерекурсивной функции, такой как петли.

Answer 5

Люди говорят много глупостей о производительности.

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

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

На мой взгляд, лучший способ найти проблемы производительности является стек выборки по времени на стене часы и examining the samples to see what the program is doing, а не просто получать измерения и интересно, что они означают.

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