Рекурсивные подпрограммы

4. Приведем несколько примеров для иллюстрации рекурсии.

1. Рекурсивная процедура печати двоичного представления натурального числа:

procedure Rec(n: integer);
begin
if n > 1 then Rec(n div 2)
Write(n mod 2);
end;
2. Рекурсивная функция вычисления факториала натурального числа. Напомним, что факториал – это произведение натуральных чисел от единицы до какого-либо данного натурального числа n, то есть 1⋅2⋅ … ⋅(n-1)⋅n, обозначается n!
function Factorial(n: integer):longint;
begin
if n = 1 then Factorial:= 1
else Factorial:= n* Factorial(n-1);
end;
3. Рекурсивная функция возведения целого числа x в целую неотрицательную степень n выглядит следующим образом:
function Deg(x, n: integer):longint;
begin
if n = 0 then Deg:=1
else
if n mod 2=0 then
Deg:=Deg(x*x, n div 2)*x;
else
Deg:=Deg(x, n-1)*x;
end;
Рекурсивный вызов может быть косвенным (косвенная рекурсия). В этом случае подпрограмма обращается к себе опосредованно, путем вызова другой подпрограммы, в которой содержится обращение к первой. Примером использования косвенной рекурсии может послужить пример приведенный выше для пояснения использования директивы forward. В данном примере процедура с именем А вызывает процедуру с именем В, а процедура В, в свою очередь, вызывает процедуру А.
Пример показывающий использование рекурсивного алгоритма для создания сложного симметричного рисунка.

Требуется написать программу, рисующую снежинку, показанную на рисунке.
Входные данные: входных данных нет.
Выходные данные: рисунок снежинки.
Решение. Рисунок представляет собой десятиконечную снежинку, каждый конец которой, в свою очередь, представляет собой множество подобных десятиконечных снежинок, уменьшающихся в размере по направлению к центру.
Рекурсивная процедура, рисующая такую снежинку, зависит от трех параметров (трех чисел, однозначно характеризующих изображаемую фигуру): координаты центра x, y и радиуса r.
Снежинка с радиусом r ≤ 1 на экране монитора не будет отличаться от пикселя, отсюда следует условие выхода из рекурсивной процедуры: если r ≤ 1, то рисуется лишь одна точка с координатами (x, y), и процедура завершается.
В противном случае (r > 1) в процедуре изображаются десять ветвей снежинки в цикле по углу с шагом 36°, начиная с крайней удаленной снежинки, радиусом в 5 раз меньшим начального радиуса (размера).
Внутри этого цикла рисуется собственно сама ветвь (от края к центру), которая состоит опять же из восьми подобных снежинок, причем радиус очередной снежинки уменьшается по мере приближения к центру исходной снежинки в 1,5 раза.
Для того чтобы нарисовать всю снежинку целиком, из основной программы достаточно вызвать эту процедуру один раз, передав в качестве параметров координаты центра экрана и радиуса исходной снежинки.
Листинг 4. Рисование снежинки
program p4;
uses Graph;
const Step=Pi*0.2;
var Driver, Mode:integer;
procedure DrowStar(x,y,Size:Integer);
{x,y – координаты центра и Size – радиус снежинки}
var i,j, NewSize, xNew,yNew:Integer;
begin
if Size<1 then PutPixel(x,y,white)
else
{Первый цикл – по количеству направляющих снежинки}
for i:=0 to 9 do
begin
newsize:=size;
{второй цикл – рисование 8-ми подуровней снежинки}
for j:=1 to 8 do
begin
xnew:=x+Round(newsize*cos(i*Step));
ynew:=y+Round(newsize*sin(i*Step));
DrowStar(xnew,ynew,newsize div 5);
newsize:=newsize*2 div 3;
end;
end;
end;
{основная программа}
begin
{задаем вид графического оборудования. Драйвер
Vga в режиме VgaHi дает разрешение экрана 640×480 точек}
Driver:=Vga; Mode:=VgaHi;
{инициализация графического режима}
InitGraph(Driver,Mode,'C:\BP\BGI');
{вызов рекурсивной процедуры}
DrowStar(320,240,120);
{320=GetMaxX/2; 240=GetMaxY/2}
Readln;
CloseGraph
end.