Каталог :: Кибернетика

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

Содержание
     Рекурсия         .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
                         .  .  .  .  .  .  . 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.