КОНСПЕКТ ОБЗОРНОЙ ЛЕКЦИИ

Для студентов специальности
1-400101 «Программное обеспечение информационных технологий»

(А.М.Кадан, к.т.н., доцент)

Вопрос 20.
Рекурсия в программировании и разработка рекурсивных программ

Рекурсия в математике и программировании.
Рекурсия и итерация.
Структура рекурсивных подпрограмм.
Рекуррентные выражения. Определение сложности рекурсивных вычислений.
Метод «разделяй и властвуй», его достоинства и недостатки.
Сокращение сложности рекурсивных вычислений, метод динамического программирования.
Перебор с возвратом

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

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

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

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

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

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

Например, это подтверждает определение факториала

F(n) = {n*F(n-1), n > 1

{1, n = 1

Чисел Фибоначчи

Ф(n) = {Ф(n-2)+Ф(n-1), n > 2

{1, n = 1,2

Или формализация задачи о Ханойских башнях:

T(n,a,c,b) = { T(n-1,a,b,c), a->c, T(n-1,b,c,a), n > 1

{ a->c , n = 1

Аналогично, рекурсивная подпрограмма должна иметь как минимум два пути выполнения, соответствующие рекурсивному вызову на более простых данных и выполнению без рекурсии

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

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

Например, при попытке вычислить числа Фибоначчи по рекурсивной схеме

F(i) = F(i-1) + F(i-2), при N >= 1; F(0) = 0; F(1) = 1;

Текст программы будет приблизительно таким:

Function F( n : integer ) : longint;
begin
if n < 2 then F := n
else F := F(n-1) + F(n-2)
end;

Требующееся при вычислении значения F(N) по такой схеме количество рекурсивных вызовов может быть получено из решения рекуррентного выражения

T_N = T_N-1 + T_N-2, при N >= 1; T₀ = 1; T₁ = 1

T_N приблизительно равно Ф^N , где Ф »1.618 - золотая пропорция, т.е. приведенная выше программа потребует экспоненциальных временных затрат на вычисления.

Метод «разделяй и властвуй». Многие алгоритмы используют два рекурсивных вызова, каждый из которых работает приблизительно с половиной входных данных. Такая рекурсивная схема, по-видимому, представляет собой наиболее важный случай хорошо известного метода «разделяй и властвуй» (divide and conquer) разработки алгоритмов.

В качестве примера рассмотрим задачу отыскания максимального из N элементов, сохраненных в массиве a[1], . . . , a[N] с элементами типа Item. Эта задача легко может быть решена за один проход массива:

Max:=a[1];
For i:=1 to N do
if a[i] > Max then Max:=a[i];

Рекурсивное решение типа «разделяй и властвуй» - еще один простой (хотя совершенно иной) способ решения той же задачи:

Function Max (a array of Item; l, r : integer) : Item;
var u, v : Item; m : integer;
begin
   m := (l+r) / 2;
   if (l = r)
      then Max := a[l]
      else begin
              u := Max (a, 1, m);
              v := Max )a, m+1, r);
              if (u > v) then Max := u else Max := v
           end
end;

Чаще всего подход “разделяй и властвуй» используют из-за того, что он обеспечивает более быстрые решения, чем итерационные алгоритмы.

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

К примеру, приведенная выше рекурсивная схема вычисления чисел Фибоначчи абсолютно недопустима при больших значениях N, так как приводит к многократным повторным вычислениям, и экспоненциальной сложности вычислений (T_N приблизительно равно Ф^N , где Ф »1.618 есть золотая пропорция).

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

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

Технология, называемая восходящим динамическим программированием (bottom-up dynamic programming) основана на том, что значение рекурсивной функции можно определить, вычисляя все значения этой функции, начиная с наименьшего, используя на каждом шаге ранее вычисленные значения для подсчета текущего значения.

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

Нисходящее динамическое программирование (top-down dynamic programming) – еще более простая технология. Она позволяет выполнять рекурсивные функции при том же количестве итераций, что и восходящее динамическое программирование. Технология требует введения в рекурсивную программу неких средств, обеспечивающих сохранение каждого вычисленного значения и проверку сохраненных значений во избежание их повторного вычисления.

К примеру, сохраняя вычисленные значения в статическом массиве K[1..100] (предварительно проинициализированном, к примеру, числом -1), мы явным образом исключим любые повторные вычисления.

Приведенная ниже программа вычисляет F(N) за время, пропорциональное N.

Function F( n : integer ) : longint;
begin
   if (K[n] <> -1)
      then F := K[n]
      else if n < 2
              then F := n
              else begin
                      t := F(n-1) + F(n-2)
                      K[n] := t;
                      F := t
end;

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

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

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

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

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

Подобная стратегия применима, например, в логических играх, где игровое пространство и множество допустимых ходов ограничено правилами игры.