Реферат: Рекурсия - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

Рекурсия

Банк рефератов / Информатика, информационные технологии

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 16 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

6 Содержание Рекурсия . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Пример 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Пример 2 . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Пример 3 . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Пример 4 . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Пример 5 . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Реку рсия. Рекурсией называется ситуация, когда процедура или функция сама с ебя вызывает. Вот типичная конструкция такого рода: procedure proc ( i : integer ); begin anweisungen 1; if bedingung then proc(i+1); anweisungen 2; end ; Вызов proc (1) означает, что proc вызывает себя раз за разом с помощью proc (2), proc (3),.. до тех пор, пока условие bedingung не отменит новый вызов. При каждом выз ове выполняется оператор anweisungen 1, после чего порядок выполнения операторов прерывается новы м вызовом proc ( i +1). Чтобы для каждого вызова был отра ботан и оператор anweisungen 2, все локальные переменные процедуры сохраняются в стеке. Стеком является ст руктура магазинного типа LIFO ( Last In First Out ), т.е. если, например, при proc (10) условие более не выполняется, anweisungen 2 выполняется со значениями, обра батываемыми в обратном порядке для proc (9),…, proc (1). Локальные параметры помещаются в стек один за другим и выби раются из стека в обратной последовательности (латинское recurrere означает «возвр ащение назад»). В Паскале можно пользоваться именами лишь тогда, когда в тексте програм мы этому предшествует их описание. Рекурсия является единственным искл ючением из этого правила. Имя proc можно использовать сразу же, не закончив его описания. Пример1 представляет собой бесконечную рекурсию, с пом ощью которой можно установить, насколько велик стек. При этом помните, чт о при использовании директивы (* $ S +*) при переполнении стека получим сообще ние об ошибке ; а при использовании директивы (* $ S -*) – нет, а значит, мы скорее всего столкнемся с зависанием системы. Установкой по умолчанию является (* $ S +*). Программа будет прервана с выдачей сообщения об ошибке « Error 202: stack overflow error (“ Ошибка 202: переполнение стека» ). Пример1: Program stack _ test ; программа проверки стека procedure proc(i:integer); begin if i mod 1024 = 0 then writeln(i:6); proc(i+1); end ; begin proc (1); end . Стек связан с другой структурой памяти – с динамическ ой областью. С помощью директивы (* $ М*) можно управлять размером стека. Рекурсия не должна восприниматься как некий программистский трюк. Это скорее некий принцип, метод. Если в программе нужно выполнить что-то повт орно, можно действовать двумя способами: - с помощью последовательного присоединения (или итерации в форме цикла) ; - с помощью вложения одной опе рации в другую (а именно, рекурсий). В следующем примере2 один раз счет от 1 до n ведется с помощью цикла, а второй – с помощью рекурсии. При э том хорошо видно, как заполняется, а затем освобождается стек. В процедур е rekursion операция writeln(i:30) выполняется перед рекурсивным вызо вом, после чего writeln(i:3) освобождает стек. Поскольку рекурсия выполняется от n до 1, вывод по команде writeln(i:30) выполняется в обратной последовательности n,n-1,…,1, а вывод по команде writeln(i:3) – в прямой п оследовательности 1,2,…,n (согласно принципу LIFO – последним пришел, первым обслужен). Пример2: Показывает принципиальное различие между итерацией и рекурсией: итерации необходим цикл и локальная переменная k как переменная цикла. Рекурсии ничего э того не требуется! program iterativ_zu_rekursion; var n:integer; procedure rekursion (i:integer); begin writeln(i:30); if i < 1 then rekursion(i-1); writeln(i:3); end; (* Рекурсия * ) procedure schleife(i:integer); var k:integer; bagin k :=1; while k <= i do begin write(k:3); k :=k+1; end; end; (* Цикл * ) begin write(‘ Введите n:’ ); readln(n); writeln(‘ Пока: ’ ); scheife(n); writeln; writeln(‘ Рекурсия ’ ); rekursion(n); end. Пример3: Рекурсивная процедура convert пер еводит десятичное число z в вос ьмеричную систему путем деления его на 8 и выдачи остатка в обратной посл едовательности. Program dezimal_oktal_konvertierung; преобразование из десятичной системы в восьмеричну ю var z:integer; procedure convert(z:integer); begin if z > 1 then convert(z div 8); ( * Это рекурсивный вызов * ) write(z mod 8:1); end; begin writeln(‘ Введите некоторое положительное число: ’ ); readln(z); writeln(‘ Десятичное число: ’ ,z:6); write(‘ Восьмеричное число: ’ ); convert(z); end. Один из наиболее ярких примеров применения рекурсии д ают числа Фибоначчи. Они определяются следующим образом: x[1]=x[2]=1 x[n]=x[n-1]+x[n-2] при n > 2 Каждый элемент ряда Фибоначчи является суммой двух пр едшествующих элементов, т.е. 1 1 2 3 5 8 13 21 34 55 … Следующий пример позволяет вычислить n -ный элемент ряда Фибоначчи как итеративно (то есть в цикле, начи ная с х [1] до х[n] ), так и рекурсивно ( n- ный элемент ряда является сум мой двух предшествующих элементов). Причем рекурсивная функция вызывае т себя дважды. Пример4: С использованием рекурсии вычисляются числа Фибоначчи, причем глубина рекурсии индицируется. Перед каждым рекурсивным вызовом выводится выв одиться ASCII -символ с номером 8 ( Backspace), а после вызова вновь стирае тся. Тем самым можно наблюдать за работой программы, поскольку программа за счет delay(300) приостанавливаетс я на 0.3 с. program fibonacci(input, output); uses crt; var n,result:integer; function fibit(n:integer):integer; var a,b,c,i:integer; begin a := 1; b := 1; if (n=1) or (n=2) then fibit :=1 else begin for i= 3 to n do begin c :=a+b; a := b; b :=c; end; fibit :=c; end; end; begin clrscr; write(‘ n = ‘ ); readln(n); writeln(‘ Итеративно: ’ ,fibit(n):5); writeln(‘ рекурсивно: ’ ); write(‘ ….!….#….!….#….’ ); writeln(‘ !….#….!….#….!….#’ ); write (‘ Глубина рекурсии: ’ ); result := fibrek(n); writeln; write(result); end. Этот пример демонстрирует прежде всего различия между итерацией и рекурсией. Итерации необходим цикл и вспомогательные велич ины ; итерация сравнительно не наглядна (см. fibit в приведенном в ыше примере). Рекурсия обходится без вспомогательных величин и обычно пр още для понимания, что демонстрирует следующая запись: if (n=1) or (n=2) then fibrek := 1 else fibrek := fibrek(n-1)+fibrek(n-2); Итерация требует меньше места в памяти и машинного вре мени, чем рекурсия, которой необходимы затраты на управление стеком. Ита к, если для некоторой задачи возможны два решения, предпочтение следует отдать итерации. Правда, для многих задач рекурсивная формулировка сове ршенно прозрачна, в то время как построение итерации оказывается весьма сложным делом. Если процедура или функция вызывает себя сама, это называют прямой реку рсией. Но может встретиться ситуация, когда процедура А вызывает процеду ру В, вызывающую С, а процедура С вновь возвращается к А. В этом случаи мы им еем дело дело с косвенной рекурсией, что демонстрирует приведенный ниже пример. С таким типом рекурсии мы сталкиваемся там, где использована дир ектива forward. Пример 5: Следующая программа выдает простые числа от 1 до n , для чего используются функции next и prim, которые вызываются перекрестно, то есть рекурсив но. Одновременно это является примером применения директивы forward. program primzahlen_rekursiv_berechnen; программа рекурсивного вычисления простых чисел var n,i : integer; c : char; function next(i:integer):integer;forward; Это прямая ссылка вперед на функцию next, которая будет оп ределена позже function prim(j:integer):boolean; prim имеет значение true, если j простое число, и false в противном случае var k:integer; begin k :=2; while (k*k <= j) and (j mod k < > 0) do k :=next(k); k пробегает последовательность простых чисел, начиная с 2, вплоть до корня из j, при этом проверяется, делит ся ли j на одно из таких простых чисел. При этом используется следующая функция next if j mod k = 0 then prim := false else prim := true; end prim ; function next; Параметры уже стоят в ссылке вперед, next вычисляет, каково следующ ее за j простое число var i:integer; begin 1 :=i+1; while not(prim(1)) do 1 :=1+1; Итак, next вызы вает в свою очередь prim next :=1; end next ; begin (******* Исполняемая часть программы *******) write(‘ Введите положительное ч исло n,’ ); writeln(‘ Должны быть определены все ’ ); writeln(‘ предшествующие ему простые числа ’ ); readln(n); for i :=2 to n do begin if prim(i) then writeln(i:14) else writeln(i:4); if i mod 23 = 0 then begin write(‘ ’ :60); read(c,c); end; end; end.
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
- Люська, а давай мы с тобой в семью поиграем!?
- А как?
- Сначала переспим, а потом характерами не сойдёмся.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по информатике и информационным технологиям "Рекурсия", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru