Главная / Рефераты / Рефераты по кибернетике
Реферат: Рекурсия
Notice: Undefined variable: ref_img in /home/area7ru/area7.ru/docs/referat.php on line 323
Содержание
Рекурсия
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 представляет собой бесконечную рекурсию, с помощью которой можно установить, насколько велик стек. При этом помните, что при использовании директивы (*+*) при переполнении стека получим сообщение об ошибке; а при использовании директивы (*-*) – нет, а значит, мы скорее всего столкнемся с зависанием системы. Установкой по умолчанию является (*+*). Программа будет прервана с выдачей сообщения об ошибке «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 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.
Этот пример демонстрирует прежде всего различия между итерац...
ВНИМАНИЕ!
Текст просматриваемого вами реферата (доклада, курсовой) урезан на треть (33%)!
Чтобы просматривать этот и другие рефераты полностью, авторизуйтесь на сайте:
|
|
|
Добавлено: 2010.10.21
Просмотров: 1542
|
Notice: Undefined offset: 1 in /home/area7ru/area7.ru/docs/linkmanager/links.php on line 21
При использовании материалов сайта, активная ссылка на AREA7.RU обязательная! |
