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

Question

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

Answer 1

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

Answer 2

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

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

Answer 3

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

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

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

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

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

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

Answer 4

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

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

Answer 5

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

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

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

Answer 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) рассчитывается дважды!

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

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

Answer 7

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

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

Answer 8

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

http://lambda -the-ultimate.org / узел / 1333 * +1009 *

Answer 9

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

Answer 10

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

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

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.