теория алгоритмов. Разработка программ с использованием рекурсивных функций Цель работы познакомиться с понятием "рекурсия" и особенностями рекурсивных процедур и функций языка программирования Pascal,
 Скачать 58.66 Kb.
|
|
Лабораторная работа № 1 Тема: Разработка программ с использованием рекурсивных функций Цель работы: познакомиться с понятием "рекурсия" и особенностями рекурсивных процедур и функций языка программирования Pascal, закрепить практические навыки работы с системой TURBO Pascal на примере реализации алгоритмов при помощи рекурсивных процедур и функций. Задача работы: освоить способы программирования алгоритмов с использованием рекурсии. 1. Теоретическая часть Рекурсия – способ организации вычислительного процесса, при котором подпрограмма в ходе выполнения составляющих ее операторов обращается сама к себе. Имеется два вида рекурсии: 1. прямая рекурсия означает, что процедура вызывает саму себя; 2. косвенная рекурсия означает, что одна процедура вызывает другую процедуру, а это в свою очередь прямо или косвенно приводит к вызову первоначальной процедуры. Рекурсию следует использовать только тогда, когда задача легко поддается рекурсивному решению. Любая задача, которая может быть решена рекурсивно, также может быть решена и без рекурсии. Перед выполнением работы необходимо изучить способы описания и использования рекурсивных процедур и функций. 1. Прямая рекурсия Функция Function (n-формальные параметры): ; Begin := (n-1); End; Процедура Procedure (n-формальные параметры); Begin (n-1); End; 2. Косвенная рекурсия До вызова процедура или функция должна быть обязательно описана, для этого используется опережающее объявление: процедура или функция содержит описание только своего заголовка, вслед за которым ставится зарезервированное слово forward. Var : ; Procedure (n-формальные параметры); forward; Procedure (n-формальные параметры); Begin (n-1); End; Procedure (n-формальные параметры); Begin (n-1); End; 2. Отчет о выполнении Отчет выполняется в электронном виде. Если заданий несколько, то повторить всю систему отчета необходимое количество раз.
Спецификация программы
Листинг алгоритма исполняемого файла
Скриншот интерфейса запускного файла программы
4. Контрольные вопросы: 1. Что понимается под структурным программированием? Структурное программирование – это технология создания программ, позволяющая путем соблюдения определенных правил уменьшить время разработки и количество ошибок, а также облегчить возможность модификации программы. В основу структурного программирования положены следующие достаточно простые положения: алгоритм и программа должны составляться поэтапно (по шагам). сложная задача должна разбиваться на достаточно простые части, каждая из которых имеет один вход и один выход. логика алгоритма и программы должна опираться на минимальное число достаточно простых базовых управляющих структур. 2. Что называется подпрограммой? Алгоритм, выполняющий некоторую относительно автономную, законченную часть основной задачи, называют вспомогательным алгоритмом, а соответствующую “вспомогательную программу” — подпрограммой (или процедурой). Во многих языках программирования процедура оформляется так же или почти так же, как головная программа. Их используют ,если один и тот же алгоритм используется несколько раз по ходу решения задачи. Одна и та же подпрограмма может обрабатывать различные данные, переданные ей в качестве аргументов. Это не просто выделенный кусок кода — для этого куска кода определены входные и выходные параметры, а от прочих данных он, в идеале, изолирован. на практике подпрограммами гораздо чаще пользуются, чтобы упростить процесс разработки программы. По мере, программы стали создаваться методом последовательных уточнений. На каждом этапе программист разбивает задачу на некоторое число подзадач. Таким образом, подпрограммы — это реализация в языке программирования основного и вспомогательных алгоритмов, на которые, как правило, распадается решение общей задачи в процедурном программировании. 3. Что такое «рекурсия»? Рекурсия – это определение объекта через обращение к самому себе. Рекурсивный алгоритм – это алгоритм, в описании которого прямо или косвенно содержится обращение к самому себе. В технике процедурного программирования данное понятие распространяется на функцию, которая реализует решение отдельного блока задачи посредством вызова из своего тела других функций, в том числе и себя самой. 4. Как объявляется рекурсивная подпрограмма? Рекурсия – это такой способ организации вычислительного процесса, при котором процедура или функция в ходе выполнения составляющих ее операторов обращается сама к себе. Типичная рекурсивная процедура имеет вид: procedure Rec (n:Integer); begin <действие на входе рекурсию> if <проверка условия> then Rec(n-1); <действия на выходе из рекурсии>; end; 5. В чем преимущества и недостатки использования рекурсии? Рекурсия имеет три основных преимущества: Может выражать алгоритмы, которые нельзя удобно выразить никаким другим образом. Логически проще метода итерации. Она широко используется в обработке списков. Рекурсия - хороший способ для описания задач, содержащих в себе подзадачу такого же типа. Недостатки рекурсии: Занимает много места в стеке по сравнению с итеративной программой Использует больше процессорного времени Отладка может быть более сложной по сравнению с эквивалентной итеративной программой 6. Какие виды рекурсий бывают и в чем их особенность Рекурсия это такой способ организации вычислительного процесса, при котором подпрограмма в ходе выполнения составляющих ее операторов обращается сама к себе. Рекурсия бывает: прямой и косвенной. Прямая – процедура обращается сама к себе Косвенная - вызов процедуры может содержаться в теле другой процедуры, к которой производится обращение Прямая – процедура обращается сама к себе { factorial n! - rekurcia} Var s:longint; n: word; function f (n:word): longint; begin if (n=1) or (n=0) then f:=1 else f:=n*f(n-1); end; Косвенная -вызов процедуры может содержаться в теле другой процедуры, к которой производится обращение из данной процедуры. Procedure A(i : Byte); begin В(i); end; Procedure В(j: Byte); begin A(j); end; |
