- “Итерация от человека, рекурсия — от Бога”. (Питер Дойч)
- “Чтобы понять рекурсию, нужно сначала понять рекурсию”. (фольклор)
Рекурсия — это прием программирования, при котором решение задачи сводится к некоторым действиям плюс решение такой же задачи, но в более простом случае. Под более простым подразумевается либо случай с меньшими входными данными, либо с меньшим их количеством.
Пример: возведение числа X в натуральную степень N.
По определению, XN=X*X*X*…*X (N раз).
Преобразуем равенство: XN=X*(X*X*…*X). Выражение в скобках содержит произведение числа X само на себя N-1 раз, что по определению равно XN-1.
Таким образом XN=X*X(N-1)
В словесной формулировке результаты преобразований будут звучать так: чтобы найти N-ю степень числа надо найти N-1-ю степень числа и умножить ее на само число. Таким образом решение задачи с параметром N свелось к решению задачи с параметром N-1. В свою очередь, используя аналогичные рассуждения можно свести задачу с параметром N-1 к задаче с параметром N-2, а ту, в свою очередь к N-3 и так далее. В какой-то момент мы сведем задачу к N=1 или N=0 — параметрам, при которых дальнейшее упрощение смысла не имеет, так как нулевая или первая степень не требуют вычислений.
На этом примере видно, что для описания рекурсивного решения необходимы две четко определенные вещи:
- правило, по которому решение задачи в сложном случае сводится к решению такой же задачи, но в более простом случае;
- условие, при котором дальнейшее упрощение нужно прекратить (терминальное условие). При отсутствии этого условия упрощение будет продолжаться до бесконечности и получится вечный цикл, чего при написании программ обычно не хочется.
С точки зрения программирования рекурсивное решение записывается в виде подпрограммы (процедуры или функции), содержащей вызов самой себя. Для примера со степенью возможна, к примеру, такая реализация:
function power(x : real; n : integer): real;
begin
if n=0 then power := 1
else power := x * power (x, n — 1);
end;
Первая строка представляет собой терминальное условие (если нужно возвести в нулевую степень, то ответ будет 1 и работа подпрограммы будет закончена), вторая строка — это правило перехода от более сложной задачи к менее сложной (вычислить такую же функцию с параметром (n — 1), ее результат домножить на x и закончить работу функции.
Пусть требуется вычислить приведенную выше функцию с параметрами: power(2, 2). Тогда подпрограмма вызовет свою компию с параметрами power(2,1), а новая копия подпрограммы в свою очередь вызовет еще одну — с параметрами power(2,0), и только последняя из вызванных функций будет готова сразу выдать ответ.
Если изобразить написанное в таблице в виде схемы, то получится цепочка рекурсивных вызовов:
power(2,2) — power(2,1) — power(2,0)
Длина такой цепочки называется глубиной рекурсии.
Основной идеей рекурсивного решения является “вера” в то, что внутренняя функция успешно справится с решением своей более простой задачи. А это вполне возможно, так как внутренняя функция может быть либо последней в цепочке рекурсии (тогда она выдает простой ответ), либо от нее цепочка будет тянуться дальше, тогда все зависит от правильности рекурсивного соотношения.
Утверждение: любой цикл можно заменить рекурсией и наоборот.
Однако, в некоторых задачах рекурсивное решение является более изящным и легким для написания.
Рассмотрим пример: пусть требуется написать программу, для построения такой фигуры (<Рисунок1>):
Рис. 1
Фигура представляет собой равнобедренный прямоугольный треугольник с длиной катета равной a. Внутри него располагаются три равных треугольника (также прямоугольных и равнобедренных). Катеты внутренних треугольников в 2 раза меньше катетов внешнего. Каждый из внутренних треугольников также содержит внутри себя по три треугольника, которые в свою очередь могут содержать еще более маленькие треугольники и так далее.
Собственно, в самом описании геометрической фигуры полностью изложен механизм рекурсивного решения данной задачи. Любой внутренний треугольник по структуре ничем не отличается от внешнего. Таким образом, требуется написать подпрограмму, которая построит треугольник, а затем вызовет саму себя для построения трех меньших треугольников внутри данного. Терминальным условием в этом случае будет ситуация, когда длина катета меньше либо равна 1 (катет превращается в одну точку).
Подпрограмма для решения такой задачи может выглядеть, например, так:
procedure triangle(x,y,a:integer); {пусть (x,y) — положение прямого угла, a — длина катета}
begin
line(x, y, x + a, y);
line(x, y, x, y - a);
line(x + a, y, x, y - a); {построили контур большого треугольника}
if (a>1) then begin {если наш треугольник должен содержать внутренние — построим их по тому же правилу что и большой}
triangle(x, y, a div 2); {меньший треугольник, у которого общий с большим прямой угол}
triangle(x, y — a div 2, a div 2); {верхний треугольник}
triangle(x + a div 2, y, a div 2); {правый треугольник}
end;
end;
При написании данной процедуры считается, что ось Y экрана направлена сверху вниз, поэтому чем выше точка, тем меньше будет ее координата.
Кстати, на примере этого решения хорошо видно, что рекурсию не всегда легко заменить циклом.
Рассмотрим еще один пример: пусть требуется написать подпрограмму для изображения серии вложенных окружностей (<Рисунок2>) Окружность диаметра d содержит внутри себя 4 одинаковых окружности диаметра d/2, которые касаются ее в верхней, нижней, правой и левой точках. С свою очередь каждая из четырех внутренних окружностей также содержит внутри еще по 4 окружности меньшего диаметра и так далее.
Рис. 2
Аналогично предыдущей задаче, любая из внутренних окружностей есть полное подобие внешней. Окончание рекурсивных вызовов будет задаваться условием d<=1 (на каком-то уровне упрощения окружность превратилась в точку).
Подпрограмма для решения этой задачи может выглядеть, например, так:
procedure circles(x,y, r : integer); {пусть (x,y) — координаты центра окружности, r - радиус }
begin
circle(x,y,r);
if (r>=2) then begin
circles(x — r div 2, y, r div 2);
circles(x + r div 2, y, r div 2);
circles(x, y — r div 2, r div 2);
circles(x, y + r div 2, div 2);
end;
end;
Аналогично предыдущей задаче данная подпрограмма строит только контур большой окружности, а всю работу по построению внутренних перекладывает на свои собственные копии, но вызванные с другими параметрами.
Классические задачи с рекурсивным решением
Ханойские башни
Дано три стержня. На первом стержне в начальный момент времени нанизано N колец различного диаметра, так что они образуют пирамидку (<Рисунок3>).
Требуется перенести все кольца с первого стержня на третий за минимальное количество ходов, соблюдая два правила:
- можно брать только свободное кольцо (то, на котором ничего не лежит);
- взятое кольцо можно нанизывать на любой стержень, но нельзя класть большее кольцо на меньшее.
Рассмотрим случай, когда N=1. Здесь решение очевидно, необходимо просто перенести кольцо с первого стержня на третий.
При N=2 решение также очевидно. Необходимо перенести верхнее кольцо на второй стержень, затем освободившееся нижнее на 3-й, а потом маленькое кольцо также перенести на 3-й стержень.
При N=3 можно сделать следующее замечание. Пока верхние два кольца куда-нибудь не денутся с нижним кольцом по правилам ничего сделать нельзя. Поэтому можно временно про нижнее кольцо “позабыть” и решать только задачу переноса двух верхних колец на второй стержень. После этого свободное нижнее кольцо можно перенести на третий стержень, а затем опять вернуться к задаче о перемещении первых двух колец. Таким образом задача для N=3 сводится к двум задачам для N=2 и одной задаче для N=1.
Аналогично, для N=4 задача сводится к переносу трех верхних колец на второй стержень, переносу нижнего кольца на третий стержень и переносу на него трех колец со второго стержня. А задачи переноса трех верхних колец, как мы уже убедились, сводятся к задаче переноса двух.
Из этих рассуждений можно получить как схему упрощения задачи и сведения ее решения к более простому случаю (действительно, для произвольного N нужно сначала N-1 кольцо поместить на второй стержень, потом перенести самое большое на третий, и поверх него поместить N-1).
Наибольший общий делитель (НОД)
Дано два натуральных числа. Требуется найти их наибольший общий делитель, то есть максимальное из чисел, на которое оба исходных числа делятся без остатка.
Найдем остаток от деления большего числа на меньшее.
Если остаток не равен нулю, то повторим шаг №1 для меньшего числа и остатка.
Если остаток равен нулю, то последнее число, на которое делалось последнее деление и будет НОД
Функция вычисления НОД двух чисел может быть записана таким образом:
function NOD(a, b : integer) : integer;
var
c: integer;
begin
if b>a then begin {сделаем так, чтобы в a находилось большее значение}
c:=a;
a:=b;
b:=c;
end;
c:=a mod b;
if c=0 then NOD:=b
else NOD:=NOD(b,c);
end;
Моделирование работы автопарковки*
Имеется автопарковка, на которую автомобили ставятся в один ряд. Длина автопарковки — N метров. Ширина автомобиля — x метров. К сожалению, на парковке отсутствует разметка — то есть каждый подъезжающий водитель находит произвольное (случайное) место, достаточное для размещения автомобиля и ставит туда свою машину. Если не осталось свободного места ширины достаточной ширины, то парковка считается заполненной. Требуется смоделировать данный процесс и определить, сколько автомобилей будет помещаться на парковке при полном заполнении (если процесс моделирования повторить несколько раз, то можно получить достаточно точную статистику и определить, сколько автомобилей в среднем будет находиться на этой стоянке).
Ключевым данным в этой задаче является то, что водитель находит произвольное место. То есть он не обязан размещать свою машину вплотную к уже имеющимся.
На рисунке (Рисунок4) показано возможное размещение автомобилей.
Рис. 4
Идея решения: представим всю парковку в виде отрезка числовой прямой от 0 до N. Тогда первый автомобиль поделит этот отрезок на две части — слева от автомобиля и справа. Каждый из полученных отрезков мы можем рассматривать независимо и заполнять по тем же правилам, что и основной.
Продемонстрируем процесс моделирования на рисунках:
Начальная ситуация (<Рисунок5>). Дана незанятая парковка
рис. 5
Первый этап. В произвольное (случайно выбранное) место поставлен автомобиль. Пусть левая граница автомобиля имеет координату a, тогда правая a+x (<Рисунок6>).
Рис. 6
Получилось два отрезка: [0; a] и [a+x; N], для каждого из которых необходимо решить точно такую же задачу — разместить автомобили.
Подпрограмма для решения этой задачи моделирования может выглядеть так:
function Cars(left, right : real) : integer;
var
place: real;
begin
if right-left<x then Cars:=0 {терминальное условие: на отрезок недостаточной ширины машину поставить нельзя}
else begin
place:=random*((right-x)-left) + left; { случайно выберем левую границу автомобиля}
Cars:=Cars(left, place) + Cars (place + x, right);
end;
end;
Стоит обратить внимание на формулу place:=random*((right-x)-left) + left. Здесь random — это функция, генерирующее случайное число в интервале [0; 1). Левая граница автомобиля не может находиться ближе чем на расстоянии x от правого края парковки (иначе правая часть автомобиля окажется за пределами парковки), поэтому ширина дипазона случайных чисел (множитель при random) взята не (right-left), а ((right-x)-left). Внутренние скобки здесь носят логический, а не математический характер. Понятно также, что координата левой границы автомобиля не может быть меньше, чем левая граница отрезка. Отсюда последнее +left в формуле.
Небольшие общие примечания
Рекурсия может быть не только прямой (когда подпрограмма содержит вызов самой себя), но и косвенной (когда подпрограмма X вызывает подпрограмму Y, которая опять вызывает подпрограмму X и так далее).
Хотя рекурсия и является довольно мощным приемом, особенно там, где это касается организации перебора, она не всегда является оптимальным способом решения задачи.
Кроме того, каждый новый вызов подпрограммы сопровождается выделением памяти под ее локальные переменные и параметры, поэтому в случае достаточно глубокой рекурсии возможны ошибки, связанные с недостатком памяти для работы программы.
Упражнения
Напишите рекурсивную программу построения фигуры (<Рисунок7>).
Рис. 7
- Напишите рекурсивную функцию нахождения суммы цифр натурального числа.
- Напишите рекурсивную подпрограмму переворота строки (последний символ на первое место, предпоследний — на второе и так далее).
- Напишите рекурсивную подпрограмму подсчета количества слов в строке (словом считается последовательность символов, внутри которой нет пробелов). Слова отделены друг от друга одиночными пробелами.
- * Напишите подпрограмму для открытия клетки в игре “сапер”. Поле задано двумерным массивом. Даны также координаты открываемой клетки. Если вокруг есть заминированные, то нужно подсчитать их количество, если вокруг мин нет, то нужно также открыть все соседние клетки.
- * Дана шахматная доска, на которой есть несколько черных шашек и одна белая. Напишите программу, для определения максимального количества черных шашек, которые можно съесть за один ход.