Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Министерство образования и науки РФ.
Федеральное агентство по образованию.
Томский Государственный Университет Систем Управления и
Радиоэлектроники.
ТУСУР.
Кафедра компьютерных систем в управлении и проектировании.
КСУП.
Отчет по лабораторной работе № 8
“Рекурсия ”
Выполнил: студент группы №514
______________________
Проверил: ассистент кафедры КСУП
______________________
ТОМСК – 2005г.
Содержание
1. Введение____________________________________________________________ стр.
2.Основная часть:
а)условие задачи №2______________________________________________ стр.
б)описание переменных____________________________________________ стр.
в)пошаговое описание алгоритма___________________________________ стр.
г)блок-схема______________________________________________________ стр.
д)программа с комментариями_____________________________________ стр.
е) условие задачи №14______________________________________________ стр.
ж) описание переменных___________________________________________ стр.
з) пошаговое описание алгоритма____________________________________ стр.
и) блок-схема (осн. Программа)______________________________________ стр.
к) )блок-схема (процедура и функция)________________________________ стр.
к) программа с комментариями_____________________________________ стр.
3.Вывод_______________________________________________________________ стр.
Введение.
Объект называется рекурсивным, если он содержит сам себя или определен с помощью самого себя. Рекурсия встречается не только в математике, но и в обыденной жизни. Каждый сталкивается с рекурсией, когда стоит с зеркальцем перед большим зеркалом. Рекурсия встречается обычно и в природе: деревья имеют рекурсивное строение (ветки образуются из других веток), реки образуются из впадающих в них рек. Клетки делятся рекурсивно. Продолжение жизни связано с рекурсивным процессом. Молекулы ДНК и вирусы размножаются, копируя себя, живые существа имеют потомство, которое в свою очередь, тоже имеет потомство и т. д. Рекурсия распространена и в языке, и в поведении так же, как и в способах рассуждения и познания. Рекурсия в языке, например, может быть в структуре или в содержании:
_Петя сказал, что Вася сказал, что..._
_Знаю, что знаю, но не помню_
_Сделать; заставить сделать; заставить, чтобы заставили сделать;..._
_Замени x этим предложением_
_Запомни и передай это сообщение_
. . .
Литературным примером может служить "рассказ в рассказе", как-то: известное стихотворение "У попа была собака,..." , роман Яна Потоцкого "Рукопись, найденная в Сарагосе", рассказ Хулио Кортасара _Непрерывность парков_ или рассказ Виктора Пелевина _Водонапорная башня_ (и по форме - состоит из одного предложения и по содержанию). Музыкальные формы и действия также могут быть рекурсивными во многих отношениях (например, канон, в котором мелодия сопровождается той же мелодией с задержкой, и другие). Целенаправленное поведение и решение проблем так же являются рекурсивными процессами.
Рекурсия в программировании - один из важнейших принципов построения подпрограмм. Если процедура P содержит явное обращение к самой себе, то она называется прямо рекурсивной; если P содержит обращение к процедуре Q , которая содержит (прямо или косвенно) обращение к P, то P называется косвенно рекурсивной. Поэтому использование рекурсии не всегда сразу видно из текста программы. С процедурой принято связывать некоторое множество локальных объектов, т. е. переменных, констант, типов и процедур, которые определены локально в этой процедуре, а вне ее не существуют или не имеют смысла. Каждый раз, когда такая процедура рекурсивно вызывается, для нее создается новое множество локальных переменных. Хотя они имеют те же имена, что и соответствующие элементы множества локальных переменных, созданного при предыдущем обращении к этой же процедуре, их значения различны. Следующие правила области действия идентификаторов позволяют исключить какой-либо конфликт при использовании имен: идентификаторы всегда ссылаются на множество переменных, созданное последним. То же правило относится к параметрам процедуры. Подобно операторам цикла, рекурсивные процедуры могут приводить к бесконечным вычислениям. Поэтому для того, чтобы работа процедуры когда-либо завершилась, необходимо, чтобы рекурсивное обращение к процедуре подчинялось некоторому логическому условию, которое в какой-то момент перестает выполняться.
Задача № 2. Напечатать в обратном порядке заданную строку.
Описание переменных:
Пошаговое описание:
Шаг №1 Вводим строку;
Шаг №2 Вводим входные параметры равные длине строки n.
Шаг №3 Если порядковое значение выражения S(n) равно длине строки, то переходим к шагу 5, в противном случае выводим символ на экран.;
Шаг №4 Присваиваем n значение равное n-1 и переходим к шагу 3.
Шаг №5 Конец программы.
Текст программы с комментариями
program lab_8_2;
uses CRT;
var n : byte; {Определение типов переменных}
s : string;
Procedure ShowStr(n : byte);
Begin
If ord(s[n]) = length(s) then exit else write(s[n]);{сравнение порядкового значения с длиной строки(если не равны,то вывод, в противном случае выход)}
ShowStr(n - 1){Вызов процедуры для n-1}
End;
BEGIN
ClrScr;
Readln(s);{Ввод строки}
ShowStr(length(s));{Вызов процедуры с входным параметром равный длине строки}
ReadKey;
END.{Конец программы}
Результаты работы программы:
1234567890
0987654321
Задача №14 Рекурсивная программа. Дана последовательность ненулевых целых чисел, за которой следует 0. Напечатать сначала все отрицательные числа этой последовательности, а затем все положительные (в любом порядке).
Описание переменных:
1)Глобальные
а) m – определяем тип mas, т.к. это массив чисел, считываемый из файла;
б) i – определяем тип byte, т.к. это количество элементов массива;
Описание процедур:
POL – выводит все положительные числа массива.
OTR – выводит все отрицательные числа массива.
Пошаговое описание алгоритма:
Шаг№1 Ввод массива;
Шаг№2 Вывод отрицательных чисел;
Шаг№3 Вывод положительных чисел.
Шаг№4 Конец программы.
Текст программы с комментариями
Program lab_8_14;
Uses Crt;
type mas=array [1..255] of integer;{Задание нового типа переменных}
Var m:mas;{Описание переменных}
i:byte;
Procedure Pol(n:byte);
Begin
If n=0 then exit else If m[n]>0 then write(' ',m[n]);{Если n равно 0, то выход, если нет, то если n-ый член больше 0 выводим его на экран}
Pol(n-1);{Вызов процедуры для n-1}
End;
Procedure Otr(n:byte);
Begin
If n=0 then exit else If m[n]<0 then write(' ',m[n]);{Если n равно 0, то выход, если нет, то если n-ый член меньше 0 выводим его на экран}
Otr(n-1);{Вызов процедуры для n-1}
End;
BEGIN
ClrScr;
Writeln('Введите числа :');
i:=0; { Ввод
While true do
Begin
Inc(i);
Readln(m[i]);
If m[i]=0 then break; массива }
End;
Pol(i-1);{Вызов процедуры для I-1}
Writeln;
Otr(i-1);{Вызов процедуры для I-1}
ReadKey;
END.{Конец программы}
Результаты работы программы:
Введите числа:
-1
1
-2
2
-3
3
0
-3 –2 –1
3 2 1
Вывод
С помощью этой лабораторной работы мы ознакомились с рекурсией. С помощью рекурсии значительно сокращается текс программы, но есть возможность переполнения стека, для этого необходимо создавать какое- то условие для не зацикливания этой процедуры или функции.