АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. II. ОПИСАНИЕ МАССОВОЙ ДУШИ У ЛЕБОНА
  2. XI. Описание заболевания
  3. Анализ основных конкурентов (схема и описание)
  4. Античное историческое сознание и историописание
  5. Античное историческое сознание и историописание – с. 74-75
  6. Библиографическое описание
  7. Библиографическое описание как форма свертывания информации
  8. Вопрос1 Кинематическое описание движения материальной точки
  9. Вопрос№3 Виды механического движения, графическое описание, харакеристики.
  10. Графическое описание алгоритма
  11. Жизнеописание Павличенки, Матвея Родионыча
  12. ЗАДАНИЕ 4 ПРАВОПИСАНИЕ ПРИСТАВОК

 

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

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

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

Пример 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 (см. пример 5) на EXTENDED, программа перестанет работать уже при N = 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. Теперь в процедуре А можно использовать обращение к процедуре В - ведь она уже описана, точнее, известны ее формальные параметры, и компилятор может правильным образом организовать ее вызов. Обратите внимание: тело процедуры В начинается заголовком, в котором уже не указываются описанные ранее формальные параметры.

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.)