Возможности получения рекурсии
Нет готовых рецептов, как для данной произвольной проблемы получить (рекурсивный) алгоритм ее решения. Однако есть некоторые рекомендации.
1) органически рекурсивные определения
Некоторые рекурсивные функции являются точным "слепком" с соответствующего определения (вспомните определение факториала числа).
2) извлечение рекурсии из постановки задачи
В большинстве случаев, однако, решаемая задача не является алгоритмически сформулированной. Поэтому пытаются прийти к (рекурсивному) алгоритму, сводя общую задачу к "более простым" задачам того же рода. Иногда непосредственной ясно, как это сделать, но чаще всего требуется интуиция.
Пример 6. Определение операции сложения двух чисел через рекурсивные отношения.
В силу законов ассоциативности и коммуникативности имеем:
a+b=a+b+1-1=(a+1)+(b-1)
Поэтому операцию сложения можно ввести так:
function plus (a, b: integer): integer;
begin
if b=0 then plus := a
else
if b>0 then plus := plus (succ(a), pred(b))
else plus := plus (pred(a), succ(b));
end;
Если ограничиться сложением натуральных чисел, то третья ветвь отпадает.
3) вложение
Если не удается извлечь рекурсию из самой постановки задачи, то часто оказывается полезным обобщить задачу (например, введя дополнительные параметры). Подходящее обобщение позволяет усмотреть возможность рекурсии, а, возвращаясь к частному случаю, мы получаем алгоритм для первоначальной задачи.
Пример 7. Классический пример использования применения такого приема вложения дал Маккарти в 1962 г. Исходная задача звучала следующим образом: "Установи, является ли заданное положительное натуральное число n простым". При этом предполагалось, что известно определение простого числа: натуральное число называется простым, если оно больше единицы и не делится ни на одно число, большее или равное двум и меньшее этого числа.
Удачным обобщением будет такая задача (в которой вводится дополнительный параметр): "Установи, верно ли, что заданное натуральное число не делится ни на одно число, большее или равное m и меньшее этого числа".
4) метод родственных задач
При использовании этого метода к задаче "прибавляют" одну или несколько задач таким образом, чтобы функции из возникающей системы опирались друг на друга.
Пример 8. Определить, содержит ли последовательность знаков m четное число знаков. При этом справедливо утверждение: число знаков в последовательности четно тогда и только тогда, когда все знаки могут быть сгруппированы в пары.
Введем родственную задачу: Определить, содержит ли последовательность знаков m нечетное число знаков.
Обнаруживается взаимосвязь двух задач: непустая последовательность знаков содержит нечетное число знаков, только если после удаления одного знака она содержит четное число знаков, и наоборот.
Формы рекурсивных процедур
В общем случае любая рекурсивная Rec включает в себя некоторое множество операторов S и один или несколько операторов рекурсивного вызова P.
Безусловные рекурсивные процедуры приводят к бесконечным процессам. На эту проблему нужно обратить особое внимание, т.к. практическое использование процедур с бесконечным самовызовом невозможно (поскольку надо выделять дополнительную область памяти, а бесконечной памяти ре существует). Отсюда вытекает главное требование к рекурсивным процедурам.
Следовательно, главное требование к рекурсивным процедурам заключается в том, что вызов рекурсивных процедур должен выполняться по условию, которое на каком-то уровне рекурсии станет ложным.
Если условие истинно, то рекурсивный спуск продолжается. Когда оно ложно, то спуск заканчивается и начинается поочередный рекурсивный возврат из всех вызванных на данный момент копий рекурсивной процедуры.
Структура рекурсивных процедур может принимать три различные формы:
-
форма с выполнением действий до рекурсивного вызова (с выполнением действий на рекурсивном спуске) - вложенная рекурсия
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 Rec; begin S1; Rec; S2; end; end; |
Рассмотрим исполнителя Червяка, который умеет ходить по клеткам поля на указанное число клеток, разворачиваться на 90º по часовой стрелке и оставлять за собой след (помечать посещенные ячейки).
Что останется на поле после прохода Червяка согласно представленным ниже алгоритмам (a=10)?
spiral1 (a)
begin
если a<1 то стоп
вперед a
поворот
spiral1 (a-1)
end
spiral2 (a)
begin
е
сли
a<1
то стоп
spiral1 (a-1)
вперед a
поворот
end
При вызове первой процедуры мы увидим "закручивающуюся" спираль, а при вызове второй — спираль будет "раскручиваться".
Все формы рекурсивных процедур находят применение на практике. Многие задачи, в том числе n!, безразличны к тому, какая используется форма рекурсивной процедуры.
Однако есть классы задач, при решении которых программисту требуется сознательно управлять ходом работы рекурсивных процедур и функций. Такими являются задачи, в частности, использующиеся списковые и древовидные структуры данных.
Например, при разработке трансляторов широко применяются, так называемые атрибутированные деревья разбора, работа с которыми требует от программиста умения сознательно направлять ход рекурсии: одни действия могут выполняться только на спуске, а другие - только на возврате.