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

Возможный дубликат:
Является ли рекурсия быстрее, чем цикл?

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

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

Ответ 1

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

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

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

Ответ 2

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

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

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

Ответ 3

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

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

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

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

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

Ответ 4

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

Ответ 5

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

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

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

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