Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364141
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62791)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21692)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8693)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3462)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20644)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Реферат: Рекурсия

Название: Рекурсия
Раздел: Рефераты по информатике, программированию
Тип: реферат Добавлен 05:40:10 05 марта 2004 Похожие работы
Просмотров: 1265 Комментариев: 2 Оценило: 2 человек Средний балл: 4 Оценка: неизвестно     Скачать

.

С понятием рекурсии мы уже встречались: рекуррентные соотношения довольно часто встречаются в математических выражениях. Рекурсия в определении состоит в том, что определяемое понятие определяется через само это понятие. Примером здесь может служить определение высказывания (см. лекция 5, определение 5.1). Рекурсия в вычислениях выступает в форме рекуррентных соотношений, которые показывают, как вычислить очередное значение, используя предыдущие.

Например, рекуррентное соотношение

xi =xi -2 +xi -1 , где x1 =1 , x2 =2

задает правило вычисления так называемых чисел Фибоначчи.

Другим примером рекуррентных соотношений могут служить правила вычисления членов арифметической прогрессии

an +1 =an +d , где d - разность прогрессии,

либо геометрической прогрессии

an +1 =qan , где q - коэффициент прогрессии.

Эта идея рекурсии реализована и в языке Pascal.

Определение 16.1. Функция (процедура) на языке Pascal называется рекурсивной, если в ходе своего выполнения она обращается к самой себе.

Например, мы можем определить вычисление функции n!
рекурсивно. Как это сделать, показано на рисунке 16.1

function Factorial (n : integer) : integer ;

begin if n>0 then Factorial:=Factorial (n-1)*n

else if n=0 then Factorial:=1

elsewriteln (’значение n меньше 0’)

end {Factorial}

Рис. 16.1. Функция вычисления n! в рекурсивной форме.

Рассмотрим подробно, как будет выполняться обращение к этой функции, напрмер, при n=4.

На рисунке 16.2 показан процесс вычисления для случая Factorial(4).

24

Рис. 16.2. Вычисление функции Factorial(n) для n=4.

Сначала образуется так называемый рекурсивный фрейм №1 при n=4. Для этого фрейма отводится память и в нем фиксируются все значения переменных тела функции при n=4. Отметим, что в рекурсивном фрейме фиксируются значения всех переменных функции, кроме глобальных.

Затем происходит вызов Factorial(n) при n=3. Образуется фрейм №2, где фиксируются значения переменных тела функции при n=3. При этом фрейм №1 также хранится в памяти. Из фрейма №2 происходит обращение к Factorial(n) при n=2. В результате этого обращения образуется фрейм №3, где фиксируются значения переменных тела функции при n=2 и т.д. до тех пор, пока при очередном обращении к функции Factorial условие n>0 не примет значение false.

Это произойдет в фрейме №5. В этом фрейме мы получим значение Factorial =1 и передадим это значение в фрейм №4. После этого фрейм №5 будет уничтожен, так как обращение Factorial(n) при n=0 будет выполнено.

В фрейме №4 мы вычислим значение Factorial(n) для n=1. После чего мы передадим это значение во фрейм №3, а фрейм №4 будет закрыт, так как обращение к Factorial(n) при n=1 будет закончено.

Так мы будем сворачивать эту цепочку фреймов в последовательности, обратной той, в которой мы их порождали, пока не свернем фрейм №1. После чего вычисление функции будет окончено.

Рекурсия возможна не только в случае функций, но и процедур. Пример рекурсии для процедур приведен на рисунке 16.3. Там показано описание рекурсивной процедуры для распечатки (вывода на печать) строки символов в порядке, обратном их вводу.

Procedure BackPrint ;

var символ : char ;

begin read (символ) ;

if символ = EOL {EOL - EndOfLine - специальное значение типа

СHAR, соответствующее окончанию ввода}

thenwriteln ( ) ; {пред началом вывода надо убедиться, что

печатать будем с новой строки}

else begin BackPrint ; write (символ) end

end {Procedure}

Рис 16.3. Пример рекурсивной процедуры.

(Косвенная рекурсия.) Итерация и рекурсия.

Нетрудно заметить сходство между циклическими конструкциями (повторениями) и рекурсией. На рисунке 16.4 показана схема цикла вида whiledo и его рекурсивного аналога.

Цикл

Рекурсия

while Условие Цикла

do Тело Цикла

Procedure РекурсивныйЦикл ;

begin

if УсловиеЦикла

then begin ТелоЦикла;

Рекурсивный Цикл

