tus0.gif (69 bytes)
 

ELEKTRONINĖS KNYGOS

tus0.gif (69 bytes)

Gintautas GRIGAS
PROGRAMAVIMAS PASKALIU

8. REKURSIJA

Pasaulis nuolat atsinaujina. Vaikai atkartoja tėvus.

Rekursija – tai atkartojimas. Funkcija arba procedūra gali kreiptis į save pačią ir tuo pačiu atkartoti savo pačios veiksmus vėl nuo pradžios, tik su kitais parametrais. Toks atkartojimas vadinamas rekursija.

Rekursija yra ir paprasta, ir sudėtinga. Paprasta dėl to, kad ja dažnai vartojama matematikoje, kai jos pagalba labai paprastai ir akivaizdžiai apibrėžiamos priklausomybės tarp dydžių. Sudėtinga dėl to, kad dažnai sunkiau suvokti, kaip tuos dydžius rasti, kad jie tenkintų tas priklausomybes.

8.1. Rekursinės funkcijos

Programuojant visada stengiamasi didesnį uždavinį skaidyti į mažesnius arba sudėtingesnį paversti keliais paprastesniais.

Veiksmų sudėtingumas kartais priklauso nuo duomenų. Pavyzdžiui, faktorialą galima apibrėžti šitaip:

n!= 1,               jei n = 1,
     (n – 1)! ·n,    jei n > 1.

Jei pradinis duomuo lygus vienetui, tai jau pats apibrėžimas pateikia rezultatą. Taigi vienetas yra pats paprasčiausias pradinis duomuo, skaičiuojant faktorialą.

Jeigu pradinis duomuo didesnis už vienetą, tai jo faktorialas išreiškiamas kita, paprastesne operacija – daugyba ir ... faktorialu, bet jau vienetu mažesnio skaičiaus. Taigi iš karto rezultato negauname. Tačiau, toliau taikydami antrąją faktorialo apibrėžimo dalį, faktorialą išreiškiame vis ilgesnės skaičių eilės sandauga:

n!=
= (n – 1)! · =
= 3! ·... ·(n – 1) ·n =
= 2! ·3 ·... ·(n – 1) ·n =
= 1! ·2 ·3 ·... ·(n – 1) ·n =
= 1 ·2 ·3 ·... ·(n – 1) ·n.

36 paveiksle grafiškai pavaizduota, kaip einama link vieneto. Kai pasiekiame vienetą, eilėje lieka vien skaičiai ir juos galime sudauginti. Dauginame iš kairės į dešinę. Taigi dabar eile einame priešinga kryptimi – į dešinę nuo vieneto.


36 pav. Skaičiaus n faktorialo išreiškimas sandauga 1·2·3·...·(n-1)·n

Jau esame sudarę faktorialo skaičiavimo algoritmą (žr. 6.2.3 užd.), kuriame skaičiaus n faktorialą išreiškėme skaičių nuo 1 iki n sandauga. Jau žinojome, kad faktorialas yra natūraliųjų skaičių sandauga, o kompiuteriui pavedėme tik juos sudauginti, t. y. atlikti antrąją uždavinio dalį – eiti nuo 1 iki n. Turint funkcijas, galima kompiuteriui pavesti ir pirmąją uždavinio dalį – „išsiaiškinti“, ar faktorialas yra skaičių sandauga. Tam pakanka faktorialo apibrėžimą užrašyti programavimo kalbos žymenimis:

function f (n: integer): integer;
begin
   if
n = 1 then f := 1
              else f := f(n -1)*n
end;

Funkcija ypatinga tuo, kad jos programoje yra kreipinys į ją pačią, kaip ir faktorialo apibrėžime – vėl faktorialas. Funkcijos ir procedūros, kuriose yra kreipinių į jas pačias, vadinamos rekursinėmis.

Pateikiame pavyzdžių.

1 pavyzdys. Kėlimą laipsniu galima apibrėžti šitaip:

an = a, jei n = 1,
an-1 ·a, jei n > 1.

Užrašome rekursinę kėlimo laipsniu funkciją:

function laipsnis (a, n: integer);
begin
    if
n = 1 then laipsnis := a
               else laipsnis := laispnis(a, n-1)*a
end;

2 pavyzdys. Fibonačio skaičių seka yra tokia:

1, 1, 2, 3, 5, 8, 13, 21, ...

Jos pirmieji du nariai lygūs vienetui, o bet kuris tolesnis narys lygus dviejų prieš jį einančių narių sumai. Taigi n-tasis narys F(n) apibrėžiamas šitaip:

          1,                            jei n = 1,
F(n) = 1,                            jei n = 2,
         F(n – 1) + F(n – 2),    jei n > 2.

Šį apibrėžimą išreiškiame funkcija:

function fib (n: integer): integer;
begin
   if
(n = 1) or (n = 2) then fib := 1
                               else fib := fib(n-2)+fib(n-1)
end;

Fibonačio sekos n-tajam nariui apskaičiuoti reikia dviejų prieš jį einančių narių – dviejų skaičių. Todėl reikalingi du atramos taškai – du skaičiai, kurie nurodyti apibrėžime (1 ir 2) ir į kuriuos atsiremia rodyklės 37 paveiksle.


37 pav. Fibonačio skaičių radimo schema

Kaip matome, rekursinę funkciją sudaryti labai paprasta – reikia tik matematinį jos apibrėžimą užrašyti programavimo kalbos žymenimis.

