Кибернетика

Рекурсия


                                 Содержание

Рекурсия         .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
 .  .  .  .  .  . 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.





смотреть на рефераты похожие на "Рекурсия"