Рекурсия еще быстрее, чем цикличное выполнение?
Я знаю, что рекурсия является иногда намного более чистой, чем цикличное выполнение, и я ничего не спрашиваю о том, когда я должен использовать рекурсию по повторению, я знаю, что уже существует много вопросов об этом.
То, что я спрашиваю, рекурсия еще быстрее, чем цикл? Мне это походит, Вы всегда могли бы совершенствовать цикл и заставить его работать более быстро, чем рекурсивная функция, потому что цикл отсутствует постоянно установка новых стековых фреймов.
Я конкретно ищу, быстрее ли рекурсия в приложениях, где рекурсия является правильным способом обработать данные, такой как в некоторых функциях сортировки, в двоичных деревьях, и т.д.
8 ответов
Это зависит от используемого языка. Вы написали «языково-независимый», поэтому я приведу несколько примеров.
В Java, C и Python рекурсия довольно дорога по сравнению с итерацией (в общем), поскольку требует выделения нового кадра стека. В некоторых компиляторах C для устранения этих накладных расходов можно использовать флаг компилятора, который преобразует определенные типы рекурсии (фактически, определенные типы хвостовых вызовов) в переходы вместо вызовов функций.
В реализациях языка функционального программирования иногда итерация может быть очень дорогой, а рекурсия - очень дешевой. Во многих случаях рекурсия преобразуется в простой переход, но изменение переменной цикла (которая является изменяемой) иногда требует некоторых относительно тяжелых операций, особенно в реализациях, которые поддерживают несколько потоков выполнения. В некоторых из этих сред мутация обходится дорого из-за взаимодействия между мутатором и сборщиком мусора, если оба могут работать одновременно.
Я знаю, что в некоторых реализациях схемы рекурсия обычно выполняется быстрее, чем цикл.
Короче говоря, ответ зависит от кода и реализации. Используйте любой стиль, который вам больше нравится. Если вы используете функциональный язык, рекурсия может быть быстрее. Если вы используете императивный язык, итерация будет на , вероятно, на быстрее. В некоторых средах оба метода приводят к созданию одной и той же сборки (вставьте ее в трубку и выкурите).
Приложение: В некоторых средах лучшей альтернативой является не рекурсия или итерация, а функции более высокого порядка. К ним относятся «карта», «фильтр» и «уменьшение» (также называемое «сворачиванием»). Мало того, что это предпочтительный стиль, они не только часто чище, но и в некоторых средах эти функции являются первыми (или единственными), которые получают импульс от автоматического распараллеливания, поэтому они могут быть значительно быстрее, чем итерация или рекурсия. Data Parallel Haskell является примером такой среды.
Списки - еще одна альтернатива, но обычно это просто синтаксический сахар для функций итерации, рекурсии или функций более высокого порядка.
Обдумайте, что абсолютно необходимо сделать для каждой итерации и рекурсии.
- итерация: переход к началу цикла
- рекурсия: переход к началу вызываемой функции
Вы видите, что здесь мало места для различий.
(я предполагаю, что рекурсия - это хвостовой вызов, и компилятор знает об этой оптимизации).
Теоретически это одно и то же. Рекурсия и цикл с одинаковой сложностью O () будут работать с той же теоретической скоростью, но конечно, реальная скорость зависит от языка, компилятора и процессора. Пример с мощностью числа может быть закодирован итерационным способом с помощью O (ln (n)):
int power(int t, int k) {
int res = 1;
while (k) {
if (k & 1) res *= t;
t *= t;
k >>= 1;
}
return res;
}
Хвостовая рекурсия выполняется так же быстро, как и цикл. Во многих функциональных языках реализована хвостовая рекурсия.
Это предположение. Обычно рекурсия, вероятно, не побеждает цикл часто или когда-либо в задачах приличного размера, если оба используют действительно хорошие алгоритмы (не считая сложности реализации), она может отличаться, если используется с языком с рекурсией хвостовых вызовов (а также хвостовой рекурсивный алгоритм и циклы также как часть языка), которые, вероятно, будут очень похожи и, возможно, даже предпочтут рекурсию в некоторых случаях.
В общем, нет, рекурсия не будет быстрее цикла при любом реалистичном использовании, имеющем жизнеспособные реализации в обеих формах. Я имею в виду, конечно, вы могли бы закодировать циклы, которые длились бы вечно, но были бы лучшие способы реализовать тот же цикл, который мог бы превзойти любую реализацию той же проблемы с помощью рекурсии.
Вы попали в точку относительно причины; создание и уничтожение кадров стека обходится дороже, чем простой переход.
Однако обратите внимание, что я сказал «имеет жизнеспособные реализации в обеих формах». Для таких вещей, как многие алгоритмы сортировки, обычно не существует очень жизнеспособного способа их реализации, который не создает эффективно свою собственную версию стека из-за порождения дочерних «задач», которые являются неотъемлемой частью процесса. Таким образом, рекурсия может быть такой же быстрой, как попытка реализовать алгоритм с помощью цикла.
Изменить: этот ответ предполагает нефункциональные языки, в которых большинство основных типов данных являются изменяемыми. Это не относится к функциональным языкам.
Рекурсия вполне может быть быстрее, если альтернативой является явное управление стеком, как в упомянутых вами алгоритмах сортировки или двоичного дерева.
У меня был случай, когда переписывание рекурсивного алгоритма на Java замедлило его работу.
Таким образом, правильный подход - сначала написать его наиболее естественным образом, оптимизировать только в том случае, если профилирование показывает, что это критично, а затем измерить предполагаемое улучшение.
Нет, в любой реалистичной системе создание кадра стека всегда будет дороже, чем INC и JMP. Вот почему действительно хорошие компиляторы автоматически преобразуют хвостовую рекурсию в вызов того же кадра, то есть без накладных расходов, поэтому вы получаете более читаемую исходную версию и более эффективную скомпилированную версию. действительно, действительно хороший компилятор должен даже уметь преобразовывать обычную рекурсию в хвостовую рекурсию там, где это возможно.