- •1.1. Как начать работу с турбо паскалем
- •1.2. Функциональные клавиши
- •1.3 Текстовый редактор
- •1.4. Основные приемы работы в среде турбо паскаля
- •Глава2. Знакомство с языком турбо паскаля
- •Глава 2 знакомство с языком турбо паскаля
- •2.1. Ваша первая программа
- •2.2. Типы данных
- •2.3. Преобразования типов и действия над ними
- •2.4. Операторы языка
- •2.5. Массивы
- •2.6. Процедуры и функции
- •2.7. Примеры программ
- •Глава3.Элементы языка
- •Глава 3
- •3.1. Алфавит
- •3.2. Идентификаторы
- •3.3. Константы
- •3.4. Выражения
- •3.5. Операции
- •3.6. Структура программы
- •Глава 4. Типы данных
- •4.1. Простые типы
- •4.2. Структурированные типы
- •4.3. Строки
- •4.4. Совместимость и преобразование типов
- •Глава 5. Файлы
- •Глава 5
- •5.1. Доступ к файлам
- •5.2. Процедуры и функции для работы с файлами
- •5.3. Текстовые файлы
- •5.4. Типизированные файлы
- •5.5. Нетипизированные файлы
- •Глава 6. Указатели и динамическая память
- •6.1. Динамическая память
- •6.2. Адреса и указатели
- •6.4. Выделение и освобождение динамической памяти
- •6.5. Использование указателей
- •6.6. Процедуры и функции для работы с динамической памятью
- •6.7. Администратор кучи
- •Глава 7. Типизированные константы
- •7.1. Константы простых типов и типа string
- •7.2. Константы-массивы
- •7.3. Константы-записи
- •7.4. Константы-множества
- •7.5. Константы-указатели
- •Глава 8. Процедуры и функции
- •Глава 8
- •8.1. Локализация имен
- •8.2. Описание подпрограммы
- •8.3. Параметры-массивы и параметры-строки
- •8.4. Процедурные типы. Параметры-функции и параметры-процедуры
- •8.5. Нетипизированные параметры-переменные
- •8.6. Рекурсия и опережающее описание
- •8.7. Расширенный синтаксис вызова функций
- •Глава 9. Модули
- •Глава 9
- •9.1. Структура модулей
- •9.2. Заголовок модуля и связь модулей друг с другом
- •9.3. Интерфейсная часть
- •9.4. Исполняемая часть
- •9.5. Инициирующая часть
- •9.6. Компиляция модулей
- •9.7. Доступ к объявленным в модуле объектам
- •9.8. Стандартные модули
- •Глава 10. Объекты
- •Глава 10
- •10.1. Основные принципы ооп
- •10.2. Постановка учебной задачи
- •10.3. Создание объектов
- •10.4. Использование объектов
- •Глава 11. Другие возможности турбо паскаля
- •Глава 11
- •11.1. Внешние процедуры (функции)
- •11.2. Использование встроенных машинных кодов
- •11.3. Обращение к функциям операционной системы
- •11.4. Поддержка процедур обработки прерываний
- •11.5. Запуск внешних программ
- •11.6. Оверлей
- •11.7. Прямое обращение к памяти и портам ввода-вывода
- •11.8. Длинные строки
- •Глава 12. Встроенный ассемблер
- •Глава 12
- •12.1. Общее описание мп 8086/8088
- •12.2. Специфика встроенного ассемблера
- •Глава 13. Использование библиотеки crt
- •Глава 13
- •13.1. Программирование клавиатуры
- •13.2. Текстовый вывод на экран
- •13.3. Программирование звукового генератора
- •Глава 14. Использование библиотеки graph
- •Глава 14
- •14.1. Переход в графический режим и возврат в текстовый
- •14.2. Координаты, окна, страницы
- •14.3. Линии и точки
- •14.4. Многоугольники
- •14.5. Дуги, окружности, эллипсы
- •14.6. Краски, палитры, заполнения
- •14.7. Сохранение и выдача изображений
- •14.8. Вывод текста
- •14.9. Включение драйвера и шрифтов в тело программы
8.6. Рекурсия и опережающее описание
Рекурсия - это такой способ организации вычислительного процесса, при котором подпрограмма в ходе выполнения составляющих ее операторов обращается сама к себе.
Рассмотрим классический пример - вычисление факториала (пример 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. Теперь в процедуре А можно использовать обращение к процедуре В - ведь она уже описана, точнее, известны ее формальные параметры, и компилятор может правильным образом организовать ее вызов. Обратите внимание: тело процедуры В начинается заголовком, в котором уже не указываются описанные ранее формальные параметры.