является ли рекурсия быстрее, чем зацикливание?

<p>я знаю, что рекурсия иногда намного чище, чем зацикливание, и я ничего не спрашиваю о том, когда мне следует использовать рекурсию поверх итерации, я знаю, что уже есть много вопросов по этому поводу.</p><p>я спрашиваю, является ли рекурсия <strong>когда-либо</strong> быстрее, чем цикл? мне кажется, вы всегда сможете уточнить цикл и заставить его работать быстрее, чем рекурсивная функция, потому что цикл отсутствует, постоянно настраивая новые кадры стека.</p><p>я специально ищу, быстрее ли рекурсия в приложениях, где рекурсия является правильным способом обработки данных, например, в некоторых функциях сортировки, в двоичных деревьях и т.д.</p>

<p>это зависит от используемого языка. вы написали "независимый от языка", поэтому я приведу несколько примеров.</p><p>в java, c и python рекурсия довольно дорога по сравнению с итерацией (в целом), поскольку требует выделения нового фрейма стека. в некоторых c-компиляторах можно использовать флаг компилятора, чтобы устранить эти издержки, которые преобразуют определенные типы рекурсии (фактически, определенные типы хвостовых вызовов) в переходы вместо вызовов функций.</p><p>в реализациях на языке функционального программирования иногда итерация может быть очень дорогой, а рекурсия - очень дешевой. во многих случаях рекурсия превращается в простой переход, но для изменения переменной цикла (которая является изменяемой) <em> иногда </em> требуются некоторые относительно тяжелые операции, особенно в реализациях, которые поддержка нескольких потоков исполнения. мутация стоит дорого в некоторых из этих сред из-за взаимодействия между мутатором и сборщиком мусора, если они оба могут работать одновременно.</p><p>я знаю, что в некоторых реализациях scheme рекурсия обычно выполняется быстрее, чем зацикливание.</p><p>короче говоря, ответ зависит от кода и реализации. используйте любой стиль, который вы предпочитаете. если вы используете функциональный язык, рекурсия <em> может </em> быть быстрее. если вы используете императивный язык, итерация <em>, вероятно </em> быстрее. в некоторых средах оба метода приводят к созданию одной и той же сборки (поместите ее в свою трубу и выкурите ее).</p><p><strong>addendum:</strong> в некоторых средах лучшей альтернативой является не рекурсия и не итерация, а функции высшего порядка. к ним относятся "карта", "фильтр" и "уменьшить" (что также называется "сложить"). они не только являются предпочтительным стилем, они не только часто более чистые, но и в некоторых средах эти функции являются первыми (или единственными), которые получают преимущество от автоматического распараллеливания - поэтому они могут быть значительно быстрее, чем итерация или рекурсия. data parallel haskell является примером такой среды.</p><p>понимание списков - это еще одна альтернатива, но обычно это просто синтаксический сахар для функций итерации, рекурсии или функций более высокого порядка.</p>

<blockquote> <p>рекурсия когда-либо быстрее, чем цикл?</p> </blockquote><p><strong><em> нет, </em></strong> итерация всегда будет быстрее, чем рекурсия. (в архитектуре фон неймана)</p><h3>объяснение:</h3><p>если вы строите минимальное количество операций с обычного компьютера с нуля, "итерация" стоит на первом месте как строительный блок и требует меньше ресурсов, чем "рекурсия", следовательно, это быстрее.</p><h3>создание псевдо-вычислительной машины с нуля:</h3><p><strong>задайте себе вопрос</strong>: что вам нужно <strong><em> вычислить </em></strong> значение, т.е. следовать алгоритму и достичь результата?</p><p>мы создадим иерархию концепций, начиная с нуля и определяя в первую очередь базовые, основные концепции, затем создавая концепции второго уровня с ними и так далее.</p><ol> <li> <p>первая концепция: <strong>ячейки памяти, память, состояние</strong>. чтобы сделать что-то, вам нужно <em> мест </em> для хранения окончательных и промежуточных значений результатов. давайте предположим, что у нас есть бесконечный массив "целочисленных" ячеек, называемых <strong>memory</strong>, m [0..infinite].</p> </li> <li> <p><strong>инструкция:</strong> сделать что-то - преобразовать ячейку, изменить ее значение. <strong>изменить состояние</strong>. каждая интересная инструкция выполняет преобразование. основные инструкции:</p> <p>а) <strong>установить и переместить ячейки памяти</strong></p> <ul> <li>сохранить значение в памяти, например: <strong><em> сохранить 5 м [4] </em></strong></li> <li>скопируйте значение в другую позицию: например: <strong><em> store m [4] m [8] </em></strong></li> </ul> <p>б) <strong>логика и арифметика</strong></p> <ul> <li>и, или, xor, не</li> <li>добавить, sub, mul, div. например <strong><em> добавить m [7] m [8] </em></strong></li> </ul> </li> <li> <p><strong>исполнительный агент</strong>: <em> ядро </em> в современном процессоре. "агент" - это то, что может выполнять инструкции. <em> агент </em> также может быть человеком, следующим алгоритму на бумаге.</p> </li> <li> <p><strong>порядок шагов: последовательность инструкций</strong>: т.е. делать это сначала, делать это после и т.д. обязательная последовательность инструкций. даже одна строка <em> выражений </em> является "обязательной последовательностью инструкций". если у вас есть выражение с определенным "порядком оценки", то у вас есть <strong><em> steps </em></strong>. это означает, что даже одно составное выражение имеет неявные "шаги", а также имеет неявную локальную переменную (назовем это "результатом"). например.:</p> <pre><code>4 + 3 * 2 - 5 (- (+ (* 3 2) 4 ) 5) (sub (add (mul 3 2) 4 ) 5) </code></pre> <p>выражение выше подразумевает 3 шага с неявной переменной "result".</p> <pre><code>// pseudocode 1. result = (mul 3 2) 2. result = (add 4 result) 3. result = (sub result 5) </code></pre> <p>так что даже инфиксные выражения, поскольку у вас есть определенный порядок вычисления, являются <em> обязательной последовательностью инструкций </em>. выражение <em> подразумевает </em> последовательность операций, которые должны быть выполнены в определенном порядке, и потому что есть <em> шаги </em>, существует также неявная промежуточная переменная "result".</p> </li> <li> <p><strong>указатель инструкций</strong>: если у вас есть последовательность шагов, у вас также есть неявный "указатель инструкций". указатель инструкции отмечает следующую инструкцию и продвигается после чтения инструкции, но до ее выполнения.</p> <p>в этой псевдо-вычислительной машине указатель инструкций является частью <em> памяти </em>. (примечание: обычно <strong>указатель инструкций</strong> будет "специальным регистром" в ядре цп, но здесь мы упростим концепции и предположим, что все данные (включая регистры) являются частью "памяти")</p> </li> <li> <p><strong>прыжок</strong> - если у вас есть заказанное количество шагов и указатель инструкций <em> </em>, вы можете применить "<strong>store</strong> "инструкция для изменения значения самого указателя инструкции. мы назовем это конкретное использование <em> инструкции магазина </em> с новым именем: <strong>jump</strong>. мы используем новое имя, потому что его проще воспринимать как новую концепцию. изменяя указатель инструкции, мы инструктируем агента "перейти к шагу x".</p> </li> <li> <p><strong>бесконечная итерация</strong>: путем <strong><em> прыжка назад, </em></strong> теперь вы можете заставить агента "повторять" определенное количество шагов. на данный момент мы имеем <strong>бесконечная итерация.</strong></p> <pre><code> 1. mov 1000 m[30] 2. sub m[30] 1 3. jmp-to 2 // infinite loop </code></pre></li> <li> <p><strong>условно</strong> - условное выполнение инструкций. с помощью "условного" предложения вы можете условно выполнить одну из нескольких инструкций в зависимости от текущего состояния (которое можно установить с помощью предыдущей инструкции).</p> </li> <li> <p><strong>правильная итерация</strong>: теперь с помощью условия <strong>условное</strong> мы можем избежать бесконечного цикла инструкции <strong>перейти назад</strong>. теперь у нас есть <strong>условный цикл</strong> и затем <strong>правильная итерация</strong></p> <pre><code>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. </code></pre></li> <li> <p><strong>naming</strong>: присвоение имен определенной ячейке памяти, содержащей данные или удержание <em> шага </em>. это просто "удобство", чтобы иметь. мы не добавляем никаких новых инструкций, имея возможность определять "имена" для областей памяти. "наименование" - это не инструкция для агента, а просто удобство для нас. <em> именование </em> делает код (на данный момент) более легким для чтения и изменения.</p> <pre><code> #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 </code></pre></li> <li> <p><strong>одноуровневая подпрограмма</strong>: предположим, вам нужно выполнить ряд шагов часто. вы можете сохранить шаги в именованной позиции в памяти, а затем <em> перейти к </em> этой позиции, когда вам нужно выполнить их (вызвать). в конце последовательности вам нужно <em> вернуть </em> в точку <em> вызова </em> продолжить исполнение. с помощью этого механизма вы <em> создаете новые инструкции </em> (подпрограммы), составляя основные инструкции.</p> <p><strong>реализация: (новые концепции не требуются)</strong></p> <ul> <li>сохранить текущий указатель инструкций в предварительно определенной позиции памяти</li> <li><strong>переход</strong> к подпрограмме</li> <li>в конце подпрограммы вы извлекаете указатель инструкций из предопределенной области памяти, фактически возвращаясь к следующей инструкции исходного вызова <em> </em></li> </ul> <p>проблема с реализацией <strong>одноуровневая</strong>: вы не можете вызвать другую подпрограмму из подпрограммы. если вы это сделаете, вы перезапишете возвращающий адрес (глобальную переменную), поэтому вы не сможете вкладывать вызовы.</p> <p>чтобы иметь <strong>лучшая реализация для подпрограмм: вам нужен stack</strong></p> </li> <li> <p><strong>stack</strong>: вы определяете пространство памяти для работы в качестве "стека", вы можете "вытолкнуть" значения в стек, а также "вытолкнуть" последнее "выдвинутое" значение. для реализации стека вам понадобится <strong><em> указатель стека </em></strong> (аналогично указателю инструкции), который указывает на фактическую "голову" стека. когда вы "нажимаете" значение, указатель стека уменьшается, и вы сохраняете значение. когда вы "выталкиваете", вы получаете значение в фактическом указателе стека, а затем увеличивается указатель стека.</p> </li> <li> <p><strong>подпрограммы</strong> теперь, когда у нас есть стек <strong><em> </em></strong>, мы можем реализовать правильные подпрограммы <em> разрешать вложенные вызовы </em>. реализация аналогична, но вместо того, чтобы хранить указатель инструкций в предопределенной позиции памяти, мы "проталкиваем" значение ip в стеке <em> </em>. в конце подпрограммы мы просто "выталкиваем" значение из стека, фактически возвращаясь к инструкции после исходного вызова <em> </em>. эта реализация, имеющая "стек", позволяет вызывать подпрограмму из другой подпрограммы. с помощью этой реализации мы можем создать несколько уровней абстракции при определении <em> новых инструкций </em> в качестве подпрограмм, используя базовые инструкции или другие подпрограммы в качестве строительных блоков.</p> </li> <li> <p><strong>рекурсия</strong>: что происходит, когда подпрограмма вызывает себя? это называется "рекурсия".</p> <p><em> проблема: </em> перезапись локальных промежуточных результатов, которые подпрограмма может сохранить в памяти. поскольку вы вызываете/повторно используете одни и те же шаги, <strong><em> if </em></strong> промежуточный результат хранится в предопределенных ячейках памяти (глобальных переменных), поэтому они будут перезаписаны на вложенные вызовы.</p> <p><em> решение: </em> чтобы разрешить рекурсию, подпрограммы должны хранить локальные промежуточные результаты <strong><em> в стеке </em></strong>, поэтому при каждом <em> рекурсивном вызове </em> (прямом или косвенном) промежуточные результаты сохраняются в разных местах памяти.</p> </li> </ol><p>...</p><p>достигнув <strong><em> рекурсии </em></strong> мы остановимся здесь.</p><h2>заключение:</h2><p>в архитектуре фон неймана ясно, что <strong><em> "итерация" </em></strong> является более простой/основной концепцией, чем <strong><em> "рекурсия" </em></strong>. у нас есть форма <strong>"итерация"</strong> на уровне 7, а <strong>"рекурсия"</strong> = находится на 14 уровне иерархии понятий.</p><p><strong><em> итерация </em></strong> всегда будет быстрее в машинном коде, поскольку она подразумевает меньше инструкций и, следовательно, меньше циклов цп.</p><h3>какой из них лучше"?</h3><ul> <li> <p>вам следует использовать "итерацию", когда вы обрабатываете простые, последовательные структуры данных, и везде будет работать "простой цикл".</p> </li> <li> <p>вы должны использовать "рекурсию", когда вам нужно обработать рекурсивную структуру данных (мне нравится называть их "фрактальными структурами данных"), или когда рекурсивное решение явно более "элегантно".</p> </li> </ul><p><strong>совет</strong>: используйте лучший инструмент для работы, но понимайте внутреннюю работу каждого инструмента, чтобы выбирать мудро.</p><p>наконец, обратите внимание, что у вас есть много возможностей использовать рекурсию. у вас есть <em> рекурсивные структуры данных </em> везде, сейчас вы смотрите на одну: части dom, поддерживающие то, что вы читаете, - это rds, выражение json: rds, иерархическая файловая система на вашем компьютере - это rds, то есть: у вас есть корневой каталог, содержащий файлы и каталоги, каждый каталог, содержащий файлы и каталоги, каждый из этих каталогов, содержащий файлы и каталоги ...</p>