Kreipinys į funkciją iš jos vidaus išreiškia tos funkcijos veiksmų kartojimą. Tuo rekursinė funkcija panaši į ciklą. Ji, kaip ir ciklas, turi būti baigtinė.

3 pavyzdys. Duota nebaigtinė rekursinė funkcija

function ff (x: integer): integer ;
begin
   if
x = 0 then ff := 1
              else if x < 0 then ff := ff(x-1)
                                 else ff := (x+1)
end;

Kai x < 0, iš funkcijos vidaus kreipiamasi į funkciją ff su vis mažesniu parametru; kai x > 0, kreipiamasi su vis didesniu parametru. Savaime suprantama, kad x niekada nebus lygus nuliui, todėl visą laiką kreipiniai į funkciją kartosis. Vadinasi, ši funkcija yra baigtinė tik tada, kai x = 0.

Parašius rekursinę funkciją, visada reikėtų įsitikinti, ar ji baigtinė.

Uždaviniai

8.1.1. Skaičiaus 2 n-tąjį laipsnį galima apibrėžti šitaip:

2n = 1,             jei n = 0,
       2n-1 ·2,     jei n > 0.

Parašykite rekursinę funkciją pagal šį apibrėžimą.

8.1.2. Duota rekursinė funkcija:

function x (a, b: integer): integer;
begin
   if
b >= a then x := 0
                else x := x(a-b, b) + 1
end;

Kokios šių kreipinių reikšmės:

a) x(9, 4),
b) x(9, 5),
c) x(29, 2)?

Kokią aritmetinę natūraliųjų skaičių operaciją apibrėžia ši funkcija?

8.1.3. Šiame skyrelyje pateikta funkcija f apibrėžta kaip natūraliųjų skaičių faktorialas. Kas
         atsitiktų, jeigu kreipinio f(x) parametras x būtų neigiamas skaičius? Ką reikėtų
         pakeisti funkcijos apraše, kad f(x) būtų lygus 1, kai x £ 0?

8.1.4. Natūraliųjų skaičių seka apibrėžiama šitaip:

a1 = 1,
a2n = an ,
a2n+1 = an + an+1 .

Parašykite rekursinę funkciją n-tajam sekos nariui an rasti.

8.1.5. Didėjančios aritmetinės progresijos pirmasis narys yra neigiamas, paskutinis narys
         yra n, o skirtumas d. Reikia rasti šios progresijos teigiamų narių kvadratų sumą.
         Parašykite dvi funkcijas šiam uždaviniui spręsti: rekursinę ir ne rekursinę.

8.1.6. Vadinamasis dvigubas faktorialas apibrėžiamas šitaip:

f!! = 1×3×5×...×n,   kai n nelyginis skaičius
      2×4×6×...×n,   kai n lyginis skaičius

Parašykite rekursinę funkciją skaičiaus n dvigubam faktorialui rasti.

8.2. Rekursinių funkcijų veiksmai

Rekursines funkcijas atlieka kompiuteris, o programuotojas privalo jas taisyklingai užrašyti. Todėl jis gali ir nežinoti, kokiais paprastesniais veiksmais kompiuteris jas išreiškia. Tačiau, analizuojant painesnes situacijas, ieškant klaidų programose, programuotojui kartais pravartu žinoti, kaip kompiuteris atlieka rekursines funkcijas. Apie tai pakalbėkime plačiau.

8.1. skyrelyje sudarytą faktorialo funkciją įjungsime į programą:

program rekursija;
function f (n: integer): integer;
   begin
      if
n = 1 then f := 1
                  else f := n*f(n-1)
   end;
begin
  
write(f(1));
   writeln;
   write(f(2));
   writeln;
   write(f(3))
end.

Išnagrinėsime, kaip atliekami trys programos kreipiniai į faktorialo funkciją.

Primename, kad funkcijos kintamiesiems neskiriama vietos atmintyje ir neatliekami funkcijos veiksmai tol, kol į ją nesikreipiama.

Programa rekursija pirmą kartą kreipiamasi į funkciją f atliekant sakinį write(f(1)). Tai galima įsivaizduoti taip: vietoj kreipinio f(1) į sakinį rašoma funkcija f (38 pav.), jos kintamiesiems priskiriama vieta atmintyje. Nagrinėjama funkcija f turi tik vieną kintamąjį – parametrą n. Jam paskirta atmintis 38 paveiksle pavaizduota mažyčiu stačiakampiu. Po kreipimosi į funkciją į tą atminties vietą įrašoma tikroji parametro reikšmė, šiuo atveju – skaičius 1. Toliau atliekami funkcijos veiksmai, šiuo atveju – sąlyginio sakinio šaka po žodžio then. Funkcijos vardui f priskiriama vieneto reikšmė. Pasiekus funkcijos veiksmų pabaigą rodantį žodį end, funkcijos reikšmė perduodama kreipiniui, o pačiai funkcijai ir jos kintamiesiems skirta vieta atmintyje panaikinama. Šiuo atveju funkcija f nesikreipia į save, todėl ji atliekama taip, kaip ne rekursinė.

 

 

