 |
Использование рекурсии в Прологе
|
|
|
|
Цель работы
Изучение построения рекурсивных процедур на Прологе. Разработка программ с использованием рекурсии.
Краткие сведения
Рекурсия — это процедура, вызывающая сама себя до тех пор, пока не будет соблюдено некоторое условие (называемое граничным), которое остановит рекурсию. В отличие от императивных языков программирования, в которых для организации повторяющихся действий используются циклы, в Прологе используются процедура поиска с возвратом (откат) и рекурсия. Откат позволяет получить множество решений в одном запросе к программе.
Пусть, например, имеется набор фактов, описывающий родственные связи людей через предикат parent (родитель), имеющий два аргумента: имя родителя, и имя ребенка. Используя предикат parent нужно реализовать отношение "быть предком". Для того чтобы один человек был предком (ancestor) другого, нужно, чтобы он либо был его родителем (parent), либо являлся родителем другого его предка. Это можно записать:
% родитель – это предок
ancestor(A, D):- parent(A, D).
% родитель предка – это предок
ancestor(A, D):- parent(A, H), ancestor(H, D).
Отношение ancestor (предок) является транзитивным. Отношение ancestor содержит отношение parent. Это следует из первого правила (всякий родитель является предком). Второе правило дает транзитивность.
По аналогии с математической индукцией, рекурсивная процедура включает в себя базис и шаг рекурсии.
Базис рекурсии — это правило, определяющее начальную ситуацию или ситуацию в момент прекращения. Обычно базис рекурсии описывает некий простейший случай, при котором ответ получается сразу даже без использования рекурсии. В приведенной процедуре, описывающей предикат ancestor (предок), базисом рекурсииявляется первое правило, которое определяет, что ближайшие предки человека — его родители. Базис рекурсии обычно содержит условие, при выполнении которого происходит выход из рекурсии или отсечение.
|
|
|
Шаг рекурсии — это правило, в теле которого в качестве подцели содержится вызов определяемого предиката. Чтобы не было зацикливания, определяемый предикат должен вызываться от других параметров, что указаны в заголовке правила. На каждом шаге рекурсии параметры должны так, чтобы в итоге либо сработал базис рекурсии, либо условие выхода из рекурсии.
Бывают ситуации, когда процедура содержит несколько предложений, описывающих базис рекурсии, и несколько предложений, описывающих шаг рекурсии.
Операция отсечения
Пролог имеет встроенную операцию отсечения, которая позволяет управлять механизмом возврата (перебора). Операция записывается с помощью восклицательного знака ('!'). Отсечение трактуется как псевдоцель, которая всегда выполняется успешно. Если операция отсечения встречается в одном из предложений процедуры, то после ее выполнения предотвращается возврат к предыдущим подцелям предложения, т.е. фиксируются выбранные решения для этих подцелей и остальные альтернативы не рассматриваются. Так, пусть имеется процедура А:
А:- P, Q,!, S, T.
A:- R.
где A, P, Q, R, S, T – предикаты. Отсечение повлияет на вычисление цели А следующим образом. Перебор будет возможен в списке подцелей P, Q, однако, как только точка отсечения будет достигнута, найденные решения для подцелей P и Q фиксируются и все альтернативные решения для них не рассматриваются. Альтернативное предложение, входящее в процедуру A:-R также не будет учитываться. Тем не менее, возврат (перебор) будет возможен в списке подцелей S, T.
Отсечение, повышая выразительность языка, дает возможность проще формулировать взаимно исключающие утверждения и повышает эффективность работы программы. Так, фрагмент программы, вычисляющий значение функции
|
|
|
выглядит следующим образом:
- без использования отсечения
f(X,Y):- X<1, Y=1+sin(X).
f(X,Y):- 1<=X, X<3, Y=1+cos(X).
f(X,Y):- X>=3, Y=X*X.
- с использованием отсечения
f(X,Y):- X<1,!, Y=1+sin(X).
f(X,Y):- X<3,!, Y=1+cos(X).
f(X,Y):- X>=3, Y=X*X.
Второй фрагмент не только выразительнее, но и эффективнее, чем первый. Это связано с тем, что после того, как решение найдено, механизм перебора (поиска других решений) отключается, в то время как в первом случае поиск несуществующих других решений продолжается. И именно с помощью отсечения мы включаем дополнительную информацию о взаимной исключительности утверждений в программе (т.е. информацию о единственности решения), что и позволяет не вести бесполезный поиск решений, которых нет.
Примеры программ
Пример 2.1. Создать предикат, который вычисляет для любого натурального числа его факториал [1]. Эта задача имеет рекурсивное математическое описание:
— факториал нуля равен единице;
— факториал некоторого числа есть факториал числа, меньшего на единицу, умноженный на исходное число.
Задача допускает рекурсивное решение. Запишем предикат, эквивалентный математическому определению предиката:
factorial(0,1). % факториал нуля равен единице
factorial(N,F_N):-
M=N-1,
factorial(M,F_M), % F_M равен факториалу числа на
% единицу меньшего исходного числа.
F_N=F_M*N. % факториал исходного числа равен
% произведению F_M на само число
Однако при попытке вычислить факториал произвольного натурального числа с помощью описанного предиката factorial произойдет переполнение стека ("Stack overflow").
Чтобы разобраться с возникшей ошибкой, рассмотрим, что будет происходить при попытке вычислить факториал трех. Запрос имеет вид:
goal factorial(3,X).
Пролог-система унифицирует цель с заголовком первого правила (factorial(1,1)) и терпит не удачу (число 3 не равно 1). Тогда, унифицируя цель с заголовком второго правила (factorial(N,F_N)), переменная N конкретизируется значением 3, а переменная X связывается с переменной F_N. Происходит попытка выполнить подцели, расположенные в теле правила слева направо. При этом N1 принимает значение N-1, т. е. 2. Срабатывание подцели factorial(M,F_M) приводит к рекурсивному вызову предиката при M, равным 2. Опять при унификации цели с первым правилом система терпит неудачу (1 не равно 2). Сопоставление с головой второго правила происходит успешно и вычисляется новое значение M, равное 2-1=1. Пролог вычисляет подцель factorial(M,F_M) (со значением переменной M, равным 1).
|
|
|
Далее происходит сопоставление цели (factorial(1,F_M)) с заголовком первого правила и переменная F_M конкретизируется значением 1. Пролог-система вычислила вторую подцель второго правила и переходит к вычислению третьей подцели (F_N=F_M*N). Переменная N равна 2, переменная F_M — 1, произведение 2*1=2, следовательно, переменная R конкретизируется двойкой.
Начинается обратный ход рекурсии. После того, как был вычислен факториал двойки, Пролог-система вычислит факториал тройки (факториал двух умножить на три) и переменная F_N будет конкретизирована числом 6. Получено значение 3!=6.
Но вычисления на этом не заканчиваются, т. к. Пролог-система обнаруживает, что цель factorial(1,F_M) можно сопоставить не только с заголовком первого правила, но и с заголовком правила factorial(N,F_N). Переменная N конкретизируется значением 1, а F_M связывается с переменной F_N. После этого переменная M конкретизируется числом на единицу меньшим, чем значение переменной N, т. е. 1-1=0.
Пролог-система пытается вычислить цель factorial(0,F_M), сопоставляет эту цель с заголовком первого правила (factorial(1,1)) и терпит неудачу, т. к. ноль не равен единице. Зато с заголовком второго правила (factorial(N,F_N)) цель успешно унифицируется. Переменная M становится равна -1 и делается попытка вычислить цель factorial(-1,F_M). Потом factorial(-2,F_M),factorial(-3,F_M),factorial(-4,F_M)...
Процесс продолжается до тех пор, пока часть оперативной памяти, отведенная под стек, не будет исчерпана. После этого выпол-нение программы остановится с сообщением "Stack overflow".
Есть два варианта корректировки процедуры.
Можно в имеющуюся процедуру вставить проверку, что число, для которого применяется правило, больше единицы. Тогда программно это будет выглядеть так:
factorial(0,1).
factorial(N,F_N):-
N>1, % проверка, что число больше единицы
M=N-1,
factorial(M,F_M),
|
|
|
F_N=F_M*N.
В этом случае произойдет повторное согласование цели factorial(1,F_M) с заголовком правила, переменная N получит значение 1, переменная F_N свяжется с F_M, первая подцель правила (N>1) будет ложной и на этом процесс оборвется.
Другой вариант решения проблемы — добавить в первое правило процедуры отсечение. Вызов отсечения приводит к тому, что правила процедуры, расположенные ниже, не рассматриваются. Как только цель будет согласована с заголовком первого правила, сработает отсечение, и не произойдет попытки унифицировать цель с заголовком второго правила. Процедура будет иметь вид:
factorial(0,1):-!. % условие останова рекурсии
factorial(N,F_N):-
M=N-1,
factorial(M,F_M),
R=R1*N.
Пример 2.2. Рассмотримвычисление значения факториала с использованием хвостовой рекурсии [1].
Хвостовая рекурсия — частный случай рекурсии, при котором любой рекурсивный вызов является последней операцией перед возвратом из функции.
Для реализации в процедуру factorial для хранения промежуточных результатов добавим два дополнительных параметра. Третий параметр используем, чтобы запомнить значение натурального числа, для которого вычисляется факториал, четвертый параметр — для факториала числа, хранящегося в третьем параметре. Третий и четвертый аргументы будут равны единице. После завершения рекурсивных вычислений второй аргумент должен содержать факториал числа, находящегося в первом параметре. На каждом шаге рекурсии третий аргумент увеличивается на 1, а второй аргумент умножается на значение третьего аргумента. Рекурсияостановится, когда третий аргумент будет равен первому, а четвертый аргумент будет содержать значение искомого факториала, которое помещается в качестве ответа во второй аргумент.
factorial2(N,R,N,R):-!.% если третий аргумент равен
% первому, остановить рекурсию
factorial2(N,R,N1,R1):-
N2=N1+1, % N2 - следующее натуральное
% число после числа N1,
R2=R1*N2, % R2 - факториал N2.
factorial2(N,R,N2,R2).% рекурсивный вызов с новым
% натуральным числом N2 и
% соответствующим ему посчитанным факториалом R2
Остановить рекурсию можно отсечением в базисе рекурсии или добавлением в начало второго правила сравнение N1 с N.
Пример 2.3. Вычисление чисел Фибоначчи. Числа Фибоначчи – это элементы последовательности 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, … в которой каждое последующее число равно сумме двух предыдущих. При реализации построим два базиса рекурсии: первый — первое число Фибоначчи равно 0; второй — второе число Фибоначчи равно 1. Шаг рекурсии:для вычисления числа Фибоначчи с номером N нужно вычислить и сложить числа Фибоначчи с номерами N-1 и N-2. Программно это выглядит так:
fib(1,0):-!. % 1-е число Фибоначчи равно 0
|
|
|
fib(2,1):-!. % 2-е число Фибоначчи равно 1
fib(N,R):-
N1=N-1, fib(N1,R1), % R1 – (N-1)-е число Фибоначчи
N2=N-2, fib(N2,R2), % R2 – (N-2)-е число Фибоначчи
R=R1+R2. % N-е число Фиб-чи
Отсечение в первых двух правилах процедуры нужно для остановки рекурсии, чтобы при прямом ходе рекурсии не произошло выхода из множества натуральных чисел в область отрицательных чисел.
Варианты заданий
1. Создать предикат, вычисляющий неотрицательную степень целого числа.
2. Создать предикат, вычисляющий по натуральному числу N сумму чисел от 1 до N.
3. Создать предикат, вычисляющий по натуральному числу N сумму нечетных чисел, не превосходящих N.
4. Создать предикат, вычисляющий наибольший общий делитель двух натуральных чисел.
5. Создать предикат, вычисляющий наименьшее общее кратное двух натуральных чисел.
6. Создать программу, реализующую игру «Угадай число» (компьютер загадывает число, человек пытается его отгадать, ориентируясь на реплики «Больше», «Меньше»).
7. Создать предикат, вычисляющий сумму цифр натурального числа.
8. Создать предикат, вычисляющий произведение цифр натурального числа.
9. Создать предикат, переводящий число из десятичной системы счисления в двоичную.
10. Создать предикат, переводящий число из двоичной системы счисления в десятичную.
11. Написать программу, которая печатает таблицу степеней числа 2.
12. Реализовать, используя рекурсию и отсечение, цикл с постусловием (типа repeat <оператор> until <условие>).
13. Реализовать, используя рекурсию и отсечение, цикл со счетчиком (типа for i:=1 to N do <оператор>).
14. Реализовать, используя рекурсию и отсечение, цикл со счетчиком (типа for i:=1 downto N do <оператор>).
|
|
|
