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

Question

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

Answer 1

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

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

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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

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

Answer 6

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

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

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

Answer 7

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

Answer 8

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

Answer 9

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

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

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

Answer 10

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

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

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