Является ли рекурсия быстрее, чем зацикливание?
Я знаю, что рекурсия иногда намного чище, чем зацикливание, и я ничего не спрашиваю о том, когда мне следует использовать рекурсию поверх итерации, я знаю, что уже есть много вопросов по этому поводу.
Что я спрашиваю, так ли рекурсия всегда быстрее, чем цикл? Мне кажется, вы всегда сможете уточнить цикл и заставить его работать быстрее, чем рекурсивная функция, потому что цикл отсутствует, постоянно настраивая новые кадры стека.
Я специально ищу, быстрее ли рекурсия в приложениях, где рекурсия является правильным способом обработки данных, например, в некоторых функциях сортировки, в двоичных деревьях и т. Д.
13 ответов
Это зависит от используемого языка. Вы написали "независимый от языка", поэтому я приведу несколько примеров.
В Java, C и Python рекурсия довольно дорога по сравнению с итерацией (в целом), потому что она требует выделения нового фрейма стека. В некоторых C-компиляторах можно использовать флаг компилятора, чтобы устранить эти издержки, которые преобразуют определенные типы рекурсии (фактически, определенные типы хвостовых вызовов) в переходы вместо вызовов функций.
В реализациях на языке функционального программирования иногда итерация может быть очень дорогой, а рекурсия - очень дешевой. Во многих случаях рекурсия превращается в простой переход, но изменение переменной цикла (которая является изменяемой) иногда требует некоторых относительно тяжелых операций, особенно в реализациях, которые поддерживают несколько потоков выполнения. В некоторых из этих сред мутация обходится дорого из-за взаимодействия между мутатором и сборщиком мусора, если они оба могут работать одновременно.
Я знаю, что в некоторых реализациях Scheme рекурсия, как правило, будет быстрее, чем зацикливание.
Короче говоря, ответ зависит от кода и реализации. Используйте любой стиль, который вы предпочитаете. Если вы используете функциональный язык, рекурсия может быть быстрее. Если вы используете императивный язык, итерация, вероятно, быстрее. В некоторых средах оба метода приводят к созданию одной и той же сборки (поместите ее в свою трубу и выкурите ее).
Приложение: В некоторых средах лучшая альтернатива - это не рекурсия и не итерация, а функции высшего порядка. К ним относятся "карта", "фильтр" и "уменьшить" (что также называется "сложить"). Они не только являются предпочтительным стилем, они не только часто более чистые, но и в некоторых средах эти функции являются первыми (или единственными), которые получают преимущество от автоматического распараллеливания - поэтому они могут быть значительно быстрее, чем итерация или рекурсия. Data Parallel Haskell является примером такой среды.
Понимание списков является еще одной альтернативой, но обычно это просто синтаксический сахар для функций итерации, рекурсии или функций более высокого порядка.
рекурсия всегда быстрее, чем цикл?
Нет, Итерация всегда будет быстрее, чем Рекурсия. (в архитектуре фон Неймана)
Объяснение:
Если вы строите минимальное количество операций с обычного компьютера с нуля, "Итерация" стоит на первом месте как строительный блок и требует меньше ресурсов, чем "рекурсия", следовательно, это быстрее.
Создание псевдо-вычислительной машины с нуля:
Задайте себе вопрос: что вам нужно для вычисления значения, т.е. чтобы следовать алгоритму и достичь результата?
Мы создадим иерархию концепций, начиная с нуля и определяя в первую очередь базовые, основные концепции, затем создавая концепции второго уровня с ними и так далее.
Первая концепция: ячейки памяти, память, состояние. Чтобы что-то сделать, вам нужны места для хранения конечных и промежуточных значений результатов. Давайте предположим, что у нас есть бесконечный массив "целочисленных" ячеек, называемый Memory, M [0..Infinite].
Инструкции: сделать что-нибудь - трансформировать ячейку, изменить ее значение. изменить состояние. Каждая интересная инструкция выполняет преобразование. Основные инструкции:
а) установить и переместить ячейки памяти
- сохранить значение в памяти, например: сохранить 5 м [4]
- скопируйте значение в другую позицию: например: store m [4] m [8]
б) логика и арифметика
- и, или, XOR, не
- добавить, sub, mul, div. например, добавить m[7] m[8]
Исполнительный агент: ядро в современном процессоре. "Агент" - это то, что может выполнять инструкции. Агент также может быть человеком, следующим алгоритму на бумаге.
Порядок шагов: последовательность инструкций: то есть: сделать это сначала, сделать это после и т. Д. Обязательная последовательность инструкций. Даже однострочные выражения являются "обязательной последовательностью инструкций". Если у вас есть выражение с определенным "порядком оценки", то у вас есть шаги. Это означает, что даже одно составное выражение имеет неявные "шаги", а также имеет неявную локальную переменную (назовем это "результатом"). например:
4 + 3 * 2 - 5 (- (+ (* 3 2) 4 ) 5) (sub (add (mul 3 2) 4 ) 5)Выражение выше подразумевает 3 шага с неявной переменной "result".
// pseudocode 1. result = (mul 3 2) 2. result = (add 4 result) 3. result = (sub result 5)Так что даже инфиксные выражения, поскольку у вас есть определенный порядок вычисления, являются обязательной последовательностью инструкций. Выражение подразумевает последовательность операций, которые должны быть выполнены в определенном порядке, и, поскольку существуют шаги, существует также неявная промежуточная переменная "result".
Указатель инструкций: если у вас есть последовательность шагов, у вас также есть неявный "указатель инструкций". Указатель инструкции отмечает следующую инструкцию и продвигается после чтения инструкции, но до ее выполнения.
В этой псевдо-вычислительной машине указатель инструкций является частью памяти. (Примечание. Обычно указатель инструкций будет "специальным регистром" в ядре ЦП, но здесь мы упростим концепции и предположим, что все данные (включая регистры) являются частью "памяти")
Переход - если у вас есть заказанное количество шагов и указатель инструкций, вы можете применить инструкцию "store", чтобы изменить значение самого указателя инструкций. Мы будем называть это конкретное использование инструкции store новым именем: Jump. Мы используем новое имя, потому что его проще воспринимать как новую концепцию. Изменяя указатель инструкции, мы инструктируем агента "перейти к шагу x".
Бесконечная итерация: отскочив назад, теперь вы можете заставить агента "повторить" определенное количество шагов. На данный момент у нас есть бесконечная итерация.
1. mov 1000 m[30] 2. sub m[30] 1 3. jmp-to 2 // infinite loopУсловно - условное выполнение инструкций. С помощью "условного" предложения вы можете условно выполнить одну из нескольких инструкций в зависимости от текущего состояния (которое можно установить с помощью предыдущей инструкции).
Правильная итерация: теперь с условным предложением мы можем избежать бесконечного цикла инструкции возврата. Теперь у нас есть условный цикл, а затем правильная итерация
1. mov 1000 m[30] 2. sub m[30] 1 3. (if not-zero) jump 2 // jump only if the previous // sub instruction did not result in 0 // this loop will be repeated 1000 times // here we have proper ***iteration***, a conditional loop.Именование: присвоение имен определенной ячейке памяти с данными или с шагом. Это просто "удобство", чтобы иметь. Мы не добавляем никаких новых инструкций, имея возможность определять "имена" для областей памяти. "Наименование" - это не инструкция для агента, а просто удобство для нас. Присвоение имен делает код (на данный момент) более простым для чтения и изменения.
#define counter m[30] // name a memory location mov 1000 counter loop: // name a instruction pointer location sub counter 1 (if not-zero) jmp-to loopОдноуровневая подпрограмма. Предположим, вам нужно выполнить серию шагов. Вы можете сохранить шаги в именованной позиции в памяти, а затем перейти к этой позиции, когда вам нужно выполнить их (вызвать). В конце последовательности вам нужно вернуться к точке вызова, чтобы продолжить выполнение. С помощью этого механизма вы создаете новые инструкции (подпрограммы), составляя основные инструкции.
Реализация: (новые концепции не требуются)
- Сохранить текущий указатель инструкций в предварительно определенной позиции памяти
- перейти к подпрограмме
- в конце подпрограммы вы извлекаете указатель инструкций из предопределенной области памяти, фактически возвращаясь к следующей инструкции исходного вызова
Проблема с одноуровневой реализацией: Вы не можете вызвать другую подпрограмму из подпрограммы. Если вы это сделаете, вы перезапишете возвращающий адрес (глобальную переменную), поэтому вы не сможете вкладывать вызовы.
Чтобы иметь лучшую реализацию для подпрограмм: вам нужен STACK
Стек: Вы определяете пространство памяти для работы в качестве "стека", вы можете "выталкивать" значения в стек, а также "выталкивать" последнее "вытолкнутое" значение. Для реализации стека вам понадобится указатель стека (аналогично указателю инструкций), который указывает на фактическую "верхушку" стека. Когда вы "нажимаете" значение, указатель стека уменьшается, и вы сохраняете значение. Когда вы "выталкиваете", вы получаете значение в фактическом указателе стека, а затем увеличивается указатель стека.
Подпрограммы Теперь, когда у нас есть стек, мы можем реализовать надлежащие подпрограммы, допускающие вложенные вызовы. Реализация аналогична, но вместо того, чтобы хранить указатель инструкций в предопределенной позиции памяти, мы "помещаем" значение IP в стек. В конце подпрограммы мы просто "выталкиваем" значение из стека, фактически возвращаясь к инструкции после исходного вызова. Эта реализация, имеющая "стек", позволяет вызывать подпрограмму из другой подпрограммы. С помощью этой реализации мы можем создать несколько уровней абстракции при определении новых инструкций в качестве подпрограмм, используя базовые инструкции или другие подпрограммы в качестве строительных блоков.
Рекурсия: что происходит, когда подпрограмма вызывает себя? Это называется "рекурсия".
Проблема: Перезаписывая локальные промежуточные результаты, подпрограмма может быть сохранена в памяти. Поскольку вы вызываете / повторно используете одни и те же шаги, если промежуточный результат хранится в предопределенных ячейках памяти (глобальных переменных), они будут перезаписаны при вложенных вызовах.
Решение. Чтобы разрешить рекурсию, подпрограммы должны хранить локальные промежуточные результаты в стеке, поэтому при каждом рекурсивном вызове (прямом или косвенном) промежуточные результаты хранятся в разных местах памяти.
...
дойдя до рекурсии, мы останавливаемся здесь.
Заключение:
В архитектуре фон Неймана ясно, что "Итерация" является более простым / базовым понятием, чем "Рекурсия". У нас есть форма "Итерации" на уровне 7, в то время как "Рекурсия" находится на уровне 14 иерархии понятий.
Итерация всегда будет быстрее в машинном коде, потому что она подразумевает меньше инструкций и, следовательно, меньше циклов ЦП.
Какой из них лучше"?
Вам следует использовать "итерацию", когда вы обрабатываете простые, последовательные структуры данных, и везде будет работать "простой цикл".
Вы должны использовать "рекурсию", когда вам нужно обработать рекурсивную структуру данных (мне нравится называть их "фрактальными структурами данных"), или когда рекурсивное решение явно более "элегантно".
Совет: используйте лучший инструмент для работы, но понимайте внутреннюю работу каждого инструмента, чтобы выбирать мудро.
Наконец, обратите внимание, что у вас есть много возможностей использовать рекурсию. Повсюду у вас есть рекурсивные структуры данных, сейчас вы смотрите на одну: части DOM, поддерживающие то, что вы читаете, - это RDS, выражение JSON - это RDS, иерархическая файловая система на вашем компьютере - это RDS, т.е. корневой каталог, содержащий файлы и каталоги, каждый каталог, содержащий файлы и каталоги, каждый из этих каталогов, содержащий файлы и каталоги...
Рекурсия может быть быстрее, если альтернативой является явное управление стеком, как в алгоритмах сортировки или двоичного дерева, о которых вы упомянули.
У меня был случай, когда переписывание рекурсивного алгоритма в Java сделало его медленнее.
Таким образом, правильный подход заключается в том, чтобы сначала написать его наиболее естественным образом, оптимизировать только в том случае, если профилирование показывает его критичность, а затем измерить предполагаемое улучшение.
Большинство ответов здесь неверны. Правильный ответ - это зависит. Например, вот две функции C, которые проходят по дереву. Сначала рекурсивный:
static
void mm_scan_black(mm_rc *m, ptr p) {
SET_COL(p, COL_BLACK);
P_FOR_EACH_CHILD(p, {
INC_RC(p_child);
if (GET_COL(p_child) != COL_BLACK) {
mm_scan_black(m, p_child);
}
});
}
А вот та же функция, реализованная с использованием итерации:
static
void mm_scan_black(mm_rc *m, ptr p) {
stack *st = m->black_stack;
SET_COL(p, COL_BLACK);
st_push(st, p);
while (st->used != 0) {
p = st_pop(st);
P_FOR_EACH_CHILD(p, {
INC_RC(p_child);
if (GET_COL(p_child) != COL_BLACK) {
SET_COL(p_child, COL_BLACK);
st_push(st, p_child);
}
});
}
}
Не важно понимать детали кода. Только то p узлы и P_FOR_EACH_CHILD делает ходьбу. В итерационной версии нам нужен явный стек st на какие узлы проталкиваются, а затем выталкиваются и манипулируют.
Рекурсивная функция выполняется намного быстрее, чем итеративная. Причина в том, что в последнем случае для каждого элемента CALL к функции st_push нужен, а потом еще st_pop,
В первом случае у вас есть только рекурсивный CALL для каждого узла.
Кроме того, доступ к переменным в стеке вызовов невероятно быстр. Это означает, что вы читаете из памяти, которая, вероятно, всегда будет в самом внутреннем кэше. С другой стороны, явный стек должен поддерживаться malloc: ed память из кучи, доступ к которой намного медленнее.
С осторожной оптимизацией, такой как встраивание st_push а также st_popЯ могу достичь примерно паритета с рекурсивным подходом. Но по крайней мере на моем компьютере стоимость доступа к куче памяти больше, чем стоимость рекурсивного вызова.
Но это обсуждение в основном спорный вопрос, потому что рекурсивное дерево ходьба является неправильной. Если у вас достаточно большое дерево, вам не хватит места для стека вызовов, поэтому необходимо использовать итерационный алгоритм.
Хвостовая рекурсия выполняется так же быстро, как и петля. Во многих функциональных языках реализована хвостовая рекурсия.
Большинство ответов здесь забывают очевидного виновника, почему рекурсия часто медленнее, чем итерационные решения. Это связано со сборкой и разборкой стековых фреймов, но не совсем так. Как правило, это большая разница в хранении автоматической переменной для каждой рекурсии. В итеративном алгоритме с циклом переменные часто хранятся в регистрах, и даже если они разливаются, они будут находиться в кэше уровня 1. В рекурсивном алгоритме все промежуточные состояния переменной хранятся в стеке, что означает, что они вызовут еще много разливов в память. Это означает, что даже если он выполняет одинаковое количество операций, у него будет много обращений к памяти в горячем цикле, и, что еще хуже, эти операции с памятью имеют паршивую частоту повторного использования, что делает кэши менее эффективными.
TL; DR рекурсивные алгоритмы обычно хуже кешируют, чем итеративные.
Рассмотрим, что абсолютно необходимо сделать для каждой итерации и рекурсии.
- итерация: переход к началу цикла
- рекурсия: переход к началу вызываемой функции
Вы видите, что здесь не так много места для разногласий.
(Я предполагаю, что рекурсия - это хвостовой вызов, а компилятор знает об этой оптимизации).
В общем, нет, рекурсия не будет быстрее цикла при любом реалистичном использовании, которое имеет жизнеспособные реализации в обеих формах. Я имею в виду, конечно, вы могли бы кодировать циклы, которые занимают вечность, но были бы лучшие способы реализовать тот же цикл, который мог бы превзойти любую реализацию той же проблемы посредством рекурсии.
Вы ударили гвоздь по голове относительно причины; Создание и уничтожение стековых фреймов обходится дороже, чем простой переход.
Однако обратите внимание, что я сказал, что "имеет жизнеспособные реализации в обеих формах". Для таких вещей, как многие алгоритмы сортировки, существует не очень жизнеспособный способ их реализации, который эффективно не устанавливает свою собственную версию стека, из-за порождения дочерних "задач", которые являются неотъемлемой частью процесса. Таким образом, рекурсия может быть такой же быстрой, как и попытка реализовать алгоритм с помощью цикла.
Изменить: Этот ответ предполагает, что нефункциональные языки, где большинство основных типов данных являются изменяемыми. Это не относится к функциональным языкам.
В любой реалистичной системе создание фрейма стека всегда будет обходиться дороже, чем INC и JMP. Вот почему действительно хорошие компиляторы автоматически преобразуют хвостовую рекурсию в вызов одного и того же фрейма, то есть без дополнительных затрат, так что вы получаете более читаемую исходную версию и более эффективную скомпилированную версию. A really, really good compiler should even be able to transform normal recursion into tail recursion where that is possible.
Функциональное программирование - это скорее "что", а не "как".
Разработчики языка найдут способ оптимизировать работу кода под ним, если мы не попытаемся сделать его более оптимизированным, чем нужно. Рекурсию также можно оптимизировать на языках, которые поддерживают оптимизацию хвостовых вызовов.
Что важнее с точки зрения программиста, так это удобочитаемость и удобство обслуживания, а не оптимизация. Опять же, "преждевременная оптимизация - корень всего зла".
Вот пример, когда рекурсия работала быстрее, чем цикл в Java. Это программа, которая выполняет сортировку пузырьком на двух массивах. recBubbleSort(....)метод сортирует массивarrиспользуя рекурсию иbbSort(....)метод просто использует цикл для сортировки массиваnarr. Данные одинаковы в обоих массивах.
public class BBSort_App {
public static void main(String args[]) {
int[] arr = {231,414235,23,543,245,6,324,-32552,-4};
long time = System.nanoTime();
recBubbleSort(arr, arr.length-1, 0);
time = System.nanoTime() - time;
System.out.println("Time Elapsed: "+time+"nanos");
disp(arr);
int[] narr = {231,414235,23,543,245,6,324,-32552,-4};
time = System.nanoTime();
bbSort(narr);
time = System.nanoTime()-time;
System.out.println("Time Elapsed: "+time+"nanos");
disp(narr);
}
static void disp(int[] origin) {
System.out.print("[");
for(int b: origin)
System.out.print(b+", ");
System.out.println("\b\b \b]");
}
static void recBubbleSort(int[] origin, int i, int j) {
if(i>0)
if(j!=i) {
if(origin[i]<origin[j]) {
int temp = origin[i];
origin[i] = origin[j];
origin[j] = temp;
}
recBubbleSort(origin, i, j+1);
}
else
recBubbleSort(origin, i-1, 0);
}
static void bbSort(int[] origin) {
for(int out=origin.length-1;out>0;out--)
for(int in=0;in<out;in++)
if(origin[out]<origin[in]) {
int temp = origin[out];
origin[out] = origin[in];
origin[in] = temp;
}
}
}
Запуск теста даже 50 раз дал почти одинаковые результаты:
Ответы на этот вопрос удовлетворительны, но без простых примеров. Может ли кто-нибудь просто объяснить, почему эта рекурсия работает быстрее?
Согласно теории это то же самое. Рекурсия и цикл с одинаковой сложностью 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;
}
Это предположение. Обычно рекурсия, вероятно, не справляется с цикличностью часто или когда-либо при проблемах приличного размера, если оба используют действительно хорошие алгоритмы (не считая сложности реализации), она может отличаться, если используется с рекурсией языка с хвостовой рекурсией (и хвостовым рекурсивным алгоритмом) и с циклами также как часть языка)- которые, вероятно, будут очень похожи и, возможно, даже предпочтут рекурсию иногда.