Рекурсия и опережающее описание. Расширенный синтаксис вызова функций.
Рекурсия – это такой способ организации вычислительного процесса, при котором подпрограмма в ходе выполнения составляющих ее операторов обращается сама к себе.
Рассмотрим классический пример – вычисление факториала (пример 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}.