Шаг 103.
Формы рекурсивных процедур

    На этом шаге мы рассмотрим различные формы рекурсивных процедур.

    В общем случае любая рекурсивная процедура Rec включает в некоторое множество операторов S и один или несколько операторов рекурсивного вызова.

    Как было показано на предыдущем шаге, безусловные рекурсивные процедуры приводят к бесконечным процессам, и на эту проблему нужно обратить особое внимание, так как практическое использование процедур с бесконечным самовызовом невозможно. Такая невозможность вытекает из того, что для каждой копии рекурсивной процедуры необходимо выделить дополнительную область памяти, а бесконечной памяти не существует.

    Следовательно, главное требование к рекурсивным процедурам заключается в том, что вызов рекурсивной процедуры должен выполняться по условию, которое на каком-то уровне рекурсии станет ложным.

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

    Структура рекурсивной процедуры может принимать три разных формы:

1. Форма с выполнением действий до рекурсивного вызова (с выполнением действий на рекурсивном спуске):

   procedure Rec; 
   begin
     S;
     If <условие>  then Rec; 
   end;
   

2. Форма с выполнением действий после рекурсивного вызова (с выполнением действий на рекурсивном возврате):

   procedure Rec; 
   begin
     if <условие> then Rec;
     S; 
   end;
   

3. Форма с выполнением действий как до, так и после рекурсивного вызова (с выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате):

   procedure Rec;
   begin
     S1;
     if <условие> then Rec;
     S2;
   end;
   

   или

   procedure Rec; 
   begin
     if <условие> then 
     begin 
       S1; 
       Rec; 
       S2; 
     end; 
   end;
   

    Все формы рекурсивных процедур находят применение на практике. Многие задачи, в том числе вычисление факториала, безразличны к тому, какая используется форма рекурсивной процедуры. Однако есть классы задач, при решении которых программисту требуется сознательно управлять ходом работы рекурсивных процедур и функций. Такими в частности являются задачи, использующие списковые и древовидные структуры данных. Например, при разработке трансляторов широко применяются, так называемые, атрибутированные деревья разбора, работа с которыми требует от программиста умения сознательно направлять ход рекурсии: одни действия можно выполнить только на спуске, а другие - только на возврате. Поэтому глубокое понимание рекурсивного механизма, и умение управлять им по собственному желанию, является необходимым качеством квалифицированного программиста.

    Первые две формы рекурсивных подпрограмм рассмотрим на примере вычисления факториала (n!), третью форму - на примере реверсивной печати вводимой строки.

    На следующем шаге мы рассмотрим выполнение действий на рекурсивном спуске.

Предыдущий шаг Содержание Следующий шаг