Иллюстрированный самоучитель по Tirbo Pascal


Рекурсия и опережающее описание


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

Рассмотрим классический пример - вычисление факториала (пример 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:




Начало  Назад  Вперед



Книжный магазин