<p>рекурсия может быть быстрее, если альтернативой является явное управление стеком, как в алгоритмах сортировки или двоичного дерева, о которых вы упомянули.</p><p>у меня был случай, когда переписывание рекурсивного алгоритма в java сделало его медленнее.</p><p>таким образом, правильный подход заключается в том, чтобы сначала написать его наиболее естественным образом, оптимизировать только в том случае, если профилирование показывает его критичность, а затем измерить предполагаемое улучшение.</p>

<p> <a href="https://stackoverflow.com/questions/33923/what-is-tail-recursion">рекурсия хвоста</a> выполняется так же быстро, как и цикл. во многих функциональных языках реализована хвостовая рекурсия.</p>

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

<p>большинство ответов здесь забывают очевидного виновника, почему рекурсия часто медленнее, чем итеративные решения. это связано со сборкой и разборкой стековых фреймов, но это не совсем так. как правило, это большая разница в хранении автоматической переменной для каждой рекурсии. в итеративном алгоритме с циклом переменные часто хранятся в регистрах, и даже если они разливаются, они будут находиться в кэше уровня 1. в рекурсивном алгоритме все промежуточные состояния переменной хранятся в стеке, что означает, что они вызовут еще много разливов в память. это означает, что даже если он выполняет одинаковое количество операций, у него будет много обращений к памяти в горячем цикле, и, что еще хуже, эти операции с памятью имеют паршивую частоту повторного использования, что делает кэши менее эффективными.</p><p>tl; dr рекурсивные алгоритмы, как правило, хуже кешируют, чем итеративные.</p>

