Ответ 1

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

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

Ответ 2

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

Ответ 3

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

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

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

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

Ссылка 1: Haskel против PHP (рекурсия против итерации)

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

http://blog.webspecies.co.uk/2011-05-31/lazy-evaluation-with-php.html

Ссылка 2: Освоение рекурсии

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

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

https://developer.ibm.com/articles/l-recurs/

Ссылка 3: Является ли рекурсия быстрее, чем зацикливание? (Ответ)

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

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

Ответ 4

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

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

Ответ 5

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

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

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

Ответ 6

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

Например, чтобы сделать рекурсивный алгоритм Фибоначи, вы разбиваете fib (n) на fib (n-1) и fib (n-2) и вычисляете обе части. Итерация позволяет повторять одну и ту же функцию снова и снова.

Однако Фибоначчи на самом деле является сломанным примером, и я думаю, что итерация на самом деле более эффективна. Заметим, что fib (n) = fib (n-1) + fib (n-2) и fib (n-1) = fib (n-2) + fib (n-3). fib (n-1) вычисляется дважды!

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

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

Ответ 7

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

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

Ответ 8

Я считаю, что рекурсия хвоста в java в настоящее время не оптимизирована. Подробности рассыпаются на эту дискуссию по LtU и связанным ссылкам. Это может быть особенностью в предстоящей версии 7, но, по-видимому, она представляет определенные трудности в сочетании с Stack Inspection, поскольку некоторые кадры будут отсутствовать. Stack Inspection был использован для реализации своей мелкозернистой модели безопасности с Java 2.

http://lambda-the-ultimate.org/node/1333

Ответ 9

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

Ответ 10

Рекурсия очень полезна в некоторых ситуациях. Например, рассмотрим код для поиска факториала

int factorial ( int input )
{
  int x, fact = 1;
  for ( x = input; x > 1; x--)
     fact *= x;
  return fact;
}

Теперь рассмотрим его с помощью рекурсивной функции

int factorial ( int input )
{
  if (input == 0)
  {
     return 1;
  }
  return input * factorial(input - 1);
}

Наблюдая эти два, мы можем видеть, что рекурсия легко понять. Но если он не используется с осторожностью, это может быть так много ошибок. Предположим, что если мы пропустили if (input == 0), тогда код будет выполнен в течение некоторого времени и заканчивается обычно переполнением стека.

Ответ 11

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

Итеративная реализация

public static void sort(Comparable[] a)
{
    int N = a.length;
    aux = new Comparable[N];
    for (int sz = 1; sz < N; sz = sz+sz)
        for (int lo = 0; lo < N-sz; lo += sz+sz)
            merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}

Рекурсивная реализация

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
    if (hi <= lo) return;
    int mid = lo + (hi - lo) / 2;
    sort(a, aux, lo, mid);
    sort(a, aux, mid+1, hi);
    merge(a, aux, lo, mid, hi);
}

PS - это то, что сказал профессор Кевин Уэйн (Принстонский университет) на курсе по алгоритмам, представленным на Coursera.

Ответ 12

Это зависит от языка. В Java вы должны использовать циклы. Функциональные языки оптимизируют рекурсию.

Ответ 13

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

Ответ 14

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

Ответ 15

Если вы просто перебираете список, то уверен, идите дальше.

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

Ознакомьтесь с методами "find" здесь: http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html

Ответ 16

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

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

Ответ 17

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

Ответ 18

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

Например, вычисление классического факториала рекурсивным способом очень неэффективно из-за: - риск переполнения данных - риск - служебные вызовы функций занимают 80% времени выполнения

при разработке алгоритма min-max для анализа позиции в игре в шахматы, который будет анализировать последующие N шагов, может быть реализован в рекурсии по "глубине анализа" (как я делаю ^ _ ^)

Ответ 19

рекурсии? С чего начать, вики расскажут вам "процесс повторения элементов автомодельно"

Назад в день, когда я делал C, рекурсия С++ была отправкой бога, например, "Рекурсия хвоста". Вы также найдете много алгоритмов сортировки, использующих рекурсию. Пример быстрой сортировки: http://alienryderflex.com/quicksort/

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

Ответ 20

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

В моем случае я пытался реализовать возведение в матрицу путем возведения в квадрат с использованием матричных объектов Armadillo как рекурсивным, так и итерационным способом. Алгоритм можно найти здесь... https://en.wikipedia.org/wiki/Exponentiation_by_squaring. Мои функции были шаблонными, и я вычислил 1,000,000 матриц 12x12 возведенных в степень 10. Я получил следующий результат:

