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