(1) Program w3_1
potomek(Potomek,Przodek) :-
Dziecko jest potomkiem
dziecko(Potomek,Przodek).
potomek(Potomek,Przodek) :-
Jeżeli X jest potomkiem,
dziecko(Potomek,X),
to jego dziecko
potomek(X,Przodek).
też jest potomkiem
Rekurencja
Reguła rekurencyjna Warunek startu / stopu
Prawidłowo napisana reguła rekurencyjna musi mieć nierekurencyjną alternatywę
(warunek startu/stopu), w przeciwnym wypadku albo będziemy kręcić się w
nieskończonej pętli, albo rekurencja (i w efekcie program) zakończy się fałszem.
3
(1) Program w3_1
Reguła rekurencyjna  reguła w której wnioskiem
potomek(Potomek,Przodek) :-
dziecko(Potomek,Przodek).
i jednym z warunków jest
ten sam predykat, reguła
potomek(Potomek,Przodek) :-
dziecko(Potomek,X),
samowywołująca się. Potomek = Zygmunt August
potomek(X,Przodek).
Przodek = Zygmunt I Stary
.
Potomek = Zygmunt August
.
Przodek = Bona Sforza
.
rekurencja(...) :-
goal
.
potomek("Zygmunt August",Kogo).
.
.
rekurencja(...),
.
.
.
Kogo=Zygmunt I Stary
Kogo=Bona Sforza
Kogo=Kazimierz Jagiellonczyk
Kogo=Elzbieta Habsburg
Kogo=Wladyslaw Jagiello
Kogo=Zofia Holszanska
2 4
(1) Program w3_1 (1) Program w3_1
Potomek = Kazimierz Jagiellonczyk
Potomek = Zygmunt I Stary
Przodek = Wladyslaw Jagiello
potomek(Potomek,Przodek) :- potomek(Potomek,Przodek) :-
Przodek = Kazimierz Jagiellonczyk
dziecko(Potomek,Przodek). dziecko(Potomek,Przodek).
Potomek = Kazimierz
potomek(Potomek,Przodek) :- potomek(Potomek,Przodek) :-
Jagiellonczyk
dziecko(Potomek,X), dziecko(Potomek,X),
Przodek = Zofia
potomek(X,Przodek). potomek(X,Przodek).
Holszanska
Potomek = Zygmunt I Stary
. .
Potomek = Zygmunt August
. . X = Kazimierz Jagiellonczyk
X = Zygmunt I Stary
. .
goal goal
potomek("Zygmunt August",Kogo). potomek("Zygmunt August",Kogo).
Kogo=Zygmunt I Stary Kogo=Zygmunt I Stary
Kogo=Bona Sforza Kogo=Bona Sforza
Kogo=Kazimierz Jagiellonczyk Kogo=Kazimierz Jagiellonczyk
Kogo=Elzbieta Habsburg Kogo=Elzbieta Habsburg
Kogo=Wladyslaw Jagiello Kogo=Wladyslaw Jagiello
Kogo=Zofia Holszanska Kogo=Zofia Holszanska
5 7
(1) Program w3_1 (1) Program w3_1
potomek(Potomek,Przodek) :- potomek(Potomek,Przodek) :-
Potomek = Zygmunt I Stary
dziecko(Potomek,Przodek). dziecko(Potomek,Przodek).
Przodek = Elżbieta Habsburg
potomek(Potomek,Przodek) :- potomek(Potomek,Przodek) :-
Program cofa się jeszcze do tego miejsca,
dziecko(Potomek,X), dziecko(Potomek,X),
ale podstawianie za X imion kobiet
potomek(X,Przodek). potomek(X,Przodek).
nie przynosi nowego rozwiązania
. .
. .
. .
goal goal
potomek("Zygmunt August",Kogo). potomek("Zygmunt August",Kogo).
Kogo=Zygmunt I Stary Kogo=Zygmunt I Stary
Kogo=Bona Sforza Kogo=Bona Sforza
Kogo=Kazimierz Jagiellonczyk Kogo=Kazimierz Jagiellonczyk
Kogo=Elzbieta Habsburg Kogo=Elzbieta Habsburg
Kogo=Wladyslaw Jagiello Kogo=Wladyslaw Jagiello
Kogo=Zofia Holszanska Kogo=Zofia Holszanska
6 8
(1) Program w3_1 (1) Program w3_1
potomek(Potomek,Przodek) :- potomek(Potomek,Przodek) :-
dziecko(Potomek,Przodek). dziecko(Potomek,Przodek).
Cofanie będzie trwało,
aż nie zostaną znalezione
potomek(Potomek,Przodek) :- potomek(Potomek,Przodek) :-
Potomek = Wladyslaw Warnenczyk
wszystkie rozwiązania
dziecko(Potomek,X), dziecko(Potomek,X),
Przodek = Wladyslaw Jagiello
potomek(X,Przodek). potomek(X,Przodek).
. .
Potomek = Kazimierz Jagiellonczyk
. .
Przodek = Wladyslaw Jagiello
. .
goal goal
potomek(Kto,"Wladyslaw Jagiello"). potomek(Kto,"Wladyslaw Jagiello").
Kto=Wladyslaw Warnenczyk Kto=Wladyslaw Warnenczyk
Kto=Kazimierz Jagiellonczyk Kto=Kazimierz Jagiellonczyk
Kto=Jan Olbracht Kto=Jan Olbracht
Kto=Aleksander Jagiellonczyk Kto=Aleksander Jagiellonczyk
Kto=Zygmunt I Stary Kto=Zygmunt I Stary
Kto=Zygmunt August Kto=Zygmunt August
9 11
(1) Program w3_1 (2) Program w3_3
Nie ma rozwiazania dla
Potomek = Wladyslaw Jagiello
potomek(Potomek,Przodek) :- inkrementuj_1(N):-
dziecko(Potomek,Przodek). write(N),nl,
NoweN = N+1,
Program będzie cofał się
potomek(Potomek,Przodek) :- inkrementuj_1(NoweN).
dziecko(Potomek,X),
do tego miejsca, dopóki
potomek(X,Przodek).
nie podstawi za zmienne
Potomek i X stałych,
.
Potomek = Wladyslaw Warnenczyk
które przyniosą
.
X = Wladyslaw Jagiello
rozwiązanie
.
goal
potomek(Kto,"Wladyslaw Jagiello").
Kto=Wladyslaw Warnenczyk
Rekurencja ogonowa  warunek wywołujący rekurencję jest ostatnim w regule.
Kto=Kazimierz Jagiellonczyk
Kto=Jan Olbracht
Rekurencja oszczędzająca stos  przy wywoływaniu rekurencji nie są odkładane
Kto=Aleksander Jagiellonczyk
do pamięci informacje o niesprawdzonych alternatywach i/lub warunkach.
Kto=Zygmunt I Stary
Kto=Zygmunt August
Brak warunku startu/stopu skutkuje nieskończoną pętlą.
10 12
(2) Program w3_3 (2) Program w3_3
inkrementuj_2(N):- inkrementuj_4(N):-
write(N),nl, write(N),nl,
NoweN = N+1, NoweN = N+1,
inkrementuj_2(NoweN), sprawdz(NoweN),
nl. inkrementuj_4(NoweN).
sprawdz(M):-
M>=100000,
write("Szesciocyfrowa liczba"),nl,
true.
sprawdz(M):-
.
.
.
Rekurencja nieogonowa  warunek wywołujący rekurencję nie jest ostatnim w regule. Rekurencja ogonowa.
Rekurencja nieoszczędzająca stosu  przy każdorazowym wywoływaniu rekurencji Rekurencja nieoszczędzająca stosu  przy każdorazowym wywoływaniu rekurencji
w pamięci zostawiana jest informacja o dodatkowym warunku nl. w pamięci zostawiana jest informacja o niesprawdzonej alternatywie sprawdz().
Program zostanie przerwany z powodu przepełnienia stosu. Program zostanie przerwany z powodu przepełnienia stosu.
13 15
(2) Program w3_3 (2) Program w3_3
inkrementuj_3(N):- inkrementuj_3(N):-
write(N),nl, write(N),nl,
NoweN = N+1, NoweN = N+1,!,
inkrementuj_3(NoweN). inkrementuj_3(NoweN).
inkrementuj_3(_):- write("Tu nigdy nie wejdziemy").
inkrementuj_4(N):-
write(N),nl,
NoweN = N+1,
sprawdz(NoweN),!,
inkrementuj_4(NoweN).
Rekurencja ogonowa. Rekurencja oszczędzająca stos.
Rekurencja nieoszczędzająca stosu  przy każdym wywoływaniu rekurencji w pamięci Odpowiednie użycie cut-a poprawi wadę inkrementuj_3() oraz inkrementuj_4()
zostawiana jest informacja o niesprawdzonej alternatywie inkrementuj_3(). i zapobiegnie przepełnieniu stosu.
Program zostanie przerwany z powodu przepełnienia stosu.
14 16
(3) Program w3_4 (3) Program w3_4
potega(X,Y):- potega1(X,Y,1). potega(X,Y):- potega3(X,Y,W,1),write("Wynik = ",W),nl.
potega1(_,0,W):-write("Wynik = ",W),nl. potega3(_,0,W,W).
potega1(X,N,W):- potega3(X,N,W,Ak):-
NW = W*X, NAk = Ak*X,
NN = N-1, NN = N-1,
potega1(X,NN,NW). potega3(X,NN,W,NAk).
Rekurencja ogonowa. Rekurencja ogonowa.
Wynik nie jest przekazywany do miejsca wywołania predykatu. Wynik jest przekazywany do miejsca wywołania predykatu. Jest to możliwe dzięki
użyciu akumulatora.
17 19
(3) Program w3_4
potega(X,Y):- potega2(X,Y,W),write("Wynik = ",W),nl.
potega2(_,0,1).
potega2(X,N,W):-
NN = N-1,
potega2(X,NN,NW),
W = NW*X.
Rekurencja nieogonowa.
Wynik jest przekazywany do miejsca wywołania predykatu.
18