Шумихин / Шумихин / Шумихин - лекция 7

ЛЕКЦИЯ 7
19.10.12

Рекурсивные процедуры

Рекурсия в Прологе -- в правой части правила есть вызов предиката, который стоит в левой части правила.

Рекурсия в Прологе -- аналог метода математической индукции в математике.

Есть база рекурсии, есть шаг рекурсии. Т.е. как правило рекурсивные процедуры описываются не менее чем двумя предложениями в Прологе.
1. Граничное условие либо условие выхода. Не содержит рекурсивного вызова.
2. Правило, которое такого сорта предложение с вызовом предиката содержит в себе.

ПРИМЕР
родитель(предок, потомок).
предок(Предок, Потомок) :- родитель(Предок, Потомок).
предок(Предок, Потомок) :- родитель(Предок, Человек), предок(Человек, Потомок).

<предикат> :-
[<подцели>],
[<условие выхода>],
[<подцели>],
<предикат>,
[<подцели>].

n! = (n-1)!*n
1! = 1

predicates
fact(integer, real)
clauses
fact(1, 1).
fact(N, F) :- M=N-1,
fact(M, K),
F=K*N.

fact(3, X).
N->3, X->F
M->2
fact(2, K)
N1->2
M1->1
fact(1, K1)
K1->1
F1->1
K->2
F=6

Однако если цель внешняя, Пролог найдёт первое (и единственное) решение, а потом пойдёт по второму правилу и начнёт пытаться высчитать факториалы отрицательных чисел. Это неправильно, и процесс может продолжаться до бесконечности.

Как это обойти

1.
clauses
fact(1, 1).
fact(N, F) :- N>1,
M=N-1,
fact(M, K),
F=K*N.

2.
clauses
fact(1, 1) :- !.
fact(N, F) :- M=N-1,
fact(M, K),
F=K*N.

Факториал достаточно большого числа вычислить не получится, т.к. стек довольно быстро переполняется. В некоторых случаях, если промежуточные значения не важны, их можно не хранить. (В данном случае они важны.)

Определение
Правой, или хвостовой, рекурсией называется рекурсивное правило, удовлетворяющее двум условиям:
1) рекурсивный вызов является последней подцелью в правиле;
2) в правиле нет точек возврата.

ПРИМЕР
predicates
count1(real)
count2(real)
count3(real)
check(real)

clauses
count1(X) :- write(X),
NewX=X-1,
count1(New X),
nl.
count2(X) :- X>=0,
write(X), nl,
count2(X).
count2(X) :- X<0,
write("-").
count3(X) :- write(X),
NewX=X-1,
check(X),
count3(New X).
check(X) :- X>=0, write("+").
check(X) :- X<0, write("-").

count1(X) -- рекурсивный вызов не последний, значит, рекурсия не хвостовая.
Хвостовая рекурсия:
count1(X) :- write(X),
nl,
NewX=X-1,
count1(New X).

count2(X) -- есть точки возврата.
Хвостовая рекусрия:
count2(X) :- X>=0, !,
write(X), nl,
count2(X).
count2(X) :- X<0,
write("-").

count3(X) -- есть точки возврата в предикате check(X).
Хвостовая рекурсия:
count3(X) :- write(X),
NewX=X-1,
check(X),
count3(New X).
check(X) :- X>=0, !, write("+").
check(X) :- X<0, write("-").

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

Вернёмся к примеру с факториалом.
predicates
fact(integer, real)
fact(integer, real, integer, real)
clauses
fact(N, F) :- fact(N, F, 1, 1).
fact(N, F, N, F) :- !.
fact(N, F, I, P) :- NI = I+1, NP = P*NI,
fact(N, F, NI, NP).

Для SWI-пролога нельзя объявить два предиката с одинаковыми именами и разной арнсотью, вернее, можно, но со скрипом. Так что лучше переименовать второй предикат: fact(integer, real, integer, real) -- в fact1(integer, real, integer, real).

ХВОСТОВУЮ РЕКУРСИЮ ИСПОЛЬЗОВАТЬ В ДЗ, если это возможно.

fib(1, 1) :- !.
fib(2, 1) :- !.
fib(N, F) :- N1 = N - 1, N2 = N - 2, fib(N1, K1), fib(N2, K2), F=K1+K2.

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

Левая рекурсия -- рекурсивный вызов является не крайним правым, а крайним левым.
Вопрос: если в программе определения pred поменять местами подцели, т.е. правую рекурсию сделать левой, останется ли это описание верным? Всегда ли оно будет верным?
________________________________________________