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.