<p>большинство ответов здесь <strong>неправильно</strong>. правильный ответ <strong>это зависит</strong>. например, вот две функции c, которые проходят по дереву. сначала рекурсивный:</p><pre><code>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); } }); } </code></pre><p>а вот та же функция, реализованная с использованием итерации:</p><pre><code>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); } }); } } </code></pre><p>не важно понимать детали кода. просто <code>p</code> являются узлами, а <code>p\_for\_each\_child</code> выполняет прогулку. в итерационной версии нам нужен явный стек <code>st</code>, в который узлы помещаются, а затем извлекаются и обрабатываются.</p><p>рекурсивная функция выполняется намного быстрее, чем итеративная. причина в том, что в последнем случае для каждого элемента требуется <code>call</code> для функции <code>st\_push</code>, а затем еще один для <code>st\_pop</code>.</p><p>в первом случае у вас есть только рекурсивное <code>call</code> для каждого узла.</p><p>кроме того, доступ к переменным в стеке вызовов невероятно быстр. это означает, что вы читаете из памяти, которая, вероятно, всегда будет в самом внутреннем кэше. с другой стороны, явный стек должен поддерживаться <code>malloc</code>: ed памятью из кучи, доступ к которой намного медленнее.</p><p>благодаря тщательной оптимизации, такой как встраивание <code>st\_push</code> и <code>st\_pop</code>, я могу достичь примерно паритета с рекурсивным подходом. но по крайней мере на моем компьютере стоимость доступа к куче памяти больше, чем стоимость рекурсивного вызова.</p><p>но это обсуждение в основном спорный вопрос, потому что рекурсивное дерево ходьба <strong>неверный</strong>. если у вас достаточно большое дерево, вам не хватит места для стека вызовов, поэтому необходимо использовать итерационный алгоритм.</p>

