Рекурсия быстрее, чем цикл?

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

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

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

Ответы

Ответ 1

Это зависит от используемого языка. Вы написали 'language-agnostic', поэтому я приведу несколько примеров.

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

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

Я знаю, что в некоторых реализациях Схемы рекурсия обычно будет быстрее, чем цикл.

Короче говоря, ответ зависит от кода и реализации. Используйте любой стиль, который вы предпочитаете. Если вы используете функциональный язык, рекурсия может быть быстрее. Если вы используете императивный язык, итерация, вероятно, будет быстрее. В некоторых средах оба метода приведут к созданию одной и той же сборки (поставьте ее в трубку и курите).

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

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

Ответ 2

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

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

Объяснение:

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

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

Задайте себе. Что вам нужно для вычислить значение, т.е. следовать алгоритму и достичь результата?

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

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

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

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

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

    b) Логика и арифметика

    • и, или, xor, not
    • add, sub, mul, div. например добавить m [7] m [8]

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

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

    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)

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

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

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

  • Перейти. После того, как у вас есть упорядоченное количество шагов и указатель инструкций, вы можете применить инструкцию store, чтобы изменить значение инструкции Указатель сам. Мы будем называть это конкретное использование команды store с новым именем: Переход. Мы используем новое имя, потому что легче думать об этом как о новой концепции. Изменяя указатель инструкции, мы инструктируем агента "перейти на шаг 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

  • Стек. Вы определяете пространство памяти для работы как "стек", вы можете "нажимать" значения в стеке, а также "всплывать" последнее "нажатое" значение. Для реализации стека вам понадобится Stack Pointer (аналогично указанию инструкций), который указывает на фактическую "головку" стека. Когда вы "нажимаете" значение, указатель стека уменьшается и вы сохраняете значение. Когда вы "поп", вы получаете значение в фактическом указателе стека, а затем указатель стека увеличивается.

  • Подпрограммы Теперь, когда у нас есть стек, мы можем реализовать правильные подпрограммы, позволяющие вложенные вызовы. Реализация аналогична, но вместо сохранения указателя инструкций в предопределенной ячейке памяти мы "нажимаем" значение IP в стеке. В конце подпрограммы мы просто "выталкиваем" значение из стека, эффективно прыгая обратно в инструкцию после первоначального вызова. Эта реализация, имеющая "стек", позволяет вызывать подпрограмму из другой подпрограммы. С помощью этой реализации мы можем создавать несколько уровней абстракции при определении новых инструкций в качестве подпрограмм, используя основные инструкции или другие подпрограммы в качестве строительных блоков.

  • Рекурсия. Что происходит, когда подпрограмма вызывает себя?. Это называется "рекурсия".

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

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

...

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

Вывод:

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

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

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

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

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

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

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

Ответ 3

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

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

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

Ответ 4

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

Ответ 5

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

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

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

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

Ответ 6

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

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

Ответ 7

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

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

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

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

Ответ 8

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

Ответ 9

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

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

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

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

Ответ 10

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

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

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

Ответ 11

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

Ответ 12

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