38 pav. Funkcijos f(1) reikšmės skaičiavimas. Plonesnėmis linijomis (su rodyklėmis galuose) parodytas duomenų persiuntimas, storesnėmis – veiksmų eiga

 
Antrasis kreipinys į funkciją f yra sakinyje write(f(2)). Dabar , ir atliekama sąlyginio sakinio šaka po žodžio else (39 pav.). Čia vėl kreipinys į funkciją f. O jeigu yra kreipinys, tai į jo vietą įrašomas tos funkcijos aprašas, paskiriama vieta tos funkcijos kintamiesiems. Taip sukuriamas naujas, antrasis, funkcijos f egzempliorius, visiškai nepriklausantis nuo pirmojo (39 pav.). Antrojo funkcijos f egzemplioriaus faktinis parametras lygus vienetui, todėl atliekama pirmoji sąlyginio sakinio šaka. Taip apskaičiuojama antrojo egzemplioriaus funkcijos reikšmė. Ji perduodama į pirmąjį egzempliorių ir ten įrašoma vietoj kreipinio. Atmintyje panaikinamas antrasis funkcijos egzempliorius. Dabar, kai vietoj kreipinio į funkciją f pirmajame egzemplioriuje yra įrašyta reikšmė (vienetas), apskaičiuojama reiškinio reikšmė (2 * 1= 2), ji priskiriama pirmojo egzemplioriaus funkcijos vardui ir perduodama į pagrindinę programos dalį. Kompiuterio atmintyje panaikinamas ir pirmasis funkcijos egzempliorius.

 

 

 

 

 

39 pav. Funkcijos f(2) reikšmės skaičiavimas. Sukuriami du funkcijos egzemplioriai

 

Atlikus paskutinį programos sakinį

write(f(3))

iš naujo sukuriami trys funkcijos f egzemplioriai (40 pav.), po to funkcijos rastos reikšmės grąžinamos į jų kreipinius ir visi funkcijos egzemplioriai pašalinami iš kompiuterio atmintinės atvirkščia tvarka, negu ten jie buvo įrašyti (pirma – trečias, po to – antras ir paskui – pirmas).

Bendru atveju, kai funkcijos f parametras yra n, bus sukuriama n funkcijos egzempliorių (41 pav)..

 
40 pav. Funkcijos f(3) reikšmės skaičiavimas. Sukuriami trys funkcijos egzemplioriai



41 pav. Kai skaičiuojama f(n), sukuriama n funkcijos egzempliorių

Kiekvienas funkcijos egzempliorius turi savus kintamuosius su sava kompiuterio atmintinės sritimi jų reikšmėms saugoti. Dėl to rašant rekursines funkcijas naudinga iš funkcijos iškelti visus nebūtinus kintamuosius.

Pavyzdys. Natūraliųjų skaičių seka apibrėžiama šitaip:

a1 = x,
a2 = y ,
an = an-1 + an-2 .

Parašysime rekursinę funkciją n-tajam sekos nariui an rasti. Paprasčiausias sprendimas būtų toks:

function narys (n,                { ieškomo nario nr. }
                        x,                { pirmasis narys }
                        y: integer     { antrasis narys } ): integer;
begin
   if
n = 1
     then narys := x
     else if n = 2
        then narys := y
        else narys := narys(n-1, x, y) + narys(n-2, x, y)
end;

Seka panaši į Fibonačio seką. Skiriasi tik pirmieji du nariai. Jie yra nėra konstantos. Todėl kreipinyje į funkciją juos reikia pateikti kaip funkcijos parametrus. Tačiau toliau, einant gilyn į rekursiją, jų reikšmės nesikeičia. Todėl juos galima iškelti iš funkcijos ir naudoti kaip globaliuosius kintamuosius. Todėl reikia dviejų funkcijų. Į vieną (ne rekursinę) funkciją su visais trimis parametrais kreipiasi programa, o ši funkcija kreipiasi į kitą jos viduje esančią rekursinę funkciją, turinčią tik vieną parametrą.

function narys (n,             { ieškomo nario nr. }
                        x,             { pirmasis narys }
                        y: integer  { antrasis narys } ): integer;
   function nar (n: integer): integer;
   begin
      if
n = 1
         then nar := x
         else if n = 2
             then nar := y
             else nar := nar(n-1, x, y) + nar(n-2, x, y)
   end;
begin
  
narys := nar(n)
end;

8.3. Rekursinės funkcijos pritaikymo pavyzdys: didžiausio bendro daliklio uždavinys

Norėdami tiksliai suformuluoti, kokie reikalavimai keliami funkcijai, pirmiausia užrašysime jos antraštę:

function dbd (x, y: integer): integer;

Laikykime, kad abu parametrai yra neneigiami. Pirmiausia aptarkime ypatingus atvejus: vienas iš parametrų lygus nuliui, abu parametrai lygūs nuliui. Jeigu vienas parametras lygus nuliui, tai didžiausiu bendru dalikliu laikysime kitą parametrą, nelygų nuliui. Jeigu abu parametrai lygūs nuliui, tai bendras jų daliklis – kiekvienas nelygus nuliui skaičius. Susitarkime, kad tokiu atveju funkcijos reikšmė lygi nuliui.

Dabar jau galime aiškiai suformuluoti uždavinį: reikia sudaryti dviejų neneigiamų skaičių funkciją didžiausiam bendram dalikliui rasti. Jeigu abu skaičiai lygūs nuliui, tai funkcijos reikšmė turi būti lygi nuliui. Jeigu vienas parametrų lygus nuliui, tai funkcijos reikšmė turi būti lygi kitam nelygiam nuliui parametrui.

Taigi nulis yra „atramos“ taškas, nuo kurio galime pradėti rašyti funkcijos veiksmus:

if (x = 0) and (y = 0) then bdd := 0
   else if x = 0 then bdd := y
      else if y = 0 then bdd := x
         else ...

Funkcijos pradžią jau turime. Tačiau liko pati sunkiausia dalis, kuri turi būti po žodžio else.

