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

Question

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

Answer 1

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

См. Ниже.

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

Answer 2

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

Answer 3

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

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

Answer 4

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

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

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

Answer 5

При использовании только 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 циклами на тест

Answer 6

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

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

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

Answer 7

Я собираюсь ответить на ваш вопрос, спроектировав структуру данных на 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

Answer 8

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

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

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

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

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

  }
}

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

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