8.4.2. Формы рекурсивных процедур
Главное требование к рекурсивным программам заключается в том, что вызов рекурсивных процедур должен выполняться по условию, которое на каком-то уровне рекурсии станет ложным.
Существуют 3 формы рекурсивных процедур:
форма с выполнением действий до рекурсивного вызова (на рекурсивном спуске):
procedure rec;
b
egin
s :=..;
if <условие> then rec;
end;
форма с выполнением действий после рекурсивного вызова (на рекурсивном возврате):
procedure rec;
b
egin
if <условие> then rec;
s :=..;
end;
форма с выполнением действий как до, так и после рекурсивного вызова (выполнение действий, как в рекурсивном спуске, так и в рекурсивном возврате).
Пример 1.
procedure rec;
b
egin
fl;
if <условие> then rec;
end;
Пример 2.
procedure rec;
b
egin
if <условие> then
begin
fl;
rec;
f2;
end;
end;
Задача 8.8. Составить процедуру вывода на печать символов строки в обратном направлении.
Листинг программы
Uses crt;
Procedure r;
Var
с : char;
Begin
If not eoln then
Begin
Read(c);
R;
Write(c);
End;
End;
Begin
Clrscr;
R;
End.
Задача 8.9 о перевёртывании строки. Составить программу, которая позволяет вводить любой текст, и слово "end" будет прекращать работу программы.
Uses crt;
Type
st = string[20];
Var
s, s1 : st;
Function r (s_t :st): st;
Var
fl : char;
f2:st;
begin
if length (s_t) = 1 then r := s_t;
else
begin
fl := s_t[l];
delete (s_t, 1, 1);
f2:=r(s_t);
r := concat (f2,fl);
end;
end;
begin
clrscr;
repeat
writeln ('введите любой текст');
writeln ('слово "end" прекратит программу');
readln (s);
s1 := г (s);
writeln (s1, ' есть перевёрнутая ', s);
until s = 'end';
end.
8.4.3. Числа Фибоначчи
Первое и второе числа равны 1. Каждое последующее, начиная с третьего, есть сумма двух предшествующих: 1, 1, 2, 3, 5, 8, ...
Листинг программы
Uses crt;
Var
n, i : integer;
A : array [1..100] of integer;
Function fib (n : integer) : integer;
Begin
If (n = 1) and (n = 2) then fib := 1
Else
fib := fib (n- 1 ) + fib (n-2);
End;
Begin
Writeln (‘…’);
Readln (n);
For I := 1 to n do Writeln (Fib (i));
End.
Рекурсивный вызов может быть косвенным. В этом случае подпрограмма обращается к себе опосредованно, путём вызова другой подпрограммы, в которой содержится обращение к первой.
Например:
Procedure A (i : Byte);
Begin
…
B(i);
…
End;
Procedure В (j : Byte);
Begin
…
A(j);
…
End;
Если строго следовать правилу, согласно которому каждый идентификатор перед употреблением должен быть описан, то такую программную конструкцию использовать нельзя. Для того чтобы такого рода вызовы стали возможны, вводится опережающее описание:
Procedure B (j: Byte); forward;
Procedure A (i: Byte);
Begin
…
B(i);
…
End;
Procedure B;
Begin
…
A(j);
…
End;
Итак, опережающее описание заключается в том, что объявляется лишь заголовок процедуры В, а её тело заменяется стандартной директивой FORWARD. Теперь в процедуре А можно использовать обращение к процедуре В - ведь она уже описана, точнее, известны её формальные параметры, и компилятор может правильным образом организовать её вызов. Обратим внимание на то, что тело процедуры В начинается заголовком, в котором уже не указываются описанные ранее формальные параметры.