Рекурсия или Итерация?
https://stackoverflow.com/questions/72209
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Снизится ли производительность, если мы будем использовать цикл вместо рекурсии или наоборот в алгоритмах, где оба могут служить одной и той же цели?Например:Проверьте, является ли данная строка палиндромом.Я видел многих программистов, использующих рекурсию как средство показать, когда простой итерационный алгоритм может подойти по всем параметрам.Играет ли компилятор жизненно важную роль в принятии решения о том, что использовать?
Решение
Возможно, что рекурсия обойдется дороже, в зависимости от того, является ли рекурсивная функция хвост рекурсивный (последняя строка - рекурсивный вызов).Хвостовая рекурсия следует быть распознанным компилятором и оптимизированным для своего итеративного аналога (при сохранении краткой и понятной реализации, которая есть в вашем коде).
Я бы написал алгоритм таким образом, который имеет наибольший смысл и является наиболее понятным для бедолаги (будь то вы сами или кто-то другой), которому приходится поддерживать код в течение нескольких месяцев или лет.Если вы столкнетесь с проблемами производительности, то профилируйте свой код, а затем и только тогда займитесь оптимизацией, перейдя к итеративной реализации.Возможно, вы захотите заглянуть в запоминание и динамическое программирование.
Другие советы
Циклы могут привести к увеличению производительности вашей программы.Рекурсия может привести к увеличению производительности вашего программиста.Выбирайте, что важнее в вашей ситуации!
Сравнивать рекурсию с итерацией - все равно что сравнивать крестообразную отвертку с плоской.По большей части вы мог бы открутите любой винт с крестообразной головкой с плоской головкой, но было бы проще, если бы вы использовали отвертку, предназначенную для этого винта, не так ли?
Некоторые алгоритмы просто поддаются рекурсии из-за способа их разработки (последовательности Фибоначчи, обход древовидной структуры и т.д.).Рекурсия делает алгоритм более кратким и простым для понимания (следовательно, доступным для совместного использования).
Кроме того, некоторые рекурсивные алгоритмы используют "Отложенную оценку", что делает их более эффективными, чем их итеративные собратья.Это означает, что они выполняют дорогостоящие вычисления только в то время, когда они необходимы, а не при каждом запуске цикла.
Этого должно быть достаточно, чтобы вы начали.Я тоже найду для вас несколько статей и примеров.
Ссылка 1: Хаскель против PHP (Рекурсия против Итерации)
Вот пример, когда программисту пришлось обрабатывать большой набор данных с помощью PHP.Он показывает, как легко было бы справиться с этим в Haskel с помощью рекурсии, но поскольку в PHP не было простого способа выполнить тот же метод, он был вынужден использовать итерацию для получения результата.
http://blog.webspecies.co.uk/2011-05-31/lazy-evaluation-with-php.html
Ссылка 2: Освоение Рекурсии
Большая часть плохой репутации recursion связана с высокой стоимостью и неэффективностью императивных языков.Автор этой статьи рассказывает о том, как оптимизировать рекурсивные алгоритмы, чтобы сделать их быстрее и эффективнее.Он также рассказывает о том, как преобразовать традиционный цикл в рекурсивную функцию, и о преимуществах использования конечной рекурсии.Я думаю, что его заключительные слова действительно подытожили некоторые из моих ключевых моментов:
"рекурсивное программирование дает программисту лучший способ организации кода способом, который одновременно удобен для сопровождения и логически непротиворечив".
Ссылка 3: Является ли рекурсия когда-нибудь быстрее зацикливания?(Ответ)
Вот ссылка на ответ на вопрос stackoverflow, который похож на ваш.Автор указывает, что многие тесты, связанные либо с рекурсией, либо с зацикливанием, являются очень специфичный для языка.Императивные языки обычно работают быстрее при использовании цикла и медленнее при рекурсии, и наоборот для функциональных языков.Я думаю, главный момент, который следует извлечь из этой ссылки, заключается в том, что очень трудно ответить на вопрос в языковом агностическом / ситуационном слепом смысле.
Рекурсия требует больших затрат памяти, поскольку для каждого рекурсивного вызова обычно требуется, чтобы адрес памяти был помещен в стек - чтобы позже программа могла вернуться к этой точке.
Тем не менее, есть много случаев, когда рекурсия намного более естественна и удобочитаема, чем циклы, например, при работе с деревьями.В этих случаях я бы рекомендовал придерживаться рекурсии.
Как правило, можно было бы ожидать, что снижение производительности будет происходить в другом направлении.Рекурсивные вызовы могут привести к созданию дополнительных фреймов стека;наказание за это разное.Кроме того, в некоторых языках, таких как Python (точнее, в некоторых реализациях некоторых языков ...), вы можете довольно легко столкнуться с ограничениями стека для задач, которые вы могли бы указать рекурсивно, таких как поиск максимального значения в древовидной структуре данных.В этих случаях вы действительно хотите придерживаться циклов.
Написание хороших рекурсивных функций может несколько снизить снижение производительности, предполагая, что у вас есть компилятор, который оптимизирует хвостовые рекурсии и т.д.(Также дважды проверьте, чтобы убедиться, что функция действительно является хвостовой рекурсивной - это одна из тех вещей, в которых многие люди допускают ошибки.)
Помимо "крайних" случаев (высокопроизводительные вычисления, очень большая глубина рекурсии и т.д.), предпочтительнее использовать подход, который наиболее четко выражает ваши намерения, хорошо продуман и удобен в обслуживании.Оптимизируйте только после определения потребности.
Рекурсия лучше, чем итерация, для задач, которые можно разбить на множественный, кусочки поменьше.
Например, чтобы создать рекурсивный алгоритм Fibonnaci, вы разбиваете 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) вычисляется дважды!
Лучшим примером является рекурсивный алгоритм для дерева.Проблему анализа родительского узла можно разбить на множественный меньшие проблемы с анализом каждого дочернего узла.В отличие от примера Фибоначчи, более мелкие задачи независимы друг от друга.
Так что да - рекурсия лучше, чем итерация, для задач, которые можно разбить на несколько, более мелких, независимых, похожих задач.
Ваша производительность ухудшается при использовании рекурсии, потому что вызов метода на любом языке требует большой подготовки:вызывающий код отправляет адрес возврата, параметры вызова, некоторая другая контекстная информация, такая как регистры процессора, может быть где-то сохранена, и во время возврата вызываемый метод отправляет возвращаемое значение, которое затем извлекается вызывающим объектом, и любая ранее сохраненная контекстная информация будет восстановлена.разница в производительности между итеративным и рекурсивным подходами заключается во времени, которое занимают эти операции.
С точки зрения реализации, вы действительно начинаете замечать разницу, когда время, необходимое для обработки вызывающего контекста, сопоставимо со временем, необходимым для выполнения вашего метода.Если выполнение вашего рекурсивного метода занимает больше времени, чем выполнение части управления контекстом вызова, используйте рекурсивный способ, поскольку код, как правило, более читабелен и прост для понимания, и вы не заметите потери производительности.В противном случае используйте итерацию по соображениям эффективности.
Я считаю, что хвостовая рекурсия в java в настоящее время не оптимизирована.Детали разбросаны по всей поверхности это обсуждение LtU и связанных с ним ссылок.IT мочь это будет функция в предстоящей версии 7, но, по-видимому, в сочетании с проверкой стека это создает определенные трудности, поскольку некоторые кадры будут отсутствовать.Проверка стека использовалась для реализации их детализированной модели безопасности начиная с Java 2.
Есть много случаев, когда это дает гораздо более элегантное решение по сравнению с итерационным методом, общим примером является обход двоичного дерева, поэтому его не обязательно сложнее поддерживать.В общем, итеративные версии обычно немного быстрее (и во время оптимизации вполне могут заменить рекурсивную версию), но рекурсивные версии проще для понимания и корректной реализации.
Рекурсия очень полезна в некоторых ситуациях.Например, рассмотрим код для нахождения факториала
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), затем код будет выполняться в течение некоторого времени и обычно заканчивается переполнением стека.
Во многих случаях рекурсия выполняется быстрее из-за кэширования, которое повышает производительность.Например, вот итеративная версия сортировки слиянием с использованием традиционной процедуры слияния.Он будет работать медленнее, чем рекурсивная реализация, из-за повышения производительности кэширования.
Итеративная реализация
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.
Используя рекурсию, вы несете расходы на вызов функции при каждой "итерации", тогда как при использовании цикла единственное, за что вы обычно платите, - это приращение / уменьшение.Таким образом, если код для цикла не намного сложнее кода для рекурсивного решения, цикл обычно превосходит рекурсию.
Рекурсия и итерация зависят от бизнес-логики, которую вы хотите реализовать, хотя в большинстве случаев они могут использоваться взаимозаменяемо.Большинство разработчиков используют рекурсию, потому что ее легче понять.
Это зависит от языка.В Java вы должны использовать циклы.Функциональные языки оптимизируют рекурсию.
Если вы просто выполняете итерацию по списку, то, конечно, выполняйте итерацию дальше.
В паре других ответов упоминался обход дерева (в глубину).Это действительно отличный пример, потому что это очень распространенная вещь, которую можно сделать с очень распространенной структурой данных.Рекурсия чрезвычайно интуитивно понятна для решения этой проблемы.
Ознакомьтесь с методами "поиска" здесь:http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html
Рекурсия более проста (и, следовательно, более фундаментальна), чем любое возможное определение итерации.Вы можете определить полную по Тьюрингу систему, используя только пара комбинаторов (да, даже рекурсия сама по себе является производным понятием в такой системе). Лямбда математический анализ - не менее мощная фундаментальная система, включающая рекурсивные функции.Но если вы хотите правильно определить итерацию, для начала вам понадобится гораздо больше примитивов.
Что касается кода - нет, рекурсивный код на самом деле гораздо проще понять и поддерживать, чем чисто итеративный, поскольку большинство структур данных рекурсивны.Конечно, для того, чтобы сделать это правильно, понадобился бы язык с поддержкой функций высокого порядка и замыканий, по крайней мере, чтобы получить все стандартные комбинаторы и итераторы аккуратным способом.Конечно, в C ++ сложные рекурсивные решения могут выглядеть немного уродливо, если только вы не заядлый пользователь FC++ и похожи друг на друга.
Я бы подумал, что при рекурсии (без хвоста) будет снижаться производительность при выделении нового стека и т.д. При каждом вызове функции (конечно, в зависимости от языка).
это зависит от "глубины рекурсии".это зависит от того, насколько накладные расходы на вызов функции повлияют на общее время выполнения.
Например, вычисление классического факториала рекурсивным способом очень неэффективно из-за:- риск переполнения данных - риск переполнения стека - служебные данные при вызове функции занимают 80% времени выполнения
при разработке алгоритма min-max для анализа позиций в игре в шахматы, который будет анализировать последующие N ходов, можно реализовать рекурсию по "глубине анализа" (как я делаю ^_^)
Рекурсия?С чего мне начать, wiki скажет вам: “это процесс повторения элементов самоподобным способом".
В те времена, когда я занимался C, рекурсия C ++ была ниспослана богом, что-то вроде "Хвостовой рекурсии".Вы также обнаружите, что многие алгоритмы сортировки используют рекурсию.Пример быстрой сортировки: http://alienryderflex.com/quicksort/
Рекурсия, как и любой другой алгоритм, полезна для конкретной задачи.Возможно, вы не сможете найти применение сразу или часто, но возникнут проблемы, и вы будете рады, что это доступно.
В C ++, если рекурсивная функция является шаблонной, то у компилятора больше шансов оптимизировать ее, поскольку весь вывод типов и создание экземпляров функций будут происходить во время компиляции.Современные компиляторы также могут встроить функцию, если это возможно.Итак, если использовать флаги оптимизации, такие как -O3 или -O2 в g++, тогда рекурсии могут иметь шанс быть быстрее, чем итерации.В итеративных кодах компилятор получает меньше шансов оптимизировать его, так как он уже находится в более или менее оптимальном состоянии (если написан достаточно хорошо).
В моем случае я пытался реализовать возведение матрицы в степень путем возведения в квадрат с использованием объектов Armadillo matrix, как рекурсивным, так и итеративным способом.С алгоритмом можно ознакомиться здесь... 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 также показывает аналогичные результаты.
Майк прав.Хвостовая рекурсия - это нет оптимизирован компилятором Java или JVM.Вы всегда будете получать переполнение стека с чем-то вроде этого:
int count(int i) {
return i >= 100000000 ? i : count(i+1);
}
Вы должны иметь в виду, что, используя слишком глубокую рекурсию, вы столкнетесь с переполнением стека, в зависимости от допустимого размера стека.Чтобы предотвратить это, обязательно укажите какой-нибудь базовый вариант, который завершит вашу рекурсию.
Недостаток рекурсии в том, что алгоритм, который вы пишете с использованием рекурсии, имеет O (n) пространственную сложность.В то время как итеративный подход имеет пространственную сложность O (1).В этом преимущество использования итерации перед рекурсией.Тогда почему мы используем рекурсию?
Смотрите ниже.
Иногда проще написать алгоритм, используя рекурсию, в то время как немного сложнее написать тот же алгоритм, используя итерацию.В этом случае, если вы решите следовать итерационному подходу, вам придется обрабатывать stack самостоятельно.
Насколько я знаю, Perl не оптимизирует хвостовые рекурсивные вызовы, но вы можете подделать это.
sub f{
my($l,$r) = @_;
if( $l >= $r ){
return $l;
} else {
# return f( $l+1, $r );
@_ = ( $l+1, $r );
goto &f;
}
}
При первом вызове он выделит место в стеке.Затем он изменит свои аргументы и перезапустит подпрограмму, не добавляя больше ничего в стек.Поэтому он будет притворяться, что никогда не вызывал свое "я", превращая это в итеративный процесс.
Обратите внимание, что здесь нет "my @_;" или "local @_;", если бы вы это сделали, это бы больше не работало.
Используя только Chrome 45.0.2454.85 m, рекурсия, кажется, выполняется намного быстрее.
Вот этот код:
(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
100 раз для выполнения цикла.Время для завершения: 7,683 мс
// 100 запусков с использованием функционально-рекурсивного подхода с хвостовой рекурсией
100-кратный запуск рекурсии.Время для завершения: 4,841 мс
На скриншоте ниже рекурсия снова выигрывает с большим отрывом при запуске со скоростью 300 циклов за тест
Если итерации являются атомарными и на порядки дороже, чем запуск нового стекового фрейма и создание нового потока и у вас есть несколько ядер и ваша среда выполнения может использовать их все, тогда рекурсивный подход может дать огромный прирост производительности в сочетании с многопоточностью.Если среднее число итераций непредсказуемо, то может быть хорошей идеей использовать пул потоков, который будет контролировать распределение потоков и предотвращать создание вашим процессом слишком большого количества потоков и перегрузку системы.
Например, в некоторых языках существуют рекурсивные многопоточные реализации сортировки слиянием.
Но опять же, многопоточность можно использовать с циклированием, а не с рекурсией, поэтому то, насколько хорошо будет работать эта комбинация, зависит от большего количества факторов, включая операционную систему и ее механизм распределения потоков.
Я собираюсь ответить на ваш вопрос, разработав структуру данных 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
Переполнение стека произойдет только в том случае, если вы программируете на языке, в котором нет встроенного управления памятью....В противном случае убедитесь, что у вас есть что-то в вашей функции (или вызов функции, STDLBS и т.д.).Без рекурсии было бы просто невозможно иметь такие вещи, как...В Google, SQL или в любом другом месте необходимо эффективно сортировать большие структуры данных (классы) или базы данных.
Рекурсия - это правильный путь, если вы хотите перебирать файлы, уверен, именно так работает 'find * | ?grep *'.Своего рода двойная рекурсия, особенно с каналом (но не делайте кучу системных вызовов, как любят делать многие, если это что-то, что вы собираетесь выложить для использования другими).
Языки более высокого уровня и даже clang / cpp могут реализовать то же самое в фоновом режиме.