Pritaikykime didžiausio bendro daliklio savybę: dviejų skaičių didžiausias bendras daliklis lygus mažesniojo skaičiaus ir liekanos, gautos didesnįjį skaičių padalijus iš mažesniojo, didžiausiam bendram dalikliui:

dbd(30, 18) = dbd(18, 30 mod 18) = dbd(18, 12).

Toliau remdamiesi šia taisykle, gauname:

dbd(18, 12) = dbd(12, 6) = dbd(6, 0).

Taigi skaičiai, kurių didžiausią bendrą daliklį reikia rasti, nuolat mažėja. Galų gale vienas iš jų tampa lygus nuliui. O tada jau žinome, kaip rasti bendrą daliklį.

Šiuos veiksmus užrašę programavimo kalba ir juos prijungę prie ankstesnių, gauname šitokią rekursinę funkciją:

function dbd (x, y: integer): integer;
                     { x >= 0, y >= 0 }
begin
   if
(x = 0) and (y = 0) then dbd := 0
     else if x = 0 then dbd := y
        else if y = 0 then dbd := x
           else if x >= y then dbd := dbd(x mod y, y)
                                else dbd := dbd(y mod x, x)
end;

Dabar pamėginkime patikrinti ir patobulinti funkciją dbd.

Pirmos trys sąlyginio sakinio šakos apima visus atvejus, kai bent vienas pradinis duomuo lygus nuliui. Tai faktiškai tos pačios skyrelio pradžioje nagrinėtos sąlygos, tik užrašytos Paskalio kalbos žymenimis, taigi yra teisingos.

Bandykime patobulinti parašytą programos dalį. Atidžiai išnagrinėję tris pirmąsias sąlyginio sakinio eilutes, galime jas pakeisti viena eilute:

if (x = 0) or (y = 0) then dbd := x + y

Norint įsitikinti, kad šia viena eilute išreikšti tie patys veiksmai, kaip ir trimis ankstesnėmis, reikia įrodyti, kad abiem atvejais gaunama ta pati rezultato dbd reikšmė, esant bet kokiems pradiniams duomenims. Įrodoma:

1. Kai (x = 0) and (y = 0) = true, tai pirmu atveju atliekamas sakinys dbd := 0. Antro atvejo sąlyga (x = 0) or (y = 0) tenkinama ir atliekamas sakinys dbd := 0. Taigi abiem atvejais gaunamas tas pats rezultatas.

2. Kai x = 0 ir y ¹ 0, pirmu atveju atliekamas sakinys dbd := y. Antru atveju sąlyga tenkinama, ir atliekamas sakinys dbd := x + y. Kadangi x = 0, tai šis sakinys ekvivalentus sakiniui dbd := y. Taip matome, abiem atvejais gaunamas tas pats rezultatas.

3. Kai y = 0 ir (x ¹ 0), kintamuosius x ir y sukeitę vietomis, gauname jau įrodytą antrą atvejį.

Taigi funkcijos aprašą galima sutrumpinti:

function dbd (x, y: integer): integer;
                     { x >= 0, y >= 0 }
begin
   if
(x = 0) and (y = 0) then dbd := x + y
      else if x >= y then dbd := dbd(x mod y, y)
                           else dbd := dbd(y mod x, x)
end

Dabar patikrinsime dvi paskutines sąlyginio sakinio šakas. Abiejų šakų didesnysis skaičius (x arba y) dalijamas iš mažesniojo. Į šias šakas patenkama tol, kol nė viena kintamųjų x ir y reikšmė nelygi nuliui. Naujame kreipinyje į funkciją dbd didesnioji kintamojo reikšmė pakeičiama tų kintamųjų dalybos liekana. Teigiamųjų skaičių dalybos liekana yra visada mažesnė už dalinį ir daliklį. Taigi kintamųjų x ir y reikšmės nuolat mažės ir pagaliau kuriame nors kreipinyje viena jų pasidarys lygi nuliui. Tada bus patenkama į pirmąją šaką, o ten kreipinių nėra. Vadinasi, ši rekursinė funkcija baigtinė.

Dabar įsitikinkime, kad rezultatas teisingas.

Kai bent vienas funkcijos parametras lygus nuliui, tai atliekama pirmoji sąlyginio sakinio šaka. Rezultatas bus x + y, kuris, kaip jau anksčiau įrodėme, yra bendras didžiausias skaičių x ir y daliklis.

Kai nė viena kintamųjų x ir y reikšmė nelygi nuliui, atliekama antra arba trečia sąlyginio sakinio šaka. Kreipiantis į funkciją dbd, skaičių x ir y bendras didžiausias daliklis pakeičiamas naujų skaičių bendru didžiausiu dalikliu, kuris abiejose šakose sutampa su ankstesnių skaičių bendru didžiausiu dalikliu. Kai bent vienas skaičių virsta nuliu, patenkama į pirmąją šaką, ir gaunamas teisingas rezultatas.

Kadangi dalybos su liekana rezultatas – liekana – visada mažesnė už daliklį, tai operacijos x mod y rezultatas visada mažesnis už y. Todėl galime dar suprastinti funkciją:

function dbd (x, y: integer): integer;
begin
   if
(x = 0) and (y = 0) then dbd := x + y
       else dbd := dbd(y mod x, x)
end

