Рекурсивные алгоритмы

Лекция 5

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

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

Неразрывно с понятием рекурсивного алгоритма связано понятие рекурсивной функции. Существует два определения этого понятия.

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

Второе определение, которое и будет использоваться здесь, происходит из области теории программирования.

Рекурсивная функция – это функция, которая вызывает саму себя.

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

1. Примеры простейших рекурсивных функций

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

Рис. 2. Нерекурсивная функция вычисления факториала числа

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

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

Рис. 3. Пример рекурсивной функции, использующей два рекурсивных вызова