Обобщенное правило рекурсии также содержит в теле правила само себя. Рекурсия будет конечной, если в правило включено условие выхода, гарантирующее окончание его работы. Ответственность за обеспечение завершаемости правила рекурсии лежит на программисте.
Тело правила состоит из утверждений и правил, определяющих задачи, которые должны быть выполнены. Ниже в символическом виде дан общий вид правила рекурсии:
<имя правила рекурсии> :-
(1) <список предикатов>,
(2) <предикат условия выхода>,
(3) <список предикатов>,
(4) <имя правила рекурсии>,
(5) <список предикатов>.
Данное правило рекурсии имеет пять компонент. Первая — это группа предикатов. Успех или неудача любого из них на рекурсиию не влияет.
Следующая компонента — предикат условия выхода. Успех или неудача этого предиката либо позволяет продолжить рекурсию, либо вызывает ее остановку. Третья компонента — список других предикатов. Аналогично, успех или неудача этих предикатов на рекурсию не оказывает влияния.
Четвертая группа — само рекурсивное правило. Успех этого правила вызывает рекурсию.
Пятая группа — список предикатов, успех или неудача которых не влияет на рекурсию. Пятая группа может использовать значения, помещенные в стек во время выполнения рекурсии.
Правила, построенные указанным образом, являются обобщенными правилами рекурсии (ОПР), а метод называется ОПР-методом.
Например, вы хотите написать правило генерации всех целых чисел, начиная с 1 и кончая 7. Пусть имя правила будет write_number(Number).
write_number(8).
write_number(Number) :-
Number < 8,
write(Number), nl,
Next_Number = Number + 1,
write_number(Next_number).
Для этого примера первая компонента структуры общего правила рекурсии не используется. Второй компонентой, т.е. предикатом выхода, является Number < 8. Когда значение Number равно 8, правило будет успешным и программа завершится.
Третья компонента правила оперирует с числами. В этой части правила число выдается на экран и затем увеличивается на 1.
Для увеличенного числа будет использоваться новая переменная Next_Number. Четветая компонента — вызов самого правила рекурсии write_number(Next_number). Пятая компонента, представленная в общем случае, здесь не используется.
Программа начинается с попытки вычислить подцель write_number(1). Заметим, что необязательно вызывать правило, используя то же имя переменной, что используется в голове правила. Это всего лишь позиция в списке параметров, имеющая значение при передаче значений. Фактически, если не передавать значение Next_Number, то приращение основного числа программы невозможно. При рекурсивном вызове головы правила, программа снова пытается выполнить подцель write_number(8). Программа продолжает выполнять цикл сопоставления, присвоения и выдачи значений Number до тех пор, пока значение Number не станет равным 8. В этот момент цель выполнена, правило успешно и программа завершается.
Упражнение 5.1.
Измените правило рекурсии write_string так, чтобы результатом программы была семикратная печать строки
Используем правило рекурсии для вычисления суммы ряда целых чисел от 1 до 7:
S(7) = 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28
Правило рекурсии программы выполняет вычисления по обычной схеме сложения:
частичная сумма + следующее значение.
Правило 1 рекурсии имеет вид:
sum_series(1,1). /* сумма1 ряда */
sum_series(Number,Sum) :-
Number > 1,
Next_number = Number — 1,
sum_series(Next_number,Partial_Sum),
Sum = Number + Partial_Sum.
Данное правило имеет четыре компоненты и одно дополнительное нерекурсивное правило. Заметим, что последняя компонента правила рекурсии — это правило Sum с Partial_Sum (частичная сумма) в качестве переменной. Это правило не может быть выполнено до тех пор, пока Partial_Sum не получит некоторого значения.
Программа Сумма1 начинается с попытки выполнить подцель sum_series(7,Sum). Сначала программа пытается сопоставить подцель с подправилом sum_series(1,1). Сопоставление неудачно. Затем она пытается сопоставить подцель с sum_series(Number,Sum). На этот раз сопоставление завершается успешно с присвоением переменной Number значения 7. Затем программа сравнивает значение Number, которое равно 7, с 1 т.е. проверяется условие выхода. Так как 7 больше 1, то сопоставление успешно, программа переходит к следующему подправилу. Для этого подправила переменной Next_number присвоено значение 6, т.е. значение Number — 1. Затем правило вызывает само себя в виде sum_series(6,Partial_Sum). Следующим подправилом является правило Sum, содержащее свободную переменную Partial_Sum. Оно не может быть вызвано до тех пор, пока Partial_Sum не получит значения.
Теперь программа пытается сопоставить факт sum_series(1,1) с sum_series(6,Partial_Sum). Процесс сопоставления неуспешен, поскольку несопоставим ни один из параметров.
В результате программа переходит к следующему правилу с головой sum_series(Number,Sum), присваивая переменной Number значение 6. Этот циклический процесс сопоставления продолжается до тех пор, пока не будет получено sum_series(1,Partial_Sum). Теперь это правило сопоставляется с sum_series(1,1), а Partial_Sum приписывается значение 1. Переменная Sum получает, наконец, значение 3 (1+2).
Во время процесса сопоставления переменная Partial_Sum была свободна, а программа запоминала значения Number для последующего использования. Теперь эти значения извлекаются из стека, а Sum получает последовательно значения 6,10,15,21 и 28. Конечное значение Sum есть 28.
При возвратах, когда цель sum_series(1,Partial_Sum) сопоставится с правилом sum_series(Number,Sum) условие Number > 1 не даст
Next_number получить значение —1, а программе войти в бесконечную рекурсию.
/* Программа 5.1 «Сумма ряда». Назначение:*/
/*демонстрация использования рекурсивного */
/*предиката подсчета суммы S(N) ряда S, */
/* где N положительное целое число */
domains
number, sum = integer
predicates
sum_series(number, sum)
goal
sum_series(7,Sum),
write("Сумма ряда:"),nl,nl,
write(" S(7) = ", Sum), nl.
clauses
sum_series(1,1). /* сумма1 ряда */
sum_series(Number,Sum) :-
Number > 0,
Next_number = Number — 1,
sum_series(Next_number,Partial_Sum),
Sum = Number + Partial_Sum.
/* Конец программы */
Заменим правило sum_series на правило sum_series2. Правило sum_series2 является модификацией правила sum_series. Модификация выполнена посредством удаления условия выхода Number > 1 и введения правила
sum_series2(1,1) :- !.
вместо факта
sum_series(1,1).
Правило sum_series2 рекурсии:
sum_series2(1,1) :- !. /* сумма2 ряда */
sum_series2(Number,Sum) :-
Next_number = Number — 1,
sum_series2(Next_number,Partial_Sum),
Sum = Number + Partial_sum.
Результаты работы этих правил идентичны. Их следует рассматривать как альтернативные варианты. Сразу возникает вопрос: где во втором правиле условие выхода?