Laikykime, kad x <= y. Tada, kreipiantis į funkciją dbd iš jos vidaus, pirmuoju parametru reikia rašyti y mod x, o antruoju x, nes y mod x < x. Kai į funkciją dbd kreipiamasi pirmą kartą iš programos pagrindinės dalies, gali būti netenkinama sąlyga x <= y. Tada pirmą kartą funkcija atliekama beveik tuščiai – pagal ją tik sukeičiamos parametrų x ir y reikšmės vietomis. Toliau sąlyga x <= y visada bus tenkinama. Kai x > 0, o y = 0, pirmiausia taip pat bus sukeičiamos vietomis parametrų reikšmės. Todėl funkciją galima dar suprastinti:

function dbd (x, y: integer): integer;
begin
   if
x = 0 then dbd := y
              else dbd := dbd(y mod x, x)
end

Įrodėme, kad paprasčiausio funkcijos varianto rezultatas teisingas. Kitus funkcijos variantus gavome iš ankstesnių, pakeitę kai kurias programos dalis trumpesnėmis, ekonomiškesnėmis, bet ekvivalenčiomis programos dalimis. Todėl, jei teisingas pradinis funkcijos variantas, turėtų būti teisingi ir kiti jos variantai.

Kad įsitikintume, jog nepadarėme klaidų, keisdami ir perrašinėdami funkciją, reikėtų ją patikrinti su keliomis būdingiausiomis parametrų reikšmėmis:

dbd(0, 25);
dbd(25, 0);
dbd(30, 75);
dbd(13, 13);
dbd(75, 30);
dbd(0, 0);

Pamėginkite atlikti funkciją su nurodytais kreipiniais ir įsitikinsite, kad rezultatai šitokie:

25   25   15   13   15   0

Norint išbandyti funkciją kompiuteriu, reikia sudaryti ją gaubiančią programą. Kad iš karto patikrintume funkciją, esant įvairiems pradiniams duomenims, programoje reikia parašyti daug kreipinių arba vieną kreipinį cikle.

Pateikiame programą, turinčią šešias pradinių duomenų poras:

program bandymas;
   var a, b, j: integer;
   function dbd (x, y: integer): integer;
      begin
          if
x = 0 then dbd := y
             else dbd := dbd(y mod x, x)
      end;
begin
   for
j := 1 to 6 do
      begin
        
read(a, b);
         writeln(a: 7, b: 7 , dbd(abs(a), abs(b)): 7)
      end
end.

Programos pradiniai duomenys gali būti ir neigiami. Tada randamas jų absoliutinių didumų (modulių) didžiausias bendras daliklis.

Uždaviniai

8.3.1. Parašykite rekursinę funkciją dviejų natūraliųjų skaičių didžiausiam bendram dalikliui
         (dbd) rasti, remdamiesi tokiomis dbd savybėmis:

dbd(a, b) = a, jei a = b;
dbd(a, b) = dbd(a, b – a), jei a < b;
dbd(a, b) = dbd(a – b, b), jei a >b.

8.3.2. Pradiniai duomenys – skaičių, nelygių nuliui, seka. Sekos pabaigoje – nulis.
         Vartodami funkciją dbd, sudarykite programą visos sekos skaičių didžiausiam
         bendram dalikliui rasti. Jeigu seką sudaro tik vienas nulis, tai jo didžiausias bendras
         daliklis lygus nuliui, jeigu nelygus nuliui skaičius ir nulis, – tai didžiausias bendras
         daliklis lygus pirmajam skaičiui.

8.3.3. Sudarykite funkciją dviejų skaičių mažiausiam bendram kartotiniam rasti. Pavartokite
         ją visų skaičių nuo 1 iki 10 mažiausiam bendram kartotiniam rasti.

8.3.4. Sudarykite loginę funkciją, patikrinančią, ar du duoti skaičiai yra tarpusavyje pirminiai.

8.4. Rekursinės procedūros

Rekursinės gali būti ne tik funkcijos, bet ir procedūros.

1 pavyzdys. Pradiniai duomenys – skaičių seka. Jos ilgis nežinomas. Paskutinis sekos skaičius – nulis, o visi kiti skaičiai nelygūs nuliui. Reikia sudaryti programą pradiniams duomenims rašyti atvirkščia tvarka. Pavyzdžiui, jeigu pradiniai duomenys yra skaičiai

3   25   115  400   13   0

tai kompiuteris turi rašyti

0   13   400   115   25   3

Sudarome programą su rekursine procedūra atb:

program atbulai;
   procedure atb;
       var x: integer;
   begin
     
read(x);
      if x <> 0 then atb;
      writeln(x)
   end;
begin
  
atb
end.

Procedūra atb yra be parametrų. Pagrindinę programos dalį sudaro vienintelis sakinys – kreipinys į procedūrą atb. Procedūra atb turi tik vieną kintamąjį x. Kiek kartų bus kreipiamasi iš procedūros atb į ją pačią, priklausys nuo pradinių duomenų sekos ilgio. Išnagrinėkime atskirus atvejus.

Kai seką sudaro tik vienas nulis (nepamirškime ir tokio atvejo!), pirmuoju sakiniu perskaitoma x reikšmė, antrasis sakinys – kreipinys į procedūrą atb neatliekamas (nes x = 0), trečiuoju sakiniu spausdinamas nulis. Štai ir atlikta procedūra, kartu ir visa programa.

