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

Содержание

Рекурсия         .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 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):int    {Это прямая ссылка вперед на функцию 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.