Формы рекурсивных процедур

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

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

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

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

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

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

  • Форма с выполнением действий до рекурсивного вызова (с выполнением действий на рекурсивном спуске):
    procedure Rec; 
    begin
      S;
      If <условие>  then Rec; 
    end;
    
  • Форма с выполнением действий после рекурсивного вызова (с выполнением действий на рекурсивном возврате):
    procedure Rec; 
    begin
      if <условие> then Rec;
      S; 
    end;
    
  • Форма с выполнением действий как до, так и после рекурсивного вызова (с выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате):
    procedure Rec;
    begin
      S1;
      if <условие> then Rec;
      S2;
    end;
    

    или

    procedure Rec; 
    begin
      if <условие> then 
      begin 
        S1; 
        Rec; 
        S2; 
      end; 
    end;
    
  •    
    Все формы рекурсивных процедур находят применение на практике. Многие задачи, в том числе вычисление факториала, безразличны к тому,
    какая используется форма рекурсивной процедуры. Однако есть классы задач, при решении которых программисту требуется сознательно управлять ходом
    работы рекурсивных процедур и функций. Такими в частности являются задачи, использующие списковые и древовидные структуры данных. Например, при
    разработке трансляторов широко применяются, так называемые, атрибутированные деревья разбора, работа с которыми требует от программиста умения сознательно
    направлять ход рекурсии: одни действия можно выполнить только на спуске, а другие - только на возврате. Поэтому глубокое понимание рекурсивного механизма, и умение
    управлять им по собственному желанию, является необходимым качеством квалифицированного программиста.

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

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



    Вы можете оставить комментарий, или Трекбэк с вашего сайта.

    Оставить комментарий