Kai seką sudaro du skaičiai (ir x2 = 0), pirmasis jų priskiriamas kintamajam x. Sąlyga tenkinama, todėl pakartotinai kreipiamasi į procedūrą atb. Antrajame procedūros egzemplioriuje bus perskaitytas antrasis skaičius – nulis. Sąlyga netenkinama, ir iš antrojo procedūros egzemplioriaus nebebus kreipiamasi į procedūrą atb. Trečiuoju sakiniu bus išspausdinta kintamojo x reikšmė (nulis), ir skaičiavimas grįš į pirmąjį procedūros egzempliorių. Čia bus atliekamas trečiasis sakinys write(x) ir rašoma pirmojo pradinio duomens reikšmė (prisiminkime, kad ji buvo priskirta pirmojo procedūros egzemplioriaus kintamajam x dar prieš kreipiantis į antrąjį egzempliorių).

Nesunku įsitikinti, kad n skaičių sekai sukuriama procedūros atb n egzempliorių. Spausdinimo sakinys yra po kreipinio į procedūrą, todėl skaičiai spausdinami atvirkščia tvarka negu buvo kreiptasi į procedūra (atvirkščia tvarka negu skaičius perskaitė kompiuteris).

Uždaviniai

8.4.1. Duota programa:

program ra;
   procedure s (n: integer);
   begin
      
write(n);
       if n > 10 then s(n-1)
          else writeln;
       write(n: 4)
   end;
begin
s(15) end.

Ką parašys kompiuteris, atlikęs programą?

8.4.2. Paaiškinkite, kaip atliekamos šitokios procedūros:

a)
procedure xxx (n: integer);
begin
   if
n = 5 then write('*')
              else xxx(n-1)
end

b)
procedure yyy (b: boolean);
begin
    if
b then yyy(true)
end

8.5. Rekursija ir ciklas

Rekursinių funkcijų ir procedūrų veiksmai gali būti kartojami be ciklo. Jeigu kreipinys į funkciją arba procedūrą yra jos pačios viduje, tai reiškia, kad ten bus pakartotinai atliekami jos pačios veiksmai, tik galbūt jau su kitais duomenimis. Taigi rekursija išreiškia veiksmų kartojimą.

3.7 skyrelyje sakėme, kad bet kokiai veiksmų atlikimo tvarkai aprašyti pakanka trijų valdymo struktūrų: sakinių sekos, sąlyginio sakinio ir ciklo. Ciklą pakeitę rekursija, gauname kitą trejetą – sakinių seką, sąlyginį sakinį ir rekursiją. Šiomis konstrukcijomis (valdymo struktūromis) taip pat galima išreikšti kiekvieną veiksmų atlikimo tvarką.

Kadangi rekursija yra abstraktesnė už ciklą konstrukcija, ją labiau mėgsta teoretikai. Ciklus vertina praktikai, nes juose konkrečiau nurodoma veiksmų atlikimo tvarka. Programos su ciklais būna ekonomiškesnės negu tuos pačius veiksmus aprašančios rekursinės programos.

Teoriškai kiekvieną rekursiją galima pakeisti ciklu, ir atvirkščiai.

1 pavyzdys. Bendro didžiausio daliklio funkcijoje (žr. 8.3 skyr.) rekursiją pakeiskime ciklu.

Nagrinėjame antrąjį, šiek tiek patobulintą, bet dar negalutinį rekursinės funkcijos variantą Kadangi iš anksto neaiškus veiksmų kartojimo skaičius, tai vartosime while ciklą. Rekursinės funkcijos pradžioje užrašytą sąlygą

(x = 0) or (y = 0)

galima laikyti ciklo pabaigos sąlyga. Vadinasi, ciklas turi vykti tol, kol ši sąlyga netenkinama. Todėl ciklo antraštė turėtų būti šitokia:

while not (x = 0) or (y = 0) do

Pritaikę loginių reiškinių pertvarkymo taisykles (žr. 3.2 skyr.), sąlygą (tuo pačiu ciklo antraštę) suprastiname:

while (x <> 0) and (y <> 0) do

Dabar galime užrašyti ir visą funkciją:

function dbd (x, y: integer): integer;
begin
   while
(x <> 0) and (y <> 0) do
      if
x >= y then x := x mod y
         else y := y mod x;
   dbd := x + y
end;

Rekursinę funkciją pavyko suprastinti išbraukus ir sąlyginį sakinį, nes jame galima buvo lengvai sukeisti vietomis parametrus. Šią funkciją taip pat prastinti neverta, nes, norint kintamųjų reikšmes sukeisti vietomis, reikėtų naujo kintamojo ir daugiau prieskyros sakinių.

Rekursiją pakeisti ciklu nesunku ir kituose šiame skyriuje pateiktuose pavyzdžiuose, išskyrus paskutinį (procedūra atb, žr. 8 .4 skyr.). Mat jame rekursija vartojama ne tik veiksmams kartoti, bet ir pradinių duomenų sekai įsiminti ir išsaugoti – kiekviename procedūros atb egzemplioriuje įsimenama vis naujo pradinio duomens reikšmė. O kol kas nenagrinėjome kitokių būdų didesniam duomenų kiekiui įsiminti.

Ką tikslingiau naudoti – rekursiją ar ciklą, – priklauso nuo konkretaus uždavinio ir jo algoritmo. Universalių pasirinkimo receptų nėra. Kiekvienu konkrečiu atveju reikia naudoti vaizdžiausias ir ekonomiškiausias išraiškos priemones.

8.6. Sprendimų paieška grįžties metodu

Tik nedaugelio uždavinių sprendimus galima išreikšti formulėmis arba lygtimis. Dažnai sprendinio tenka ieškoti bandymų keliu.

