Основы программирования на языке Пролог



         

Рекурсия - часть 3


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

1!=1 /* факториал единицы равен единице */ N!=(N-1)!*N /* для того, чтобы вычислить факториал некоторого числа, нужно вычислить факториал числа на единицу меньшего и умножить его на исходное число */

Попробуем записать реализацию предиката, эквивалентную математическому определению предиката:

fact(1,1). /* факториал единицы равен единице */ fact(N,F):- N1=N-1, fact(N1,F1), /* F1 равен факториалу числа на единицу меньшего исходного числа */ F=F1*N. /* факториал исходного числа равен произведению F1 на само число */

К сожалению, при попытке вычислить факториал произвольного натурального числа с помощью описанного выше предиката fact произойдет переполнение стека ("Stack overflow"). Попробуем разобраться, в чем причина. Рассмотрим, например, что будет происходить, если мы попытаемся вычислить факториал трех.

Соответствующий вопрос можно записать следующим образом:

fact(3,X).

Пролог-система попытается унифицировать цель с заголовком первого предложения (fact(1,1)). Ей это не удастся, поскольку число три не равно единице. При унификации цели с заголовком второго предложения (fact(N,F)) переменная N конкретизируется числом три, а переменная X связывается с переменной F. После этого происходит попытка выполнить подцели, расположенные в теле правила слева направо. Сначала переменная N1 означивается числом на единицу меньшим, чем значение переменной N, то есть двойкой. Срабатывание следующей подцели (fact(N1,F1)) приводит к рекурсивному вызову предиката, вычисляющего факториал, со значением переменной N1, равным двум.

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


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