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



         

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


Вычисляется новое значение N1, равное двум без единицы, то есть единице. Пролог снова пытается вычислить подцель fact(N1,F1) (правда, со значением переменной N1, равным единице).

На этот раз происходит сопоставление цели (fact(1,F1)) с заголовком первого предложения, при этом переменная F1 конкретизируется единицей. Пролог-системе наконец-то удалось вычислить вторую подцель второго правила, и она переходит к вычислению третьей подцели (F=F1*N). Переменная N была равна двум, переменная F1 - единице, произведение двух и единицы равно двум и, значит, переменная F конкретизируется двойкой.

Начинается обратный ход рекурсии. После того, как был вычислен факториал двойки, Пролог-система готова вычислить факториал тройки. Для этого нужно умножить факториал двух на три. Переменная F будет конкретизирована числом шесть. Мы получили ответ на вопрос о факториале трех.

Однако вычисления на этом не заканчиваются. Пролог-система обнаруживает, что цель fact(1,F1) может быть сопоставлена не только с заголовком первого предложения, но и с заголовком правила (fact(N,F)). Переменная N конкретизируется единицей, а переменная F1 связывается с переменной F. После этого переменная N1 означивается числом на единицу меньшим, чем значение переменной N, то есть нулем. Пролог-система пытается вычислить цель fact(0,F1). С заголовком первого предложения (fact(1,1)) сопоставить эту цель не удается, поскольку ноль не равен единице. Зато с заголовком второго предложения (fact(N,F)) цель успешно унифицируется. Переменная N1 становится равна минус единице. После этого делается попытка вычислить цель fact(-1,F1).... Потом fact(-2,F1), fact(-3,F1), fact(-4,F1), fact(-5,F1)... .

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

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


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