Вход

Рекурсия

Реферат по информатике и информационным технологиям
Дата добавления: 23 июля 2008
Язык реферата: Русский
Word, rtf, 95 кб (архив zip, 15 кб)
Реферат можно скачать бесплатно
Скачать
Не подходит данная работа?
Вы можете заказать написание любой учебной работы на любую тему.
Заказать новую работу

Содержание


Рекурсия . . . . . . . . . . . . . . . . . . . . . . . . . . 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(‘’:60); read(c,c);

end;

end;

end.








12



© Рефератбанк, 2002 - 2017