Задачи по Python с решениями

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

   
В общем случае любая рекурсивная процедура 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!), третью форму - на примере реверсивной печати вводимой строки.

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