Практическая информатика




Рекурсивные процедуры


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

Гравюра голландского художника Мориса Эшера "Рисующие руки" - одна из лучших иллюстраций понятия рекурсии. Всем известный стишок о попе и его собаке демонстрирует нам бесконечность рекурсивных вызовов. Используя рекурсию как прием программирования мы должны быть уверены, что рекурсивная процедура будет завершена.


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

На примере уже имеющейся у нас базы данных объясним преимущества использования рекурсии и особенности рекурсивных правил. Пусть имеются следующие факты:

больше(слон, лошадь). больше(лошадь, осел). больше(осел, собака). больше(осел, обезьяна).

Выполним запрос к базе данных

?- больше(осел, собака). Yes

Цель больше(осел, собака) была достигнута потому, что этот факт был сообщен Прологу при загрузке базы. Теперь проверим, больше ли обезьяна слона?

Нет, не больше. Мы получили такой ответ, какой и ожидали: соответствующий запрос, а именно больше(обезьяна, слон) не подтвердился. Но, что случится, если мы зададим вопрос по-другому?

?- больше(слон, обезьяна). No

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

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


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