- •Программирование на языке паскаль Учебное пособие
- •1. Общая характеристика языков программирования
- •1.1. Языки программирования
- •1.2. Трансляторы
- •1.3. История создания языков
- •1.4. Базовые структуры языков программирования
- •Контрольные вопросы
- •2. Описание языка паскаль
- •2.1. Основные объекты языка
- •2.2. Структура Паскаль-программы
- •2.3. Типизация данных
- •2.4. Объявление данных
- •Контрольные вопросы
- •3. Простые операторы. Ввод/вывод данных
- •3.1. Оператор присваивания и выражения
- •3.2. Операторы вызова процедур. Ввод/вывод данных
- •3.2.1. Процедуры ввода read и readln
- •Общая форма записи оператора
- •3.2.2. Процедуры вывода write и writeln
- •Контрольные вопросы
- •Каково назначение процедуры writeln без параметров? Задания для самостоятельной работы
- •Варианты заданий
- •Дополнительные задания
- •4. Структурные операторы. Организация ветвлений и циклов
- •4.1. Составной и пустой операторы
- •4.2. Организация ветвлений. Операторы выбора
- •4.2.1. Оператор ветвления if
- •4.2.2. Оператор варианта case
- •Общая форма записи
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •Варианты заданий
- •Дополнительные задания
- •4.3. Организация циклов. Операторы повторения
- •4.3.1. Оператор while
- •4.3.2. Оператор repeat
- •4.3.3. Оператор for
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •Варианты заданий
- •5. Организация подпрограмм. Процедуры и функции
- •5.1. Процедуры и их типизация
- •5.1.1. Встроенные процедуры
- •5.1.2. Процедуры пользователя
- •5.1.3. Процедуры без параметров
- •5.1.4. Фактические и формальные параметры
- •5.1.5. Локальные и глобальные переменные
- •5.1.6. Процедуры с параметрами-значениями
- •5.1.7. Процедуры с параметрами-переменными
- •5.1.8. Комбинированные процедуры
- •5.2. Функции пользователя. Рекурсивные функции
- •5.2.1. Определение функции
- •О бщая форма записи заголовка функции
- •5.2.2. Функции пользователя
- •5.2.3. Рекурсивные функции
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •Варианты заданий
- •Дополнительные задания
- •6. Массивы. Данные типа array
- •Одномерные массивы
- •Общая форма записи
- •Общая форма записи
- •6.2. Многомерные массивы
- •6.3. Способы работы с массивами
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •Варианты заданий
- •Дополнительные задания
- •Обработка литерных величин. Данные типа char и string
- •7.1. Тип данных char
- •Работа программы
- •7.2. Массивы литер
- •7.3. Тип данных string
- •7.4. Строковые функции и процедуры
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •Варианты заданий
- •Дополнительные задания
- •8. Множества. Данные типа set
- •О бщий вид регулярного типа
- •8.1. Определение типа set
- •8.2. Операции над множествами
- •8.2.1. Принадлежность множеству
- •8.2.2. Сравнение множеств
- •8.2.3. Действия над множествами
- •8.3. Вывод множеств
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •Варианты заданий
- •9. Комбинированный тип. Данные типа record
- •9.1. Оператор типа record
- •9.2. Оператор with
- •9.3. Записи с вариантами
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •Варианты заданий
- •10. Файловый тип
- •10.1. Определение и описание типизированного файла
- •Общая форма записи
- •10.2. Типы файлов. Процедура работы с файлами
- •10.3. Основные приемы работы с файлами
- •10.4. Текстовые файлы
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •Типизированные файлы
- •Текстовые файлы
- •Программирование графики
- •Основные понятия компьютерной графики
- •Формирование изображения на экране
- •Инициализация графического режима
- •Простейшие графические операторы (процедуры)
- •Основные приемы работы с графикой
- •Работа с цветом
- •Заполнение (закрашивание) произвольной замкнутой фигуры
- •Построение простейших геометрических фигур
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •Варианты заданий
- •Библиографический список
5.2.3. Рекурсивные функции
К функциям можно обращаться тремя способами: из тела основной программы, из тела другой функции, из тела самой функции, т.е. функция может вызывать саму себя. Функции называются рекурсивными, если в описании функции происходит вызов самой себя, а процесс обращения – рекурсией. Продемонстрируем использование рекурсии на примере вычисления значения факториала произвольного натурального числа N.
В математике известно рекурсивное определение факториала:
n! = 1 при n = 0;
n! = (n - 1)! n при n > 0.
Это рекурсивное определение можно реализовать с помощью соответствующей рекурсивной функции:
function FACTORIAL (VALUE: integer): integer;
begin
iF VALUE = 0 then FACTORIAL := 1
else FACTORIAL := VALUE*FACTORIAL (VALUE - 1)
end;
Теперь можно обращаться к этой функции в теле основной программы, как показано в следующем примере:
program FINDFACTORIAL;
var N: integer;
begin
writeln ('Введите число');
readln (N);
if N < 0 then writeln ('Нет факториала')
else writeln ('Факториал ', N, ' равен ', FACTORIAL (N))
end.
Мы видим, что характерной особенностью построенной функции является наличие в ее теле оператора присваивания:
FACTORIAL := VALUE*FACTORIAL (VALUE - 1),
где происходит вызов определяемой функции. Здесь идентификатор FACTORIAL в левой части оператора обозначает имя переменной для хранения значения функции, а в правой – имя вызываемой функции.
Важным моментом при составлении любой рекурсивной функции является организация выхода из рекурсии. В некоторых простых случаях должно существовать не рекурсивное решение. Рекурсивный процесс должен шаг за шагом так упрощать задачу, чтобы, в конце концов, для нее появилось не рекурсивное решение. В этих функциях должны проверяться значения аргумента для принятия решения о завершении. В нашем случае условием завершения рекурсии является VALUE = 0.
При описании рекурсивных функций необходимо хорошо представлять процесс вычислений. Всякая рекурсия состоит из двух этапов: углубления (погружения) внутрь рекурсии и выхода из нее. На первом этапе никаких вычислений не производится, а идет только настройка рабочей формулы на конкретные операнды. На втором этапе происходит процесс вычислений по настроенным формулам.
Рассмотрим рекурсивный процесс на примере вычисления факториала для N = 3. Получим следующие шаги:
N = 3, где N <> 0. Тогда FACTORIAL := 3*FACTORIAL (2);
N = 2, где N <> 0. Тогда FACTORIAL := 2*FACTORIAL (1);
N = 1, где N <> 0. Тогда FACTORIAL := 1*FACTORIAL (0);
N = 0, следовательно, FACTORIAL := 1,
т.е. получили не рекурсивное значение. Углубление в рекурсию закончено, далее пойдет процесс выхода из нее с выполнением необходимых вычислений.
В выражение 1*FACTORIAL (0) вместо FACTORIAL (0) подставляется его значение 1, вычисляется произведение 1*1, которое становится значением FACTORIAL (1). В выражение 2*FACTORIAL (1) вместо FACTORIAL (1) подставляется значение 1, вычисляется 2*1 и становится значением FACTORIAL (2). В выражение 3*FACTORIAL (2) вместо FACTORIAL (2) подставляется значение 2, вычисляется 3*2 и становится значением переменной FACTORIAL, которая возвращает в основную программу значение 3!.
Весь этот двухэтапный рекурсивный процесс реализуется в памяти ЭВМ с помощью организации в ней стека рекурсии. Дело в том, что для хранения значений переменной N (а значит и переменной VALUE) отводится не одна ячейка, а стек с именем N. В этот стек последовательно заносятся значения 3, 2, 1, 0, причем значение 0 есть признак конца заполнения стека. Затем начинает работать цикл с телом FACTORIAL := FACTORIAL*N, где значения N выбираются последовательно из стека в порядке 1, 2, 3. Исходным же значением переменной FACTORIAL является единица, являющаяся значением 0!.
Работа стека представлена в таблице:
Заполнение стека (углубление) |
Стек № |
Вычисление (разуглубление) |
FACTORIAL := 1 |
0 |
FACTORIAL := 1 |
FACTORIAL := 1*FACTORIAL (0) |
1 |
FACTORIAL := 1*FACTORIAL |
FACTORIAL := 2*FACTORIAL (1) |
2 |
FACTORIAL := 2*FACTORIAL |
FACTORIAL := 3*FACTORIAL (2) |
3 |
FACTORIAL := 3*FACTORIAL |
В заключение покажем, что часто рекурсивные функции строятся гораздо проще, чем «обычные», хотя вполне понятно, что не всякая функция может быть переделана на рекурсивную. Сделаем это на примере уже построенной ранее функции POWER.
Данная функция явно носит рекурсивный характер, исходя из ее определения:
Xn = 1, если n = 0;
Xn = Xn-1 * X, если n > 1.
Ниже следует рекурсивная функция вычисления значения степени:
function POWER (FACTOR: real; EXPONENT: integer): REAL;
begin
if EXPONENT < 0
then POWER := 1/POWER (FACTOR, abs (EXPONENT))
else
if EXPONENT > 0
then POWER := FACTOR*POWER (FACTOR, EXPONENT - 1)
else POWER := 1
end;
Замечание. Помимо рекурсивных функций, в языке Паскаль по тому же принципу можно определять и рекурсивные процедуры. Подробно о них будет сказано в следующих разделах, а пока покажем, как рекурсивная функция может быть переделана в рекурсивную процедуру на примере вычисления факториала:
procedure FACTORIAL (VALUE: integer; var F: integer);
begin
iF VALUE = 0 then F := 1
else begin FACTORIAL (VALUE - 1, F);
F := F*VALUE
end;
end;
Здесь уже, в отличие от функции FACTORIAL, для вычисления N! необходимо вызвать эту процедуру с помощью оператора процедуры FACTORIAL (N, FN), где FN – переменная для возвращения из процедуры значения N!.