else{окончание рекурсии}

end

Рис. 16.4. Схема организации цикла вида whiledo

и его рекурсивного эквивалента.

Обратите внимание, что в правой части рис. 16.4 возможно зацикливание! Надо быть очень осторожным и всякий раз, применяя рекурсивную поцедуру или функцию, убедиться в их корректном завершении. Рассмотрим пример. На рисунке 16.5 приведен алгоритм Евклида, с которым мы познакомились на лекции 1, для вычисления НОД (наибольшего общего делителя) в форме обычной и рекурсивной функции на языке Pascal.

Function НОД (a, b : integer) : integer ;

begin repeat

if a > b then a:=a-b

else b:=b-a

untile a = b;

НОД:=a

end

begin if a = b then НОД:=a;

if a > b then НОД:=НОД(a-b, b);

else НОД:=НОД(b-a , a);

end

Рис. 16.5. Циклическая и рекурсивная функции

для вычисления НОД.

Как видно из приведенных примеров на рисунках 16.1 и 16.5, итерация, т.е. цикл всегда может быть заменен его рекурсивным аналогом по схеме, показанной на рисунке 16.4.

С обратным утверждением о замене рекурсии итерацией все сложнее. На рисунке 16.6 приведен пример рекурсивной функции, где по схеме (рис. 16.4) рекурсию итерацией заменить не удается.

в остальных случаях

Рис. 16.6. Рекурсивная функция Аккермана.

Способы повторного использования процедур и функций.

Итак, процесс абстракции в форме процедуры состоит из трех шагов:

Именование. Присвоить рутинному алгоритму уникальное имя, которое затем будем использовать как имя соответствующей процедуры.

Определить пред- и постусловия для создаваемой процедуры или функции в соответствии с контекстом их использования в основной программе.

Параметризиовать процедуру. (Везде далее, если явно не оговорено, говоря о процедурах, будем иметь в виду также и функции). Для этого часть предусловия и постусловия в спецификации оформить в виде параметров соответствующего типа, часть из которых будет доставлять исходные данные, а другая часть - результаты работы процедуры.

Обобщить типы параметров. Проанализировать все места в программе, где будет обращение к данной процедуре на предмет, какие типы данных используются в этих местах, как они соотносятся с типами параметров в процедуре. Назовем совокупность типов данных в месте вызова процедуры контекстом обращения к процедуре Определить типы параметров так, чтобы они соответствовали как можно большему числу контекстов обращений к процедуре.

Реализовать получившуюся абстракцию рутинного алгоритма либо в форме процедуры, либо функции.

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

Присоединение. Этот способ предполагает, что если у нас есть процедура P1 c предусловием Q1 и постусловием R1 и процедура P2 c пред-и c постусловиями Q2 и R2 соответственно, (причем R1 ÞQ2 ) , то мы можем построить процедуру Pc предусловием Q1 и постусловием R2 последовательно соеденив Р1 и P2 так, как показано на рис.16.7.

P {Q1 }

{Q1 } Р1 {R1 }

{R1 ÞQ2 }

{Q2 } Р2 {R2 }

{R2 }

Рис. 16.7. Присоединение процедур Р1 и P2 .

Вложение. Этот способ применяется, когда новая процедура P образуется вложением известной процедуры P2 внутрь другой известной процедуры P1 . Вложение возникает либо когда мы явно вставляем P2 как тело цикла или как альтернативу в теле процедуры P1 , либо когда P2 - это параметр для P1 .

Настройка. Суть этого способа состоит в том, что существующую процедуру Р1 мы либо обобщаем, либо, наоборот, сужаем в соответствии со спецификацией Р.

Например, если у нас есть процедура выбора максимального числа из массива из 100 натуральных чисел, то легко ее можем обобщить на случай массива из 1000 целочисленных компонентов.

Слияние. Этот способ построения новой процедуры Р за счет слияния, объединения двух существующих процедур Р1 и P2 .

Например, пусть процедура Р1 выбирает максимальное, а P2 - минимальное значения в массиве из 100 целых чисел. Тогда, объединив операторы процедуры Р1 и процедуры P2 в надлежащем порядке, мы получим процедуру Р , выбирающую max и min из 100 целых чисел.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений21:35:31 18 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
09:40:58 24 ноября 2015

Работы, похожие на Реферат: Рекурсия

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(173751)
Комментарии (1984)
Copyright © 2005-2017 BestReferat.ru bestreferat@gmail.com реклама на сайте

Рейтинг@Mail.ru