Рассмотрим построение рекурсивной функции на примере вычисления N!. При правильно организованной рекурсивной подпрограммы осуществляется многократный переход от некоторого текущего уровня организации алгоритма к низшему уровню последовательно до тех пор, пока не будет получено тривиальное решение поставленной задачи.
PROGRAM DEMO1;
USES CRT;
VAR M:BYTE;
FUNCTION FAKT(N:BYTE):LONGINT;
BEGIN
IF N=1 THEN FAKT:=1
ELSE FAKT:=FAKT(N-1)*N;
END;
BEGIN
CLRSCR;
WRITE('N-');READLN(M);
WRITELN('N!=',FAKT(M));
READKEY;
END.
В нашем примере происходит так: в операторе печати вызывается функция FAKT с параметрам N, которая в свою очередь вызывает функцию FAKT с параметрам N-1, и так далее, пока не вызывается FAKT(1). Тогда это процесс останавливается, затем происходить извлечение результата в обратном порядке.
Это хорошо видно на следующем примере программы:
Текст программы:
Результат работы программы:
PROGRAM DEMO2;
USES CRT;
VAR CH: WORD;
PROCEDURE WRITEA;
BEGIN
CH:=CH+1;
WRITELN('НАЧАЛО',CH);
IF CH<4 THEN WRITEA;
WRITELN(' КОНЕЦ',CH);
CH:=CH-1;
END;
BEGIN
CLRSCR;
CH:=0;
WRITEA;
READKEY;
END.
НАЧАЛО 1
НАЧАЛО 2
НАЧАЛО 3
НАЧАЛО 4
КОНЕЦ 4
КОНЕЦ 3
КОНЕЦ 2
КОНЕЦ 1
Рекурсивная форма организации алгоритма обычно выглядит изящнее итерационной и дает более компактный текст программы, но при выполнении, как правили, медленнее и может вызвать переполнение стека.
Стек– это специальная область памяти (конечное число ячеек), где сохраняется адреса возврата (адрес вызывающей программы, используется для передачи управления вызывающей программе). Стеки используются так же для передачи параметров в процедуры (для обычных параметров в стек заносятся их значения, для параметров-переменных – их адреса), размер стек ограничен. Стек можно представить в виде стопки книг. Если стопка достигла максимального размера, то при добавлении новой книги сверху – нижняя книга должна быть убрана.
Нужно обязательно отслеживать в программе наполнение стека, то есть не допускать зацикливания рекурсии.
Рекурсивный вызов может быть косвенным. В этом случае программа обращается к себе опосредованно, путем вызова другой программы, в которой содержится обращение к первой. При использовании такого подхода нужно использовать опережающее описание. Опережающее описание заключается в том, что объявляется лишь заголовок процедуры, а ее тело заменяется директивой FORWARD. После этого можно в другой процедуре использовать обращение к ней – ведь компилятор уже может правильным образом организовать ее вызов. Обратите внимание: тело второй процедуры описывается после первой и начинается заголовком, в котором уже не указываются описанные ранее формальные параметры.
При составлении программ обязательно использовать процедуры или функцию.
· Найти разность двух факториалов F=m! – k!, используя функцию.
Uses crt;
Var F,m,k:integer;
Function Fact(n:integer):integer;
Var P,i:integer;
Begin
P;=1;
For i:=2 to n do
P;=P*i;
Fact:=P;
End;
Begin
Read (M,K);
F:=Fact(m) – Fact(K);
Writeln (‘F=’,F:5);
repeat until keypressed
End.
· Написать программу «Бегущие огни» с использованием процедуры рисования окружности.
uses crt,graph;
var gd,gm,x:integer;
begin
gd:=detect;
initgraph(gd,gm,'');
x:=20;
repeat
repeat
setcolor(4);
circle(x,200,15);
setfillstyle(1,3);
floodfill(x,200,4);
delay(8000);
setcolor(0);
circle(x,200,15);
setfillstyle(1,3);
floodfill(x,200,0);
x:=x+40;
until x>600;
repeat
setcolor(4);
circle(x,200,15);
delay(8000);
setcolor(0);
circle(x,200,15);
x:=x-40;
until x<20;
repeat until keypressed; end.
Примеры программ с использованием рекурсий:
Вычислить Xn:
PROGRAM DEMO3;
USES CRT;
VAR X1,X2: WORD;I,M:BYTE;S:LONGINT;
FUNCTION XN(X,N:BYTE):LONGINT;
BEGIN
IF N=0 THEN XN:=1
ELSE XN:=XN(X,N-1)*X;
END;
BEGIN
CLRSCR;
WRITE('X,N-');READLN(X1,M);
WRITELN('XN-',XN(X1,M));
READKEY;
END.
Подсчитать сумму N чисел Фибоначчи (1,1,2,3,5,8,13,..):
PROGRAM DEMO4;
USES CRT;
VAR X1,X2: WORD;I,M:BYTE;S:LONGINT;
FUNCTION FIB(N:BYTE):LONGINT;
BEGIN
IF N=1 THEN FIB:=1;
IF N=2 THEN FIB:=1;
IF N>=3 THEN FIB:=FIB(N-1)+FIB(N-2);
END;
BEGIN CLRSCR;
WRITE('N-');READLN(M); S:=0;
FOR I:=1 TO M DO
S:=S+FIB(I);
WRITELN('S-',S);
READKEY;
END.
Используя рекурсивную функцию получить подобную фигуру:
1 вариант (простая рекурсивная форма)
PROGRAM DEMO6;
USES CRT,GRAPH;
VAR X,Y: WORD;I,K,M,N:BYTE;
GD,GM:INTEGER;
PROCEDURE LINT(X,Y,N,M:WORD);
BEGIN
LINETO(X+N,Y);
LINETO(X+N,Y+N);
LINETO(X+M,Y+N);
LINETO(X+M,Y+M);
X:=X+M;Y:=Y+M;
N:=N-2*M;
K:=K+1;
IF K<5 THEN LINT(X,Y,N,M);
END;
BEGIN
GD:=DETECT;
INITGRAPH(GD,GM,'');
LINT(0,0,100,10);
READKEY;
END.
2 вариант (рекурсивная форма с опережающим описанием)
PROGRAM DEMO7;
USES CRT,GRAPH;
VAR X,Y: WORD;I,K,M,N:BYTE;
GD,GM:INTEGER;
PROCEDURE LNT(X,Y,N,M:WORD); forward;
PROCEDURE LINT(X,Y,N,M:WORD);
BEGIN
for k:=1 to 5 do begin
lnt(x,y,n,m);
X:=X+M;Y:=Y+M;
N:=N-2*M; end;
END;
procedure lnt;
begin
LINETO(X+N,Y);
LINETO(X+N,Y+N);
LINETO(X+M,Y+N);
LINETO(X+M,Y+M);
end;
BEGIN
GD:=DETECT;
INITGRAPH(GD,GM,'');
LINT(0,0,100,10);
READKEY;
