Иллюстрированный самоучитель по Турбо Паскалю
Рекурсия и опережающее описание
Рекурсия - это такой способ организации вычислительного процесса, при котором
подпрограмма в ходе выполнения составляющих ее операторов обращается сама к
себе.
Рассмотрим классический пример - вычисление факториала (пример 18). Программа
вводит с клавиатуры целое число N и выводит на экран значение
N!, которое
вычисляется с помощью рекурсивной функции РАС. Для выхода из программы
необходимо либо ввести достаточно большое целое число, чтобы вызвать
переполнение при умножении чисел с плавающей запятой, либо нажать
Ctrl-Z и Enter.
При выполнении правильно организованной рекурсивной подпрограммы осуществляется многократный переход от некоторого текущего уровня организации
алгоритма к нижнему уровню последовательно до тех пор, пока, наконец, не будет получено
тривиальное решение поставленной задачи. В примере 8.5 решение при N = 0
тривиально и используется для остановки рекурсии.
Пример 8.5
Program Factorial;
{$S+} {Включаем контроль переполнения стека}
var
n: Integer;
Function Facfn: Integer): Real;
{Рекурсивная функция, вычисляющая n ! }
begin
{Fac}
if n < 0 then
WriteLn ('Ошибка в задании N')
else
if n = 0 then
Fac := 1
else Fac := n * Fac(n-l)
end {Fac} ;
{---------------}
begin {main} repeat
ReadLn (n) ;
WriteLn ('n!= ',Fac(n))
until EOF
end {main} .
Рекурсивная форма организации алгоритма обычно выглядит изящнее итерационной
и дает более компактный текст программы, но при выполнении, как правило,
медленнее и может вызвать переполнение стека (при каждом входе в подпрограмму ее
локальные переменные размещаются в особым образом организованной области памяти,
называемой программным стеком). Переполнение стека особенно ощутимо сказывается
при работе с сопроцессором: если программа использует арифметический
сопроцессор, результат любой вещественной функции возвращается через аппаратный
стек сопроцессора, рассчитанный всего на 8 уровней. Если, например, попытаться
заменить тип REAL функции FAC (см. пример 8.5) на EXTENDED, программа перестанет
работать уже при N = 8. Чтобы избежать переполнения стека сопроцессора, следует
размещать промежуточные результаты во вспомогательной переменной. Вот правильный
вариант примера 8.5 для работы с типом EXTENDED:
Program Factorial;
{$S+,N+,E+} {Включаем контроль Стека и работу сопроцессора}
var
n: Integer;
Function Fac(n: Integer): extended;
var
F: extended; {Буферная переменная
для разгрузки стека сопроцессора}
{Рекурсивная функция, вычисляющая п! }
begin {Рас}
if n < 0 then
WriteLn ('Ошибка в задании N') else
if n = 0 then
Fac := 1 else begin
F := Fac(n-l) ; Fac := F * n end end {Fac} ;
{--------------}
begin {main}
repeat
ReadLn (n) ;
WriteLn ('n! = ',Fac(n))
until EOF
end {main} .
Рекурсивный вызов может быть косвенным. В этом случае подпрограмма обращается
к себе опосредованно, путем вызова другой подпрограммы, в которой содержится
обращение к первой, например:
Procedure A (i : Byte) ;
begin
.......
В (i);
.......
end ;
Procedure В (j : Byte) ;
.......
begin
.......
A(j);
.......
end;
Если строго следовать правилу, согласно которому каждый идентификатор перед
употреблением должен быть описан, то такую программную конструкцию использовать
нельзя. Для того, чтобы такого рода вызовы стали возможны, вводится опережающее
описание:
Procedure В(j : Byte); forward;
Procedure A(i : Byte);
begin
.......
В (i) ;
.......
end ;
Procedure В;
begin
.......
A(j);
.......
end;
Как видим, опережающее описание заключается в том, что объявляется лишь
заголовок процедуры В, а ее тело заменяется стандартной директивой FORWARD.
Теперь в процедуре А можно использовать обращение к процедуре В - ведь она уже
описана, точнее, известны ее формальные параметры, и компилятор может правильным
образом организовать ее вызов. Обратите внимание: тело процедуры В начинается
заголовком, в котором уже не указываются описанные ранее формальные параметры.