3.7. Рекурсивные определения

Как уже отмечалось, рекурсия является одним из средств описания отношений. Недостаток, свойственный рекурсивным определениям, заключается в том, что. в процессе обработки запроса размер стека может расти очень быстро, поскольку предусмотрено сохранение частичных решений. Наиболее часто для иллюстрации рекурсивного отношения используется отношение, позволяющее вычислить факториал числа. Факториал определяется так:

т. е. 4! = 4*3*2*1 = 24. Факториал 1 равен 1. Теперь можно сформировать отношения для вычисления факториала

1 fact 1

TIMES (X*Y)

Для проверки работы правил, описывающих это отношение, можно использовать следующий тест:

all (x: 4 fact x)

[Ответов (больше) нет]

Ниже приведен протокол работы программы^*, получаемый в ответ на запрос:

^* (Этот протокол не снабжается переводом, поскольку, если читатель внимательно изучил предыдущие протоколы трассировок, он без труда разберется и в этом.- Прим. пер.)

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

(1 1): 1 LESS X

No (more) answers

В процессе вычисления N1 отношения LESS и SUM используются для каждого из чисел: N, N-l, N-2, ...2, 1. Результаты сопоставления каждый раз помещаются в стек, хотя в данном случае никаких альтернативных вариантов сопоставления заведомо не существует. N раз используется и отношение TIMES. Результаты его работы также попадают в стек. Ясно, что в процессе вычисления факториала для больших чисел размер стека будет расти очень быстро. Кроме того, значительное время будет тратиться на реализацию возвратов. Таким образом, можно сказать, что для работы с рекурсивными определениями отношений, аналогичными определенному выше, потребуется память, объем которой пропорционален числу обращений к рекурсивному правилу. В данном случае для вычисления факториала потребуется память, объем которой пропорционален N, где N - число, факториал которого определяется.

Отметим, что у читателя может вызвать удивление тот факт, что рядом е условиями (1 1), (2 1), (3 1) и другими после осуществления возврата появляется сообщение: "failing" (неудача), в то время как ранее выполнение этих условий завершалось успешно. Дело в данном случае в том, что при осуществлении возврата Пролог-система старается найти решения, отличные от тех, которые привели к успешному сопоставлению.

На рис. 3.4 показано содержимое стека в процессе вычисления факториала числа 3. Механизм возврата начнет работать именно тогда, когда число элементов в стеке достигнет девяти. Все элементы по очереди будут выталкиваться из стека, поскольку любые попытки поиска альтернативных вариантов обречены на неудачу.

Рис. 3.4. Процесс изменения состояния стека во время вычисления факториала числа 3

Но если стек растет так быстро при вычислении всего-навсего 3!, то размеры его станут поистине гигантскими при определении факториалов больших чисел.

Мы уже рассказывали читателям об отношении "/". Напомним, что оно может использоваться для того, чтобы программа могла считать условия, сопоставление которых прошло успешно, не подлежащими дальнейшей проверке, т. е. для того, чтобы предотвращать возвраты с целью поиска альтернативных вариантов. Такая процедура носит название "выталкивания в случае успеха". Ее реализация приводит к уменьшению размера стека за счет удаления из него элементов, сопоставление которых было завершено успешно. Рекурсия специального типа, которая называется хвостовой^*, также позволяет ограничить рост стека и строго контролировать процесс возврата. Это происходит благодаря очистке стека после успешного сопоставления условия, содержащего рекурсию.

^* (Новый термин - хвостовая рекурсия (tail recursion).- Прим. пер.)

Как известно, любое рекурсивное определение содержит по крайней мере одно нерекурсивное правило и одно или несколько правил с рекурсией. В большинстве случаев в определении имеется по одному правилу каждого типа. Считается, что используется хвостовая рекурсия, если последнее условие в последнем правиле является рекурсивным. Данное выше определение факториала является рекурсивным, поскольку во втором правиле используется отношение fact. Но это не хвостовая рекурсия, так как отношение fact не является последним в последнем (в данном случае во втором) правиле. Приведем пример определения отношения, использующего хвостовую рекурсию:

X in (X Y)

X in (x Z)

Это отношение можно использовать для генерации последовательности чисел X, X + 1, X + 2, ..., Z - 1. Аналогичная задача решалась в гл. 2 с помощью других отношений. В данном случае рекурсия содержится в последнем условии последнего правила. Ниже дан протокол трассировки

all-trace (x:x in (13))

No (more) answers

На рис. 3.5 изображено состояние стека во время обработки запроса. Попробуем на этом примере разобраться, в чем сила хвостовой рекурсии. Заметим, что в процессе оценки каждого числа используются три отношения - SUM, LESS и in. После того как сопоставление цели с правилом 2 успешно проведено, стек очищается и программа переходит к поиску следующего по порядку числа^* до тех пор, пока сопоставление не закончится неудачей.

^* (Можно добавить, что в стеке в любой момент времени находится не более двуи отношений SUM и LESS.- Прим. пер.)

Рис. 3.5. Состояние стека в процессе обработки запроса для программы с хвостовой рекурсией

Упражнение 3.12

Составьте содержащее хвостовую рекурсию отношение для получения расположенной в порядке убывания последовательности целых чисел в интервале (X Y), причем X должно входить в эту последовательность. Для получения протокола трассировки типичного запроса используйте программу SIMTRACE.

Упражнение 3.13

Возрастающую последовательность можно получить, изменив на противоположный порядок следование правил, описывающих отношение in. Можно ли считать, что это новое определение содержит хвостовую рекурсию. Проконтролируйте работу новой программы с помощью SIMTRACE.

Значительный эффект может принести использование отношений с хвостовой рекурсией в работе со списками. В приложении книги "Руководство по микроПрологу" приводится пример отношения APPEND, содержащего хвостовую рекурсию:

append (( ) X X)

append (Y Z x)

В руководстве отмечается, что размер стека не зависит от длины обрабатываемого списка.