iterative + optimisation flag -O3 -> 2.79.. sec
recursive + optimisation flag -O3 -> 1.32.. sec

iterative + No-optimisation flag  -> 2.83.. sec
recursive + No-optimisation flag  -> 4.15.. sec

Эти результаты были получены с использованием gcc-4.8 с флагом C++ 11 (-std=C++11) и Armadillo 6.1 с Intel MKL. Компилятор Intel также показывает аналогичные результаты.

Ответ 21

Майк прав. Рекурсия хвоста не оптимизирована компилятором Java или JVM. Вы всегда получите переполнение стека с чем-то вроде этого:

int count(int i) {
  return i >= 100000000 ? i : count(i+1);
}

Ответ 22

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

Ответ 23

Рекурсия имеет тот недостаток, что алгоритм, который вы пишете с помощью рекурсии, имеет сложность O (n). Хотя итеративный подход имеет пространственную сложность O (1). Это преимущество использования итерации по рекурсии. Тогда почему мы используем рекурсию?

См. ниже.

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

Ответ 24

Насколько я знаю, Perl не оптимизирует хвостовые рекурсивные вызовы, но вы можете подделать его.

sub f{
  my($l,$r) = @_;

  if( $l >= $r ){
    return $l;
  } else {

    # return f( $l+1, $r );

    @_ = ( $l+1, $r );
    goto &f;

  }
}

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

Обратите внимание, что нет "my @_;" или "local @_;", если вы это сделали, больше не будет работать.

Ответ 25

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

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

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

Ответ 26

Используя только Chrome 45.0.2454.85 м, рекурсия кажется более приятной.

Вот код:

(function recursionVsForLoop(global) {
    "use strict";

    // Perf test
    function perfTest() {}

    perfTest.prototype.do = function(ns, fn) {
        console.time(ns);
        fn();
        console.timeEnd(ns);
    };

    // Recursion method
    (function recur() {
        var count = 0;
        global.recurFn = function recurFn(fn, cycles) {
            fn();
            count = count + 1;
            if (count !== cycles) recurFn(fn, cycles);
        };
    })();

    // Looped method
    function loopFn(fn, cycles) {
        for (var i = 0; i < cycles; i++) {
            fn();
        }
    }

    // Tests
    var curTest = new perfTest(),
        testsToRun = 100;

    curTest.do('recursion', function() {
        recurFn(function() {
            console.log('a recur run.');
        }, testsToRun);
    });

    curTest.do('loop', function() {
        loopFn(function() {
            console.log('a loop run.');
        }, testsToRun);
    });

})(window);

Результаты

//100 запусков с использованием стандартного цикла

100x для цикла. Время завершения: 7,683 мс

//100 выполняется с использованием функционального рекурсивного подхода с рекурсией хвоста

100x рекурсивный запуск. Время завершения: 4.841мс

На скриншоте ниже рекурсия снова выигрывает с большим отрывом при запуске на 300 циклов за тест

Ответ 27

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

Введем тип для простого дерева:

data Tree a = Branch (Tree a) (Tree a)
            | Leaf a
            deriving (Eq)

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

Сделайте дерево:

example :: Tree Int
example = Branch (Leaf 1) 
                 (Branch (Leaf 2) 
                         (Leaf 3))

Теперь предположим, что мы хотим добавить 1 к каждому значению в дереве. Мы можем сделать это, позвонив:

addOne :: Tree Int -> Tree Int
addOne (Branch a b) = Branch (addOne a) (addOne b)
addOne (Leaf a)     = Leaf (a + 1)

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

Что нужно, чтобы написать addOne в итеративном стиле? Что будет зацикливаться на произвольное число ветвей?

Кроме того, такую ​​рекурсию часто можно учесть в терминах "функтора". Мы можем сделать Деревья в Функторы, определив:

instance Functor Tree where fmap f (Leaf a)     = Leaf (f a)
                            fmap f (Branch a b) = Branch (fmap f a) (fmap f b)

и определяя:

addOne' = fmap (+1)

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

addOne'' = cata go where
           go (Leaf a) = Leaf (a + 1)
           go (Branch a b) = Branch a b

Ответ 28

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

Рекурсия - это способ пойти, если вы хотите итерации через файлы, уверен, что как "найти" | "grep *" работает. Сразу две рекурсии, особенно с трубой (но не делайте кучу системных вызовов, как многие любят делать, если это все, что вы собираетесь использовать там, чтобы другие могли использовать).

Языки более высокого уровня и даже clang/cpp могут реализовывать его в фоновом режиме.