<p>в любой реалистичной системе создание фрейма стека всегда будет обходиться дороже, чем inc и jmp. вот почему действительно хорошие компиляторы автоматически преобразуют хвостовую рекурсию в вызов одного и того же фрейма, то есть без дополнительных затрат, поэтому вы получаете более читаемую исходную версию и более эффективную скомпилированную версию. <em>действительно, действительно</em> хороший компилятор должен даже иметь возможность преобразовывать обычную рекурсию в хвостовую рекурсию, где это возможно.</p>

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

<p>в общем, нет, рекурсия не будет быстрее цикла при любом реалистичном использовании, которое имеет жизнеспособные реализации в обеих формах. я имею в виду, конечно, вы могли бы кодировать циклы, которые занимают вечность, но были бы лучшие способы реализовать тот же цикл, который мог бы превзойти любую реализацию той же проблемы с помощью рекурсии.</p><p>вы ударили гвоздь по голове относительно причины; создание и уничтожение стековых фреймов обходится дороже, чем простой переход.</p><p>тем не менее, обратите внимание, что я сказал "имеет жизнеспособные реализации в обеих формах". для таких вещей, как многие алгоритмы сортировки, существует не очень жизнеспособный способ их реализации, который эффективно не устанавливает свою собственную версию стека, из-за порождения дочерних "задач", которые являются неотъемлемой частью процесса. таким образом, рекурсия может быть такой же быстрой, как и попытка реализовать алгоритм с помощью цикла.</p><h3>правка: этот ответ предполагает, что нефункциональные языки, где большинство основных типов данных являются изменяемыми. это не относится к функциональным языкам.</h3>

<p>это предположение. обычно рекурсия, вероятно, не справляется с цикличностью часто или когда-либо при проблемах приличного размера, если оба используют действительно хорошие алгоритмы (не считая сложности реализации), она может отличаться, если используется с языком w/ <a href="http://en.wikipedia.org/wiki/tail\_recursion">рекурсия хвостового вызова</a> = (и хвостовой рекурсивный алгоритм и с циклами также как часть языка) - который, вероятно, будет очень похож и, возможно, даже предпочтет рекурсию иногда.</p>

<p>согласно теории это то же самое. рекурсия и цикл с одинаковой сложностью o() будут работать с той же теоретической скоростью, но, конечно, реальная скорость зависит от языка, компилятора и процессора. пример со степенью числа может быть итеративно закодирован с помощью o (ln (n)):</p><pre><code> int power(int t, int k) { int res = 1; while (k) { if (k & 1) res *= t; t *= t; k >>= 1; } return res; } </code></pre>