Rekurzija v prologu

Članek govori o rekurziji v programskem jeziku Prolog.

Rekurzija v prologu definira pojem tako, da pri sami definiciji uporabi isti pojem.

rekurzijska spremenljivka, natančna spodnja meja

robni pogoj

definicija pri spodnji meji, nimamo rekurzivnega klica, imamo samo znane pojme

splošni primer

definiranje pojma pri neki vrednosti rekurzijske spremenljivke z uporabo znanih pojmov in z uporabo pojma samega pri manjših vrednostih rekurzijske spremenljivke

Robni pogoj:

f(0)=1

Splošni primer:

f(N+1) = (N+1) × f(n)

Faktoriela

Primer rekurzivnega programa v prologu:

fak(0,1).         %0 in 1 sta v relaciji faktoriela
fak(N,Fak) :-
  N > 0,
  N1 is N-1,
  fak(N1,Fak1),
  Fak is N*Fak1.

Časovna zahtevnost raste linearno.

Sledenje:

?- spy(fak/2), trace, fak(2,F).

 call> fak(2,F)
   call> 2 > 0
   exit> 2 > 0
   call> N1' is 2-1
   exit> 1 is 2-1 % N1' = 1
   call> fak(1,Fak1')
     call> 1 > 0
     exit> 1 > 0
     call> N1 is 1-1
     exit> 0 is 1-1 % N1 = 0
     call> fak(0,Fak1)
     exit> fak(0,1) % Fak1 = 1
     call> Fak1' is 1*1
     exit> 1 is 1*1 % Fak1' = 1
   exit> fak(1,1)
   call> F is 2*1
   exit> 2 is 2*1 % F = 2
 exit> fak(2,2)
F = 2
yes

Fibonaccijeva števila

Robna primera

Fib(0) = 0

Fib(1) = 1

Splošni primer

Fib(N) = Fib(N-1) + Fib(N-2), N > 1

0 1 2 3 4 5 6 7
0 1 1 2 3 5 8 13

fib(0,1).
fib(1,1).
fib(N,F) :-
  N > 1,
  N1 is N - 1,
  fib(N1,F1),
  N2 is N - 2,
  fib(N2,F2),
  F is F1 + F2.

Problem te procedure je časovna zahtevnost, ki raste eksponentno. To povzroči ponavljanje kjer že izračunane stvari ponovno računamo.

           Fib(10)
         /        \
     Fib(9)        Fib(8)
     /   \        /     \
 Fib(8) Fib(7)  Fib(7)  Fib(6)
  /  \   /  \    /  \     /  \

Težavo rešimo z dinamičnim programiranjem (s pristopom od spodaj navzgor). Najprej rešimo preproste probleme in s pomočjo njih gradimo rešitve za težje probleme.

Zapomnimo si zadnji 2 števili in izračunamo naslednjo:

fib_hitri(0,1).
fib_hitri(N,F) :-
  N > 0,
  fib_hitri(N,F,1,1,1).

%fib_hitri(Vhod,Rezultat,Števec,Predhodni,Trenutni)

fib_hitri(N,F,N,_,F).            %robni pogoj
fib_hitri(N,F,Stevec,F1,F2) :-
  Stevec < N,                    %stevec ne sme preseci meje, drugace se zacikla
  F3 is F1 + F2,                 %izracun novega fib. stevila
  Stevec1 is Stevec + 1,         %vecanje stevca
  fib_hitri(N,F,Stevec1,F2,F3).  %rekurzija

F je neopredeljena spremenljivka in se (ker je pointer) njegova lokacija v pomnilniku samo prenaša skozi rekurzijo naprej. Šele pri robnem pogoju se F prilagodi izračunanemu številu.

Prednik

primer vzet iz vaj

%prednik(X,Y)

prednik(X,Y) :- 
  roditelj(X,Y).  %robni pogoj

prednik(X,Y) :- 
  prednik(X,Z),
  roditelj(Z,Y).

Delaj

• write(Izraz)
• read(Izraz)

Rekurzija deluje dokler se uporabnik ne naveliča dajati ukaze.

delaj :-
  write(' vtipkaj ukaz:  '),
  read(Ukaz),
  (Ukaz = konec ;
  izvrsi(Ukaz),
  delaj).

Lahko povečamo berljivost tako, da ločimo konjunkcijo od disjunkcije

delaj_lepo :-
  write(' vtipkaj ukaz:  '),
  read(Ukaz),
  odloci(Ukaz).

odloci(konec).
odloci(Ukaz) :-
  izvrsi(Ukaz),
  delaj_lepo.    %posredna rekurzija