Pateiksime gana universalų uždavinių sprendimo metodą, kuris dažnai vadinamas grįžimo arba bandymų ir klaidų metodu. Sistemingai bandomi visi galimi sprendimų keliai ir visada atrandamas sprendinys, jeigu tik jis egzistuoja arba, peržiūrėjus visus galimus kelius, nustatoma, kad sprendinio nėra (gali būti ir tokių atvejų).

Metodo esmę pailiustruosime „laipiojimu“ po medį (42 pav.).

 

 

 

 

42 pav. Medis, po kurį laipioja kirminas, norėdamas surasti obuolį

 

Tarkime, kad po medį laipioja kirminas. Nuo žemės (taško A) jis nori pasiekti obuolį, kabantį ant šakos galo I. Kol kirminas lipa kamienu iki taško B, jam viskas aišku, nes kito kelio nėra. Taške B medis šakojasi. Kurią šaką pasirinkti? Mat kirminas, būdamas viename šakos gale, dar nemato, kas yra kitame jos gale (obuolys, tuščias šakos galas ar naujas išsišakojimas). Todėl jis nežino, kurį kelią (kurią šaką) pasirinkti. Belieka išbandyti visus kelius (ištyrinėti visas šakas). Tam, kad būtų sistemingai išbandyti visi keliai, sutarkime, kad kirminas visada pasirenka kairiausią dar neišbandytą šaką. Taigi jis eina į tašką C, po to į tašką D, po to – į tašką E. Toliau nebėra kur eiti (ir obuolio nėra). Tenka grįžti atgal į tašką D. Dabar iš taško C kirminas eina jau į tašką G (kelias CD jau išbandytas). Iš G į H – ir vėl tuščias šakos galas. Tenka grįžti į tašką H. Toliau kirminas eina į tašką I ir sėkmingai pasiekia obuolį. Uždavinys išspręstas.

Jo sprendinys – kelias ABCGI. Šis kelias buvo nutiestas palaipsniui, išbandant šitokias kelio atkarpas:

A
AB
ABC
ABCD
ABCDE
ABCD
ABCDF
ABCD
ABC
ABCG
ABCGH
ABCG
ABCGH

Atkreipiame dėmesį, kad tada, kai sužinoma, kad nueita klaidingu keliu (pasiekiamas tuščias šakos galas), uždavinį spręsti pradedama ne iš naujo, o daromas tiktai vienas žingsnis atgal ir iš čia vėl bandome eiti. Jeigu žengus žingsnį atgal pasirodo, kad ir čia nebėra naujų nenagrinėtų kelių, tai žengiamas dar vienas žingsnis atgal ir t.t., kol pasiekiamas taškas, iš kurio eina bent vienas dar neišbandytas kelias. Jeigu sugrįžtama į pradinį taškas ir iš jo nebėra naujų kelių, tai reiškia, kad išbandyti visi galimi keliai ir nė vienas nepasiekė tikslo. Tokiu atveju uždavinys sprendinio neturi.

Laipiojimas po medį yra akivaizdi sprendimo paieškos grįžties metodu iliustracija. Metodą galima taikyti daugeliui uždavinių spręsti. Tai kelio paieška labirinte, teksto perskaitymas šachmatų žirgo ėjimu, šachmatų figūrų išdėstymas lentoje taip, kad būtų tenkinamos tam tikros sąlygos ir daugelis kitų uždavinių, kurie dėl sprendimo paieškos sudėtingumo dažnai pateikiami kaip galvosūkiai.

Pavyzdys. Sudarysime šachmatų lentos apėjimo žirgu algoritmą. Šachmatų žirgo ėjimu turi būti pereinami visi lentos langeliai taip, kad kiekviename langelyje žirgas pabuvotų tik vieną kartą. Pradinė žirgo padėtis – apatinis kairysis langelis. Pirmiausia pateiksime algoritmo eskizą. Procedūros eiti veiksmus detalizuosime vėliau.

const n = 8;                                   { lentos dydis }
type koord = 1..n;                           { koordinatės }
        lenta = array [koord, koord] of integer;
procedure žirgas (var len: lenta);
    var i, j: koord;
          viskas: boolean;
    procedure eiti (i: integer;            { ėjimo numeris }
                     x, y: koord;                { pradinė žirgo padėtis}
         var len: lenta;
               viskas: boolean);              { užpildyta visa lenta }

Ėjimai surašomi į lentą (t.y. į masyvą len). Jie pradedami nuo langelio (x, y) – laikoma, kad ten jau yra žirgas. Ėjimai numeruojami pradedant skaičiumi i. Kintamojo viskas reikšmė true, jeigu sprendinys egzistuoja (t.y. po vieną kartą žirgas apsilankė visuose langeliuose) ir false priešingu atveju.

begin                      { žirgas }
   viskas := false;
   for i := 1 to n do
       for
j := 1 to n do
          
len[i, j] := 0;
   len[1, 1] := 1;           { pradinė žirgo padėtis }
   eiti (2, 1, 1, len, viskas);
end;

Algoritme užrašyti veiksmai pakankamai aiškūs. Visa uždavinio sprendimo esmė slypi procedūroje eiti, kuri turi užpildyti ėjimų eilės numeriais visus likusius lentos langelius. Detalizuokime šią procedūrą.

