Вторник, 23.10.2018, 02:32
Приветствую Вас, Гость |
Меню сайта
Наш опрос
Нужен ли форум на этом сайте?
Всего ответов: 1182
Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0

Рекурсия в паскале


        В математике, да и не только в ней одной, часто встречаются объекты, определяемые при помощи самих себя. Они называются
рекурсивными.Например, рекурсивно определяется функция факториал:

   0! =1,

   n! = n*(n-1)!    для любого натурального n.

        В паскале рекурсивной называется подпрограмма, исполнение которой приводит к ее же повторному вызову.Если подпрограмма просто вызывает сама
себя, то такая рекурсия называется прямой.

Например:
    procedure rec1(k: byte);
    begin
       ...
       rec1(k+1);
       ...
    end;
    function rec2(k: byte):byte;
       begin
       ...
       x:=rec2(k+1);
       ...
    end;


Структура подпрограммы на паскале с прямой рекурсией:
Т.о., сначала в каждой активации подпрограммы выполняются
  1.      операторы, расположенные до рекурсивного вызова,
  2.      затем (при достижении условия выхода) – нерекурсивная часть очередной активации,
  3.      а затем – операторы, записанные после рекурсивного вызова.
На этом построены многие рекурсивные алгоритмы.

Ограничение глубины рекурсии

Теоретически, рекурсия может быть бесконечной. Однако такой вариант вряд ли кого-нибудь устроит:
рекурсивный алгоритм, как и любой нерекурсивный его собрат, обязан выдавать результат своей работы за некое обозримое время.
Кроме того, память у компьютера не резиновая, в ней может поместиться лишь конечное число контекстов одновременно открытых экземпляров
рекурсивной подпрограммы.
Следовательно, каждая рекурсивная подпрограмма должна содержать в себе признак окончания – своеобразный "забор", определяющий максимальную
глубину вложенности для этой рекурсии.
Признак конца рекурсии может быть как явным (например, в случае реализации факториала), так и неявным (в частности, описанная ниже процедура
razlozh рано или поздно обязательно закончится, поскольку на каждом шаге происходит уменьшение разлагаемого натурального числа).

Рекурсивные подпрограммы
Если несколько подпрограмм вызывают друг друга, но эти вызовы "замкнуты в кольцо", то такая рекурсия называется косвенной.В случае косвенной
рекурсии возникает проблема с описанием подпрограмм:

 по правилу языка Паскаль, нельзя использовать никакой объект раньше, чем он был описан.

Следовательно, невозможно написать в программе:
   procedure rec_А(k: byte);
   begin 
      ...
      reс_В(k+1); 
      ...
    end;

   procedure rec_В(k: byte);
   begin
      ...
      rec_А(k+1); 
      ...
   end;


И здесь полезной оказывается возможность отрывать объявление подпрограммы от ее описания (см. Тему 6).
Например, для косвенной рекурсии в случае двух процедур, вызывающих друг друга (rec_A ® rec_B ® rec_A), нужно такое описание:
(косвенная рекурсия в паскале)
   procedure rec_А(k: byte);forward;
   procedure rec_В(k: byte);
   begin 
      ...
      reс_А(k+1);
      ...
    end;
    procedure rec_A;
    begin 
       ...
       rec_В(k+1); 
       ...
    end;


 
Форма входа
Поиск
Мы в сети
Реклама
Для того чтобы не видеть рекламу в правом верхнем углу сайта пройдите простую процедуру регистрации
ФОРУМ
У нас наконецто появился форум! Добро пожаловать! Будьте первыми, задайте направление форуму! =)
--- Не стесняемся - заходим на форум! ---