РЕКУРСИЯ

Существует целый класс задач, в которых отношения между объектами можно определить, только пользуясь самими определяемыми соотношениями. Получающиеся при этом правила называются рекурсивными.

Пример:

рекурсивное определение натурального числа:

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) и попытке согласовать его с правилом «факт». Это приводит к бесконечному процессу рекурсии с отрицательными аргументами в «факт», которая завершается при исчерпании глубины зарезервированных интерпретатором Пролога стеков.

Содержание Назад Вперед

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий