Рекурсия
Для организации повторений, в прологе используется рекурсия.
Рекурсия — это предикат, вызывающий сам себя, до тех пор, пока не будет соблюдено некоторое условие, которое остановит рекурсию.
Пример рекурсии: найти факториал n!.
Задача нахождения значения факториала n! очень хорошо решается с помощью рекурсии, поскольку может быть сведена к решению аналогичной подзадачи, которая, в свою очередь, сводится к решению аналогичной подзадачи и т.д.
Действительно, чтобы найти значение факториала n!, можно найти значение факториала (n-1)! и умножить найденное значения на n. Для нахождения значения факториала (n-1)! можно пойти по уже известному пути - найти значение факториала (n-2)! и умножить найденное значения на n-1. Так можно действовать до тех пор, пока не доберемся до нахождения значения факториала (n-n)! или другими словами, факториала 0!. Значение факториала 0! известно - это 1. Вот это и будет граничное условие, которое позволит остановить рекурсию. Все, что теперь остается - это умножить полученную единицу на (n-(n-1)), затем на (n-(n-2)) и т.д. столько раз, сколько было рекурсивных вызовов. Результат n! получен.
Вот как выглядит программа, которая проделывает вычисление n! (нужно заметить, что предложения Prolog - программы достаточно точно повторяют формулировку задачи на естественном языке).
PREDICATES
factorial (integer, integer)
CLAUSES
%факториал 0! равен 1
factorial (0, 1):- !.
%факториал n! равен факториалу (n-1)!, умноженному на n
factorial (N, Factorial_N):- M=N-1, factorial (M, Factorial_M),
Factorial_N=Factorial_M*N.
GOAL
write ("Для какого числа Вы хотите найти факториал? "), readint (Number),
factorial (Number, Result), write (Number, "!=", Result).
Результат работы программы: 3!=6
- Основные понятия Искусственного Интеллекта
- Основные направления исследований в области Искусственного Интеллекта
- Логическое программирование. Основные понятия языка Пролог (Предикаты, Факты, Правила, Простые и составные запросы).
- Константы, переменные и составные термы. Сопоставление.
- Основные разделы Prolog. Встроенные предикаты
- Арифметические вычисления и сравнения в прологе
- Встроенные предикаты ввода и вывода
- Управление поиском решений. Встроенный механизм поиска с возвратом. Использование предиката fail и отсечение.
- Рекурсия
- Обработка списков. Объявление и использование.
- Обработка строк. Предикаты для строк. Встроенные предикаты для преобразования типов. Использование строк.
- Файлы. Оисание. Стандартные предикаты. Операции над файлами.
- Работа с внутренними базами данных: добавление и удаление фактов из базы данных.
- Данные и знания.