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

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

Безусловные рекурсивные процедуры приводят к бесконечным процессам. На эту проблему нужно обратить особое внимание, т.к. практическое использование процедур с бесконечным самовызовом невозможно (поскольку надо выделять дополнительную область памяти, а бесконечной памяти ре существует). Отсюда вытекает главное требование к рекурсивным процедурам.

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

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

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

1. форма с выполнением действий до рекурсивного вызова (с выполнением действий на рекурсивном спуске) - вложенная рекурсия

procedure Rec;

begin

S;

if условие then Rec;

end;

2. форма с выполнением действий после рекурсивного вызова (с выполнением действий на рекурсивном возврате) - хвостовая рекурсия

procedure Rec;

begin

if условие then Rec;

S;

end;

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

Рассмотрим исполнителя Червяка, который умеет ходить по клеткам поля на указанное число клеток, разворачиваться на 90º по часовой стрелке и оставлять за собой след (помечать посещенные ячейки).

Что останется на поле после прохода Червяка согласно представленным ниже алгоритмам (a=10)?

spiral1 (a)

begin

если a<1 то стоп

вперед a

поворот

spiral1 (a-1)

end

spiral2 (a)

begin

если a<1 то стоп

spiral1 (a-1)

вперед a

поворот

end

При вызове первой процедуры мы увидим "закручивающуюся" спираль, а при вызове второй — спираль будет "раскручиваться".

Все формы рекурсивных процедур находят применение на практике. Многие задачи, в том числе n!, безразличны к тому, какая используется форма рекурсивной процедуры.

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

Например,при разработке трансляторов широко применяются, так называемые атрибутированные деревья разбора, работа с которыми требует от программиста умения сознательно направлять ход рекурсии: одни действия могут выполняться только на спуске, а другие - только на возврате.