Вычисление факториала

Для написания рекурсивных алгоритмов необходимо и достаточно наличие понятия процедуры и функции.

Рекурсия - это такой способ организации вычислительного процесса, при котором подпрограмма в ходе выполнения составляющих её операторов обращается сама к себе.

Рассмотрим классический пример — вычисление факториала. Программа вводит с клавиатуры целое число N и выводит на экран значение n!, которое вычисляется с помощью рекурсивной функции Fасt. Для выхода из программы необходимо либо ввести достаточно большое целое число, чтобы вызвать переполнение при умножении чисел с плавающей запятой, либо нажать Ctrl-Z и Enter.

При выполнении правильно организованной рекурсивной подпрограммы осуществляется многократный переход от некоторого текущего уровня организации алгоритма к нижнему уровню последовательно до тех пор, пока, наконец, не будет получено тривиальное решение поставленной задачи. В ниже приведённом примере решение при n=0 тривиально и используется для остановки рекурсии.

Пример 8.3.

Листинг программы

Program Factorial;

{$S+} {Включаем контроль переполнения стека}

var n: integer;

function Fасt (n: integer):real;

{Рекурсивная функция, вычисляющая n!}

begin

if n < 0 then writeln ('Ошибка в задании N')

else

if n = 0 then Fact:= 1

else Fact:= n * Fact (n-1);

end;

begin

repeat

readln (n);

writeln ('n! = ', Fact (n));

until EOF;

end.

Рекурсивная форма организации алгоритма обычно выглядит изящнее итерационной и даёт более компактный текст программы, но при выполнении, как правило, медленнее и может вызвать переполнение стека (при каждом входе в программу её локальные переменные размещаются в особым образом организованной области памяти, называемой программным стеком). Переполнение стека особенно ощутимо сказывается при работе с сопроцессором: если программа использует арифметический сопроцессор, результат любой вещественной функции возвращается через аппаратный стек сопроцессора, рассчитанный всего на 8 уровней. Если, например, попытаться заменить тип real функции Fасt на Extended, программа перестанет работать уже при n = 8. Чтобы избежать переполнения стека сопроцессора, следует размещать промежуточные результаты во вспомогательной переменной. Правильный пример для работы с типом Extended: