Rekursija

Arbatos pakellis, ant kurio pavaizduotas toks pats arbatos pakelis, ant kurio aišku pavaizduotas ir vėl tas pats arbatos pakelis ... (begalinė rekursija)

Rekursija yra funkcijos 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. Šis atkartojimas vadinamas rekursija. Funkcijos kuriose yra kreipinių į jas pačias, vadinamos rekursinėmis.

Rekursinis funkcijos apibrėžimas

Pavyzdžiui, faktorialą galima apibrėžti kaip sandaugą:

$n!=\prod _{k=1}^{n}k\!$

arba, rekursiniu būdu:

$n!=\left\{{\begin{matrix}1,&{\mbox{jei }}n{\mbox{=0}}\\n\cdot (n-1)!,&{\mbox{jei }}n\geq {\mbox{1}}\end{matrix}}\right.$

Programavime tai užrašoma funcija, kurioje yra kreipinys į ją pačią:

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

Panašiai, dvejeto kėlimą nurodytu laipsniu (2ⁿ) galima taip pat užrašyti rekursija:

$n!=\left\{{\begin{matrix}1,&{\mbox{jei }}n{\mbox{=0}}\\2\cdot n,&{\mbox{jei }}n\geq {\mbox{1}}\end{matrix}}\right.$

„Laipiojimo po medį“ uždaviniai

Rekursija gerai tinka įvairiems „laipiojimo po medį“ algoritmas, kuomet kiekviename žingsnyje bandomi įvairūs variantai, kiekvienam variantui rekursiniu būdu kreipiantis į sprendimo ieškančią funkciją. Ši funkcija grąžina arba „sprendimas rastas“ arba „sprendimas nerastas“. Šiuo atveju rekursinėje funkcijoje paprastai būna keletas kreipinių į save pačią, po vieną kiekvienam bandomam kelio tęsiniui.

Sužinojus jog nueita klaidingu keliu (galimų tolimesnių žingsnių nebėra, o sprendimas irgi nerastas), daromas tiktai vienas žingsnis atgal ir iš čia vėl bandome eiti kitaip. Jei visi variantai jau mėginti, žengiamas dar vienas žingsnis atgal ir t. t., kol pasiekiamas taškas, iš kurio veda bent vienas dar neišbandytas kelias. Jei taip galop sugrįžtama į pradinę uždavinio padėtį, sprendimo nėra.

Įprastiniai tokio tip uždaviniai yra kelio paieška labirinte, lentos apėjimas šachmatų žirgu, šachmatų figūrų išdėstymas lentoje taip, kad būtų tenkinamos tam tikros sąlygos kiti uždaviniai, kurie dėl sprendimo paieškos sudėtingumo dažnai pateikiami kaip galvosūkiai.

Rekursija ir ciklas

Bet kokiai programai užrašyti pakanka trijų valdymo struktūrų: sakinių sekos, sąlyginio sakinio ir ciklo. Tačiau galimas ir kitas trejetas: sakinių seka, sąlyginis sakinys ir rekursiją. Kadangi rekursija yra abstraktesnė už ciklą, ją labiau mėgsta teoretikai. Ciklus labiau vertina praktikai, nes juose konkrečiau nurodoma veiksmų atlikimo tvarka. Programos su ciklais yra ekonomiškesnės negu tuos pačius veiksmus aprašančios rekursinės programos, nes kiekvieną kartą funkcijai kreipiantis į save pačią tenka ir vėl išskirti atmintį ten esantiems kintamiesiems bei perduodamiems parametrams. Ciklo pakartojimui papildoma atmintis nebūtina.

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

Šaltiniai

Vikižodynas