Repeat:– repeat.

Дата добавления: 2015-09-15; просмотров: 688; Нарушение авторских прав

Следует отметить, что в языке Пролог рекурсия является одним из основных методов управления программой. В общем случае рекурсивное определение содержит следующие группы предикатов: 1) предикаты, определяющие нормальный выход из рекурсии, их успешное или безуспешное выполнение не приводит к рекурсивным обращениям; 2) предикаты, работающие на входе в рекурсию, в случае отказа осуществляется прекращение рекурсии; 3) непосредственно рекурсивное обращение; 4) предикаты, не оказывающие непосредственного влияния на рекурсию, в процессе рекурсивных обращений они «выталкиваются» в стек и выполняются лишь по завершении рекурсии. Следует обратить внимание на условие выхода из рекурсии. Рекурсивное правило всегда должно содержать этот предикат. Рассмотрим использование рекурсивных определений на примере вычисления n!:

factorial(N, 1):– N<=1, !.	Условие выхода из рекурсии
factorial(N, S):–	Рекурсивное правило
N1= N-1,	Предикат, успешное выполнение которого приводит к рекурсии, а отказ– к выходу
factorial(N1, S1),	Рекурсивное обращение
S= S1*N.	Предикат, выполняющийся на выходе из рекурсии

Протокол поиска ответа на вопрос

?– factorial(5, S).

factorial(5, S)	Вход в первый виток рекурсии.
N1₁= 5-1		N1₁= 4
factorial(4, S1₁)	Вход во второй виток рекурсии
N1₂= 4-1		N1₂= 3
factorial(3, S1₂)	Вход в третий виток рекурсии
N1₃= 3-1		N1₃= 2
factorial(2, S1₃)	Вход в четвертый виток рекурсии
N1₄= 2-1		N1₄= 1
factorial(1, S1₄)	Обращение к нерекурсивному правилу	S1₄= 1
S1₃= 1*2	Выход из четвертого витка рекурсии	S1₃= 2
S1₂= 2*3	Выход из третьего витка рекурсии	S1₂= 6
S1₁= 6*4	Выход из второго витка рекурсии	S1₁= 24
S= 24*5	Выход из первого витка рекурсии	S= 120
Yes

Контрольные вопросы

1 Что называется подстановкой?

2 Назовите правила сопоставления переменных.

3 Что такое механизм отката?

4 В чем состоит алгоритм унификации?

5 Что такое отсечение?

<== предыдущая лекция	\|	следующая лекция ==>
BMW–320	\|	Рекурсивные структуры данных