Посмотрите наши лучшие предложения ⇛ домены со скидками... и самые дешевые домены...

Рекурсия

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

Классическим примером рекурсии является определение функции факториала, приведенного здесь в коде C:

unsigned int factorial(unsigned int n)

{

  if (n < = 1)
      return 1;
  else
      return n * factorial(n-1);

}

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

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

Рекуррентные соотношения — уравнения с целью рекурсивного определения одной или более последовательностей. Некоторые определенные виды рекуррентного соотношения могут быть «решены», чтобы получить нерекурсивное определение.

При использовании алгоритма рекурсии выделяют как преимущества, так и недостатки. Основное преимущество — простота. Основной недостаток — часто алгоритм может требовать больших объемов памяти в том случае, если глубина рекурсии является очень большой.