Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (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)
Иностранный язык (62792)
Информатика (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)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Рекурсия
Раздел: Рефераты по кибернетике
Тип: реферат Добавлен 06:26:17 29 августа 2005 Похожие работы
Просмотров: 358 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Содержание

Рекурсия . . . . . . . . . . . . . . . . . . . . . . . . . . 2

Пример 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 2

Пример 2 . . . . . . . . . . . . . . . . . . . . . . . . . . 3

Пример 3 . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Пример 4 . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Пример 5 . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Реку рсия.

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

procedure proc(i:integer);

begin

anweisungen1;

if bedingung then proc(i+1);

anweisungen2;

end;

Вызов proc(1) означает, что proc вызывает себя раз за разом с помощью proc(2), proc(3),.. до тех пор, пока условие bedingung не отменит новый вызов. При каждом вызове выполняется оператор anweisungen 1, после чего порядок выполнения операторов прерывается новым вызовом proc(i+1). Чтобы для каждого вызова был отработан и оператор anweisungen2, все локальные переменные процедуры сохраняются в стеке. Стеком является структура магазинного типа LIFO (Last In First Out), т.е. если, например, при proc(10) условие более не выполняется, anweisungen2 выполняется со значениями, обрабатываемыми в обратном порядке для 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(‘<RET>’:60); read(c,c);

end;

end;

end.

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

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

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

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



Результаты(151445)
Комментарии (1844)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru