Главная | Обратная связь | Поможем написать вашу работу!

Порядок выполнения работы

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.

Следует учитывать, что использование рекурсивной формы организации алгоритма обычно выглядит изящнее итерационной и дает более компактный текст программы, но при выполнении, как правило, медленнее и может вызвать переполнение стека. Это объясняется тем, что при каждом входе в подпрограмму ее локальные переменные размещаются в особым образом организованной области памяти, называемой программным стеком.

⇐ Предыдущая 14 15 16 17 181920 21 22 23 Следующая ⇒