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