Вопрос:

Рекурсия или итерация?

performance algorithm language-agnostic recursion

135140 просмотра

28 ответа

11107 Репутация автора

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

Автор: Omnipotent Источник Размещён: 16.09.2008 01:33

Ответы (28)


4 плюса

0 Репутация автора

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

Автор: mc Размещён: 16.09.2008 01:35

4 плюса

251 Репутация автора

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

Автор: MovEaxEsp Размещён: 16.09.2008 01:38

2 плюса

71 Репутация автора

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

Автор: metadave Размещён: 16.09.2008 01:39

16 плюса

4863 Репутация автора

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

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

Автор: Doron Yaacoby Размещён: 16.09.2008 01:43

11 плюса

10941 Репутация автора

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

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

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

Автор: zweiterlinde Размещён: 16.09.2008 01:45

2 плюса

2121 Репутация автора

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

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

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

Автор: ugasoft Размещён: 16.09.2008 01:48

173 плюса

3213 Репутация автора

Решение

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

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

Автор: Paul Osborne Размещён: 16.09.2008 01:52

7 плюса

574 Репутация автора

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

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

Автор: entzik Размещён: 16.09.2008 01:55

6 плюса

0 Репутация автора

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

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

Автор: Mike Edwards Размещён: 16.09.2008 01:56

295 плюса

7231 Репутация автора

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

Автор: Leigh Caldwell Размещён: 16.09.2008 02:11

1 плюс

16152 Репутация автора

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

int count(int i) {
  return i >= 100000000 ? i : count(i+1);
}
Автор: noah Размещён: 16.09.2008 02:19

0 плюса

25531 Репутация автора

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

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

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

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

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

  }
}

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

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

Автор: Brad Gilbert Размещён: 10.11.2008 05:28

4 плюса

22827 Репутация автора

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

Автор: Warrior Размещён: 29.11.2008 06:23

5 плюса

746 Репутация автора

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

Автор: Felix Размещён: 24.06.2011 03:39

5 плюса

2008 Репутация автора

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

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), то код будет выполняться некоторое время и заканчивается, как правило, переполнением стека.

Автор: Harikrishnan Размещён: 24.06.2011 03:46

76 плюса

10705 Репутация автора

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

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

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

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

Ссылка 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, который похож на ваш. Автор указывает, что многие тесты, связанные либо с рекурсивными, либо с циклическими, очень специфичны для каждого языка. Императивные языки обычно быстрее используют цикл и медленнее с рекурсией и наоборот для функциональных языков. Я полагаю, что основной смысл этой ссылки заключается в том, что очень трудно ответить на вопрос в не зависящем от языка / ситуации слепом смысле.

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

Автор: Swift Размещён: 24.06.2011 03:47

2 плюса

1530 Репутация автора

Рекурсия? С чего начать, вики расскажет вам «это процесс повторения предметов самоподобным способом»

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

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

Автор: Nickz Размещён: 24.06.2011 03:59

3 плюса

6854 Репутация автора

Если вы просто перебираете список, то, конечно же, перебираете.

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

Проверьте методы поиска здесь: http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html

Автор: Joe Cheng Размещён: 24.06.2011 04:01

8 плюса

965 Репутация автора

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

Например, чтобы создать рекурсивный алгоритм Фибоначчи, вы разбиваете 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) рассчитывается дважды!

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

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

Автор: Ben Размещён: 24.06.2011 04:18

3 плюса

8526 Репутация автора

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

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

Автор: SK-logic Размещён: 24.06.2011 10:33

5 плюса

6398 Репутация автора

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

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

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.

Автор: Nikunj Banka Размещён: 08.12.2012 06:26

-1 плюса

1896 Репутация автора

Я собираюсь ответить на ваш вопрос, спроектировав структуру данных на 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
Автор: nomen Размещён: 22.03.2013 11:36

0 плюса

12701 Репутация автора

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

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

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

Автор: ccpizza Размещён: 21.04.2013 06:30

1 плюс

2220 Репутация автора

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

Автор: Grigori A. Размещён: 29.01.2014 12:51

0 плюса

1067 Репутация автора

Используя только 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 прогонов, используя стандартный цикл for

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

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

100-кратный рекурсивный прогон. Время для завершения: 4.841мс

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

Рекурсия снова побеждает!

Автор: Alpha G33k Размещён: 16.09.2015 03:50

2 плюса

311 Репутация автора

В C ++, если рекурсивная функция является шаблонной, то у компилятора больше шансов оптимизировать ее, так как все дедукции типов и реализации функций будут происходить во время компиляции. Современные компиляторы также могут встроить функцию, если это возможно. Поэтому, если использовать флаги оптимизации, такие как -O3или -O2in 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 flag ( -std=c++11) и Armadillo 6.1 с Intel mkl. Компилятор Intel также показывает аналогичные результаты.

Автор: Titas Chanda Размещён: 09.10.2015 11:22

1 плюс

31 Репутация автора

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

Увидеть ниже.

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

Автор: Varunnuevothoughts Размещён: 02.06.2017 11:14

-2 плюса

1 Репутация автора

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

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

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

Автор: F13n0 Размещён: 30.11.2017 01:46
Вопросы из категории :
32x32