Рекурсия

Рекурсия

Содержание

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

. . . . . . 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 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 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.