Рекурсия

Для организации повторений, в прологе используется рекурсия.

Рекурсия — это предикат, вызывающий сам себя, до тех пор, пока не будет соблюдено некоторое условие, которое остановит рекурсию.

Пример рекурсии: найти факториал 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