Sudaryti procedūrą, kuri iš karto išspręstų visą uždavinį (t.y. užpildytų visus lentos langelius žingsnių numeriais), sunku. Todėl uždavinį suprastinsime panaudodami rekursiją. Sudarysime procedūrą, kuri darytų tik vieną žirgo ėjimą ir užpildytų tik vieną lentos langelį. Tam, kad būtų daromas naujas ėjimas, procedūra turi vėl kreiptis pati į save. Kreipiniai tęsiasi tol, kol užpildoma visa lenta arba prieinama aklavietė, t.y. lenta dar neužpildyta, o eiti nėra kur. Tada grįžtama atgal ir bandoma eiti nauju keliu.

Kai žirgas nėra lentos krašte, galimi ėjimo variantai, parodyti paveiksle. Taigi, jeigu pradinė žirgo padėtis – masyvo len langelis len[x, y], tai bet kuri (viena iš aštuonių) nauja padėtis parodyta 43 paveiksle.

43 pav. Šachmatų žirgo ėjimai

len[x + cx[k], y + cy[k]]

Čia k - varianto eilės numeris, o masyvų cx ir cy reikšmės nustatomos iš pateikto brėžinio:

cx[1] := 2; cy[1] := 1;
cx[2] := 1; cy[2] := 2;
cx[3] := -1; cy[3] := 2;
cx[4] := -2; cy[4] := 1;
cx[5] := -2; cy[5] := -1;
cx[6] := -1; cy[6] := -2;
cx[7] := 1; cy[7] := -2;
cx[8] := 2; cy[8] := -1;

Kai žirgas yra arčiau lentos krašto, tai variantų skaičius mažesnis – reikia atmesti tuos variantus, kai bent vienas (arba abu) masyvo len indeksai nepatenka į atkarpą 1..n (t.y. nurodo langelį už lentos ribų).

Pateikiame procedūrą eiti.

procedure eiti (i: integer;                { ėjimo numeris }
                       x, y: koord;              { pradinė žirgo padėtis }
                       var len: lenta;
                             iskas: boolean); { užpildyta visa lenta }
   const nn = 64;                             { lentos dydis n“ n }
            cx: array [1..8] of integer =
                                (2, 1. -1, -2, -2, -1, 1, 2);
            cy: array [1..8] of integer =
                                (1, 2, 2, 1, -1, -2, -2, -1);
   var k: 0..8;                                  { varianto numeris }
         u, v: integer;                          { nauja žirgo padėtis }
begin                                            { eiti }
   k := 0;
   repeat
     
k := k + 1;
      u := x + cx[k];
      v := y + cy[k];
      if (u >= 1) and (u <= n) and (v >= 1) and (v <= n)
          then                                     { naujos koordinatės dar patenka į lentą }
             if len[u, v] = 0
                 then                              { langelis dar tuščias }
                    begin
                       
len[u, v] := i;
                        if i < nn then
                           begin
                             
eiti (i+1, u, v, len, viskas);
                              if not viskas then len[u, v] := 0
                           end
                           else
viskas := true
                    end
   until
viskas                                   { užpildyta visa lenta }
         or (k = n);                               { peržiūrėti visi variantai }
end;                                                { eiti }

Belieka procedūrą įdėti į programą.

Pastaba. Masyvo ir įrašo tipų konstantas turi tik Turbo Paskalis. Jeigu jų nenaudotume, vietoj konstantų cx ir cy reikėtų aprašyti tokio pat tipo kintamuosius ir programos (procedūros) pradžioje jiems priskirti pradines reikšmes.

Panašiai rekursinės programos sudaromos ir kitiems uždaviniams, kuriuos sprendžiant variantai peržiūrimi tol, kol gaunamas bent vienas sprendinys, arba nustatoma, jog sprendinys neegzistuoja. Jeigu norima rasti visus galimus sprendinius, tai po pirmojo rasto sprendinio skaičiavimai nebaigiami – ieškoma kitų sprendinių tol, kol randami visi.

Abiejuose pavyzdžiuose pateikėme rekursinius algoritmus. Šios rūšies uždaviniams rekursija gerai tinka, kadangi paieškos požiūriu visi kelio taškai yra lygiaverčiai. Todėl nuėjus į naują tašką tolesnį kelią galima ieškoti vėl pagal tą patį algoritmą. Tačiau galima parašyti ir nerekursinius algoritmus – juk kiekvieną rekursinį algoritmą galima išreikšti ne rekursiniu (iteraciniu) algoritmu. Tiktai nenaudojant rekursijos tektų parašyti šiek tiek daugiau veiksmų – ir tuos, kuriuos neišreikštiniu pavidalu atlieka rekursija per procedūrų (arba funkcijų) parametrų perdavimo mechanizmą.

Praktikos darbas

8.6.1. Kelio paieška labirinte. Labirintas vaizduojamas n x m (n, m – nelyginiai skaičiai) langelių dydžio lenta (44 pav.) Vieni langeliai juodi, kiti – balti. Vaikščioti galima tik baltais langeliais horizontaliai arba vertikaliai. Eiti įstrižai negalima. Kelias prasideda nuo centrinio langelio. Todėl jis turi būti baltas. Reikia rasti bent vieną kelią iš centrinio langelio į lentos kraštą.

Parašykite algoritmą keliui rasti ir apipavidalinkite jį rekursine procedūra. Po to procedūrą įjunkite į programą ir išbandykite kompiuteriu.


a


b

44 pav. 9 x 21 langelių dydžio labirintas. Pavaizduoti du variantai: a) tuščias tik centrinis langelis (iš jo išėjimo nėra) ir b) yra daugiau tuščių langelių (iš centrinio langelio yra du išėjimai – abu į viršų)

E Ankstesnis puslapis

3 Turinys

Kitas puslapis F

tus0.gif (69 bytes)