 |
|
Порядок выполнения работы
1. Изучить теоретические сведения по теме: “Написание программы на Паскале с использованием процедур, определенных пользователем”.
2. Получить индивидуальное задание у преподавателя и разработать программу в соответствии с поставленной задачей.
3. Показать работающую программу преподавателю.
4. Ответить на контрольные вопросы.
Контрольные вопросы
1. Описание процедуры. Общая структура.
2. Формальные, фактические параметры.
3. Параметры – значения, параметры – переменные.
4. Примеры программ с использованием процедур, определенных пользователем.
Лабораторная работа № 16
Написание программы на Паскале с использованием рекурсии
Цель работы: формирование знаний и умений по работе с подпрограммами. Приобретение навыков написания программ с использованием рекурсивных процедур и функций.
Краткие теоретические сведения
Рекурсии
Рекурсия — это такой способ организации вычислительного процесса, при котором процедура или функция в ходе выполнения составляющих ее операторов обращается сама к себе.
Примером программы с использованием рекурсии может быть программа вычисления факториала числа. (Факториалом натурального числа n называют произведение чисел 1*2*...*n.)
{Вычисление факториала числа п с использованием рекурсивной функции}
program Demo_Rekurs;
var
N : integer;
F : longint;
{Описание функции, N — формальный параметр-значение типа integer, результат выполнения функции типа longint}.
function Fakt(N : integer): longint;
begin {Начало вычисления функции}
if N=1 then Fakt:=1 {Проверка условия завершения рекурсии}
else Fakt:=N*Fakt(N-1); {Рекурсивное вычисление N!}
end;
begin {Начало главной программы}
Writeln('Введите число N : ') ;
Read(N) ;
F:=Fakt(N); {Вызов функции для фактического параметра N}
Writeln('Для числа',N,'значение факториала= ', F);
end.
После запуска программы на экран выводится запрос: "Введите число N: ", затем с клавиатуры считывается значение целого числа N и в выражении F:=Fakt(N) вызывается функция Fakt с параметром-значением N. В подпрограмме-функции вычисления факториала проверяется условие N=1. Если оно выполняется, то функции Fakt присваивается значение 1, на этом выполнение подпрограммы-функции завершается. Если условие N=1 не соблюдается, то выполняется вычисление произведения N*Fakt(N-1). Вычисление произведения носит рекурсивный характер, так как при этом осуществляется вызов функции Fakt(N-1), значение которой вычисляется, в свою очередь, через вызов функции Fakt, параметром которой также будет функция Fakt, и т. д., до тех пор, пока значение формального параметра N=1. Так как базовая часть описания рекурсивной функции Fakt определяет значение Fakt для N=1, равным единице, то рекурсивные вызовы функции Fakt больше не выполняются, а наоборот, выполняется вычисление функции Fakt для чисел, возрастающих от 1 до N, причем функция Fakt всякий раз возвращает значение, равное произведению очередного k-гo числа на факториал от k-1-го числа. Последнее возвращение результата вычисления функции Fakt присвоит переменной F значение произведения всех чисел от 1 до N, т. е. факториал числа N.
Вывод. При выполнении рекурсивной подпрограммы осуществляется многократный переход от некоторого текущего уровня организации алгоритма к нижнему уровню последовательно до тех пор, пока, наконец, не будет получено тривиальное решение поставленной задачи. В рассмотренном выше примере решение при N=1 тривиально, т.е. Fakt=l. Затем осуществляется возврат на верхний уровень с последовательным вычислением значения функции Fakt.
Следует учитывать, что использование рекурсивной формы организации алгоритма обычно выглядит изящнее итерационной и дает более компактный текст программы, но при выполнении, как правило, медленнее и может вызвать переполнение стека. Это объясняется тем, что при каждом входе в подпрограмму ее локальные переменные размещаются в особым образом организованной области памяти, называемой программным стеком.