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


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


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

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


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

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

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

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

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

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

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

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

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

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


- Начало -  - Назад -  - Вперед -