Является ли рекурсия когда-либо быстрее, чем цикл?

рекурсия когда-либо быстрее, чем цикл?

нет, итерация всегда будет быстрее рекурсии. (в архитектуре фон Неймана)

объяснение:

если вы создаете минимальные операции универсального компьютера с нуля," итерация "сначала является строительным блоком и менее ресурсоемким, чем" рекурсия", ergo быстрее.

построение псевдо-вычислительной машины с скретч:

вопрос: что вам нужно вычислить значение, т. е. следовать алгоритму и достичь результата?

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

1. Первая Концепция: ячейки памяти, хранение, состояние. Чтобы сделать что-то вы нужно мест для хранения конечных и промежуточных результирующих значений. Предположим, что у нас есть бесконечный массив "целочисленных" ячеек, называемых , M[0..Бесконечный.]

2. инструкции: сделайте что-нибудь-преобразуйте ячейку, измените ее значение. изменить состояние. Каждая интересная инструкция выполняет преобразование. Основные инструкции:

   a) установить и переместить ячейки памяти

   • сохранить значение в памяти, например: магазин 5 м[4]
   • скопируйте значение в другую позицию: например:магазин m[4] m[8]

   б) логика и арифметика

   • и, или, исключающее ИЛИ, НЕ
   • добавить, sub, mul, div. например,добавить m[7] m[8]

3. An Агент-Исполнитель: a базовый в современном процессоре. "Агент" - это то, что может выполнять команды. Ан агент также может быть человек, следуя алгоритму на бумаге.

4. порядок шагов: последовательность инструкций: т. е.: сделайте это сначала, сделайте это после и т. д. Императивная последовательность инструкций. Даже одна строчка выражения являются "императивной последовательностью инструкций". Если у вас есть выражение с определенным "порядком оценки" тогда у вас есть шаги. Это означает, что даже одно составленное выражение имеет неявные "шаги", а также имеет неявную локальную переменную (назовем ее"результатом"). например:

   4 + 3 * 2 - 5
   (- (+ (* 3 2) 4 ) 5)
   (sub (add (mul 3 2) 4 ) 5)  
   

   приведенное выше выражение подразумевает 3 шага с неявной переменной "результат".

   // pseudocode
   
          1. result = (mul 3 2)
          2. result = (add 4 result)
          3. result = (sub result 5)
   

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

5. Инструкция Указатель: если у вас есть последовательность шагов, у вас также есть неявный "указатель инструкции". Указатель инструкции отмечает следующую инструкцию и продвигается вперед после чтения инструкции, но до выполнения инструкции.

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

6. прыжок - после того, как у вас есть заказанное количество шагов и Инструкция Указатель можно применить "магазине" инструкция по изменению значения самого указателя инструкции. Мы будем называть это конкретное использование инструкция по хранению С новым именем: прыжок. Мы используем новое имя, потому что легче думать о нем как о новой концепции. Изменяя указатель инструкции, мы указываем агенту "перейти к шагу x".

7. Бесконечные Итерации: By прыжки назад, теперь вы можно заставить агента "повторить" определенное количество шагов. На данный момент у нас есть бесконечные итерации.

                      1. mov 1000 m[30]
                      2. sub m[30] 1
                      3. jmp-to 2  // infinite loop
   

8. условный - условное выполнение инструкций. С помощью предложения "conditional" вы можете условно выполнить одну из нескольких инструкций на основе текущего состояния (которое может быть установлено с помощью предыдущей инструкции).

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

   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.
   

10. наименования: присвоение имен определенной ячейке памяти, содержащей данные или удерживающей шаг. Это просто "удобство", чтобы иметь. Мы не добавляем никаких новых инструкций, имея возможность определить "имена" для участков памяти. "Нейминг" - это не инструкция для агента, это просто удобство для нас. наименования делает код (на данный момент) легче читать и легче изменить.

       #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  
    

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

    реализация: (никаких новых концепций не требуется)

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

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

...

достиг рекурсия мы останавливаемся здесь.

вывод:

в архитектуре фон Неймана, ясно "итерации" это более простая / базовая концепция, чем "рекурсия". У нас есть форма "итерации" на уровне 7, в то время как "рекурсия" находится на уровне 14 иерархии понятий.

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

какой из них "лучше"?

• вы должны использовать "итерации", когда вы обрабатываете простой, последовательные структуры данных, и везде "простой цикл" будет делать.

• вы должны использовать "рекурсию", когда вам нужно обработать рекурсивную структуру данных (мне нравится называть их" фрактальными структурами данных"), или когда рекурсивное решение явно более"элегантное".

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

наконец, обратите внимание, что у вас есть много возможностей для использования рекурсии. У вас есть Рекурсивные Структуры Данных!--12--> везде вы смотрите на один Сейчас: части DOM, поддерживающие то, что Вы читаете, - это RDS, выражение JSON-это RDS, иерархическая файловая система на вашем компьютере-это RDS, т. е. у вас есть корневой каталог, содержащий файлы и каталоги, каждый каталог, содержащий файлы и каталоги, каждый из этих каталогов, содержащих файлы и каталоги...

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

У меня был случай, когда переписывание рекурсивного алгоритма в Java сделало его медленнее.

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

хвостовая рекурсия так же быстро, как зацикливание. Многие функциональные языки имеют хвостовую рекурсию, реализованную в них.

рассмотрим, что абсолютно необходимо сделать для каждого, итерации и рекурсии.

• итерация: переход к началу цикла
• рекурсия: переход к началу вызываемой функции

вы видите,что здесь не так много места для различий.

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

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

TL;DR рекурсивные алгоритмы обычно имеют худшее поведение кэша, чем итерационные.

большинство ответов здесь неправильно. Правильный ответ:зависит. Например, вот две функции 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 на какие узлы нажимаются, а затем выскакивают и манипулируют.

рекурсивная функция работает намного быстрее, чем итерационная. Причина в том, что в последнем, для каждого элемента, a CALL функции st_push нужен, а затем еще один, чтобы st_pop.

в первом случае у вас есть только рекурсивные CALL для каждого узла.

кроме того, доступ к переменным в стеке вызовов невероятно быстрый. Это означает, что Вы читаете из памяти, которая скорее всего, всегда будет в самом сокровенном тайнике. Явный стек, с другой стороны, должен быть поддержан malloc: ed память из кучи, которая гораздо медленнее для доступа.

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

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

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

функциональное программирование-это больше о "что" вместо "как".

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

что имеет большее значение с точки зрения программиста, так это читаемость и ремонтопригодность, а не оптимизация в первом место. Опять же, "преждевременная оптимизация-корень всех зол".

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

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

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

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

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

согласно теории это одно и то же. Рекурсия и цикл с одинаковой сложностью 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;
  }