Обобщение правил рекурсии
В общем случае рекурсивное правило может иметь вид:
<условие выхода по успеху>, (0)
<рекурсивное правило> : -
<список предикатов>, (1)
<предикат условия выхода>, (2)
<список предикатов>, (3)
<рекурсивное правило>, (4)
<список предикатов>, (5)
(1), (3) и (5) - предикаты не связанные с рекурсией.
(2) - условие выхода по неуспеху.
Все действия связанные с остатками хранятся в стеке.
Пример:
Пусть необходимо сгенерировать натуральные числа от 1 до 7.
Domains
Number:=integer
Predicates
Write
number (number)
Goal
nl ,
write_number (1),
nl , write
(“Конец”).
Clauses ( условие выхода )
Write
number (8).
Write_number(Number):-
Number<8,
Write(Number),nl,
Next_Number
= Number+1,
Write_number(Next_number).
До тех пор, пока аргумент с начальным значением 1 не достигнет 8, его значение выводится на экран, увеличивается на 1 и производится рекурсивный вызов со следующим значением. Условие выхода из рекурсии в данном случае находится в первой клаузе, когда она сопоставляется, генерация чисел прекращается, т.е. здесь выход из рекурсии по успеху.
Пример:
Суммирование чисел от 1 до 7 методом нисходящей рекурсии.
Domains
Number,sum=
integer
Predicates
Sum.ser(number,sum)
Goal
Sum.ser(7,sum),
Write(“сумма ряда S(7)=”,sum),nl.
Clauses
Sum_ser(1,1).
Sum_ser(Number,Sum):-
Number>0,
Next_Number=Number-1,
Sum_ser(Next_Number,Part_sum),
Sum= Number+Part_Sum,
Подразумевается, что первый аргумент предиката суммирования последовательности, есть верхний предел, а второй аргумент - сумма ряда.
При рекурсивных вызовах, первый аргумент уменьшается на 1, значение суммы (второго аргумента) не определено. Формула для его вычисления содержит также неопределенную переменную частичной суммы. Вычисление суммы не может быть произведено, т.к. оно стоит после рекурсивного вызова и содержит неопределенную переменную. Процесс будет продолжаться до тех пор, пока N=2, Nn=1, при этом будет вызов Sum.ser(1,part_sum)
1-я клауза сопоставляется, происходит означивание переменной частичной суммы как 1, вычисляется начальное значение суммы как 2+1. Начинается сворачивание рекурсии с привлечением из стека недоделанных операций по вычислению суммы.