Существует целый класс задач, в которых отношения между объектами можно определить, только пользуясь самими определяемыми соотношениями. Получающиеся при этом правила называются рекурсивными. Пример: рекурсивное определение натурального числа: 1) 1- натуральное число; 2) число, на 1 большее натурального числа, также натуральное. В системах логического программирования рекурсия служит также для описания циклов, повторений и является важнейшим методом программирования. Рассмотрим простой пример: вычисление факториала натурального числа n (n!) . Определение n! рекурсивно: 1)1!=1, 2)n!=(n-l)!*n. Для описания отношения «факториал» между n и n! будем использовать двухарный предикат факт(N,М). Тогда база знаний, соединенная с запросом, приобретает вид (программа 115); Программа 115 факт(1,1). факт(N,Х): - факт( N-1 ,V), Х is Y*N. ?- факт(3,А); В данной программе правило «факт» вызывает само себя - это и есть рекурсия. Запись is Y*N представляет собой обращение к встроенному предикату «is» («есть») для описания арифметического действия. Процесс работы программы можно изобразить следующим образом: ?факт(3,A0). ОТВЕТ: А=6 ?факт(1,A2). Х1= 2*3 = 6 факт(1,1) Х2=1*2=2 Здесь стрелочка вниз означает сопоставление и резолюцию, а стрелочка вверх - возврат и завершение отложенного вычисления. Правило «факт» вызывает само себя - происходит углубление рекурсии (прямой ход). При этом в памяти ЭВМ выделяется место для переменных А,АО,А1,А2 и N,NO,N1,N2, образующих стеки. При согласовании вопроса с предикатом факт(1,1) рекурсия прекращается и начинается возврат из рекурсии (обратный ход) - выполнение отложенных на прямом ходе согласований. Предикат факт(1,1) играет очень важную роль - это ограничитель рекурсии, условие ее завершения. Отметим, что Пролог стремится найти все решения поставленной задачи, а значит, после появления ответа А=6 происходит возврат к вопросу ?факт(1,А2) и попытке согласовать его с правилом «факт». Это приводит к бесконечному процессу рекурсии с отрицательными аргументами в «факт», которая завершается при исчерпании глубины зарезервированных интерпретатором Пролога стеков. Ускорить выход из рекурсии можно, добавив к предикату «факт(1,1)» отсечение !: факт(1,1):-!. Однако, использование отсечения требует более подробного рассмотрения. В общем случае последовательность предложений в базе знаний не имеет значения. Однако это не так для рекурсивно-определенных отношений. Например: родитель(Х):- родитель(Y),отец(Y,Z). родитель(коля). отец(коля,петя). родитель(петя). В этом случае в первом предложении голова имеет ту же функцию, что и одна из целей - «родитель». В процессе поиска ответа в этой базе знаний будет применено правило: предложение, стоящее первым, будет применено первым - известное как принцип поиска в глубину. Это приведет к тому, что система будет обращаться только к первому предложению базы знаний и ответ на вопрос не будет найден никогда (образуется бесконечная петля вывода). Однако небольшое изменение базы знаний - перестановка двух предложений местами - приведет к удачному поиску решения. Программа 116 родитель(коля). родитель(X):- родитель(Y), отец(Y,Х). отец(коля,петя). ? - родитель(петя). Неограннчено-повторное обращение к предложению может быть и более замаскированным так, как это получается в программе 117. Программа 117 выше(А,В): - ниже(В,А). ниже(В,А): - выше(А, В). выше(коля,петя). ?- ниже(петя,коля). Однако если третье предложение стоит на первом месте, то повторного обращения не произойдет и ответ будет найден. В общем виде рекурсия на Прологе выглядит так: Р(1,...). P(n,...) -Q1,..., Qn, P(n-l,...), R1,... Rm. Правило Р обращается само к себе, при этом происходит углубление рекурсии. Предикаты Q1, .... Qn выполняются на прямом ходе рекурсии, а R1,..., Rm - на обратном; n - это некоторый условный параметр, входящий в условие продолжения рекурсии, а Р(1,...)- факт, завершающий процесс рекурсии. Особенно простым случаем рекурсии является простое циклическое повторение. Один из способов организации повторения связан с наличием в базе знаний процедуры вида repeat, repeat: - repeat. Использование repeat в качестве подцели некоторого правила приводит к многократному повторению остальных подцелей этого правила.