Rekursija ir ciklai Spausdinti
( 5 Votes )
Parašė Aurimas Šimkus   

Prolog kalboje, kaip ir kitose tradicinėse loginio programavimo kalbose, vietoj imperatyviosiose kalbose tradiciškai naudojamų ciklų (while, for) paprastai yra naudojama rekursija. Rekursija kaip ir ciklai naudojama kokios nors programos kodo dalies kartojimui realizuoti. Pvz., paieška duomenų bazėje, mažiausio/didžiausio aibės skaičiaus radime, rikiavimo algoritme.

 

Ciklas repeat 

repeat - vienas iš integruotųjų Prolog predikatų, kuris už savęs procedūroje esančius predikatus kartoja tol, kol nors vienas iš jų grąžina false reikšmę. Pavyzdžiui, tokiu principu galime realizuoti programos meniu (laukiama vis naujo vartotojo pasirinkimo, kol neįvedamas numatytas pabaigos raktažodis). Žinoma, tą patį galima realizuoti ir su rekursija.

Meniu procedūros pavyzdys:

meniu :-
   repeat,
   write('\tPasisveikinimas - 1\n\tKvadratu - 2\n\tBaigti - 3'),
   read(X),
   pasirinkimas(X), !.

pasirinkimas(1) :- 
   write('Labas, vartotojau!'),
   nl, false.

pasirinkimas(2) :-
   write('Iveskite skaiciu, kurio kvadrato norite:'),
   read(Sk), Ats is Sk * Sk,
   write(atsakymas:Ats), nl, false.

pasirinkimas(3) :- true.

Meniu bus kartojamas tol, kol pasirinkimas(X) negrąžins reikšmės true, ty kol nesikreipsime į pasirinkimas(3). Šauktukas reikalingas tam, kad pabaigus programą nebebūtų prašoma įvesties (<enter>).

Vykdymo pavyzdys:

?- meniu.
      Pasisveikinimas - 1
      Kvadratu - 2
      Baigti - 3
 |: 1.
 Labas, vartotojau!
      Pasisveikinimas - 1
      Kvadratu - 2
      Baigti - 3
 |: 2.
 Iveskite skaiciu, kurio kvadrato norite:
 |: 15.
 Atsakymas:225.
      Pasisveikinimas - 1
      Kvadratu - 2
      Baigti - 3   
 |: 3.
 true.
?-

 

Rekursija 

Prolog kalboje rekursija realizuojama taip:

  1. pirmiausia aprašomas faktas arba taisyklė, kuri patikrina rekursijos (ciklo) pabaigą,
  2. tada rašomos kitos tokiu pačiu pavadinimu (tas pats predikatas) taisyklės arba procedūra, kuriuos atlieka kokius nors veiksmus ir jose taip pat nurodomas kreipimasis vėl į tą patį predikatą (pakartotinis kreipimasis - rekursija).

Užklausos vykdymas trunka tol, kol nėra tenkinamas pirmasis faktas arba taisyklė, kadangi juose jau nėra pakartotinio kreipimosi į save.

Vienas paprastesnių pavyzdžių yra Euklido didžiausio bendrio daliklio (DBD) algoritmas. Apie šį algoritmą plačiau pasiskaityti ir pamatyti C++ pavyzdį galite čia. Prolog versija:

dbd(Sk1, 0) :- write(Sk1).  /*rekursija baigiama, kai antrasis skaičius =0*/
dbd(Sk1, Sk2) :- A is Sk2,          /*A lygus antrajam skaičiui.*/
                 B is Sk1 mod Sk2,  /*B lygus pirmojo ir antrojo skaičių dalybos liekanai*/
                 dbd(A, B).         /*nauja užklausa - rekursija*/ 

Pvz., įvykdę užklausą

dbd(21, 77).

gausime rezultatą - 7. Užklausa buvo vykdoma šitaip:

  • taisyklė dbd(Sk1, 0) nepatvirtinta, nes antrasisskaičius atėjo ne 0, o 77, paieška tęsiama.
  • antrojoje taisyklėje A=77, B=56 (21 mod 77 = 56), siunčiama nauja užklausa dbd(77, 56).

  • taisyklė dbd(Sk1, 0) ir vėl nepatvirtinama, nes antrasis skaičius ne 0, o 56.
  • antrojoje taisyklėje A=56, B=21, siunčiama nauja užklausa dbd(56, 21).

  • taisyklė dbd(Sk1, 0) ir vėl nepatvirtinama, nes antrasis skaičius ne 0, o 21.
  • antrojoje taisyklėje A=21, B=14, siunčiama nauja užklausa dbd(21, 14).

  • taisyklė dbd(Sk1, 0) ir vėl nepatvirtinama, nes antrasis skaičius ne 0, o 14.
  • antrojoje taisyklėje A=14, B=7, siunčiama nauja užklausa dbd(14, 7).

  • taisyklė dbd(Sk1, 0) ir vėl nepatvirtinama, nes antrasis skaičius ne 0, o 7.
  • antrojoje taisyklėje A=7, B=0 (14 mod 7 = 0), siunčiama nauja užklausa dbd(7, 0).

  • taisyklė dbd(Sk1, 0) ir patvirtinama (dbd(7, 0)) ir atspausdinamas skaičius 7 (atsakymas).