8.7.2. Числовая рекурсия
Хорошо известно
правило вычисления n!
через (n
1)! При этом
граничным условием или условием выхода
из рекурсии является соглашение, что
.
Таким образом, имеется рекурсивное
правило: n!
= (n
– 1)! × n
и граничное условие
На PROLOG эти два допущения можно записать так:
fact(0,1)if!.
fact(N,X)if M=N1,fact(M,Y),X=Y+N.
Зададим вопрос:
fact(3,X).
Процесс работы программы можно изобразить как на рис. 8.1.
Рис. 8.1. Рекурсия
Здесь сплошная стрелка означает очередное сопоставление и его результат (резолюцию) при движении к граничному условию, а пунктирная обратный ход рекурсии до получения ответа на заданный вопрос. В программе использован стандартный предикат "!", называемый "отсечение" (по английски "cut"). Он прекращает поиск альтернативных решений после достижения граничного условия. PROLOG-системе не известно, нужны ли программисту другие варианты ответа, система, если нет других указаний, всегда будет искать все возможные ответы и будет продолжать прямой ход для Х = 1, 2, … до исчерпания стека. Чтобы этого не случилось, в правой части граничного правила стоит предикат "!".
Приведем еще два примера числовой рекурсии.
Примеры
8.6. Найти 4 член в последовательности чисел Фибоначчи:
,
если
,
,
где
fib(1,.,1) if!./*определим 1-е число,0-ене определено*/
fib(2,1,1) if!./*второе число=1,первое число=1*/
fib(N,X,Y) if M=N-1,fib(M,L,X),Y=L+X.
/*N-е число=Y, предыдущее N1=X,
если M=N 1, M–е число=Х, М1-е число=L,
а Y=L+X*/.
8.7. Найти наибольший общий делитель NOD(M, N).
Clauses
Nod(X,X,X) if!.
Nod(X,Y,K) if X>Y,R=X-Y,nod(R,Y,K).
Nod(X,Y,K) if Y>X,R=Y-X,nod( X,Y,K).
/* если два числа X и Y равны, то nod=X, если не равны то уменьшать большее на величину меньшего до тех пор ,пока числа не сравняются*/.
8.8. Написать программу с внутренней целью, которая осуществляет ввод с клавиатуры и выводит значение xn для:
xn=xn-1+2xn-2, x1=x2=1, x5=?
predicates
xn(integer,integer)
writeresult(integer)
query
clauses
xn(X,1) if X<=2,!.
xn(X,Y) if X1=X-1, xn(X1,Y1),X2=X-2, xn(X2,Y2),Y=Y1+2*Y2
writeresult(X) if
X<=0,
write("no solutions because N<=0"),
nl,!
writeresult(X) if
xn(X,Y),
write(Y),nl.
query if
write("input N: "), readint(N),
writeresult(N).
goal
query.
Упражнения
В следующих упражнениях написать программу с внутренней целью, которая осуществляет ввод с клавиатуры и выводит значение xn .
xn = 2xn-1 – 1, x1=1, x5 = ?
xn = n/xn-1, x1 = 2, x5 = ?
xn = 3xn-1 + 1, x1 = 2, x5 = ?
xn+1 = 2xn – xn-1, x1 = 3, x2 = 1, x6 = ?
xn = 1+xn-1 + xn-2, x1 = x2 = 2, x6 = ?
xn+1 = xn + xn-1 + 3, x1 = 1, x2 = 2, x5 = ?
xn+2 = xn + 2xn+1, x1 = 2, x2 = 1, x6 = ?
xn = xn-1 + xn-2 + 2, x1 = x2 = 1, x6 = ?
xn+2 = xn + 1/xn+1, x1 = x2 = 1, x5 = ?
xn+1 = xn × xn-1, x1 = 1, x2 = 1/2, x6 = ?
xn+2 = 2xn+1 + 3xn, x1 = 0, x2 = 1, x5 = ?
xn = xn-1 + 2xn-2, x1 = x2 = 1, x5 = ?
xn+2 = 2xn+1 + xn, x1 = 2, x2 = 1, x5 = ?
xn+2 = xn+1 + xn/2, x1 = 1, x2 = 2, x5 = ?
xn+1 = xn + 2xn-1, x1 = x2 = 1, x6 = ?