Uodeginė rekursija

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką

Uodeginė rekursija (angl. tail recursion) – rekursijos atvejis, kai rekursiją galima transformuoti į iteraciją (kompiliatorius gali optimizuoti į steko nenaudojančius veiksmus). Uodeginė rekursija kai kuriose programavimo kalbose (pavyzdžiui, Scheme) yra būtinas reikalavimas realizacijai. C kompliatoriai dažnai taip pat sugeba tai atlikti, tačiau būtinas optimizacijos įjungimas.

Principas[taisyti | redaguoti kodą]

Paprastai kviečiant funkciją, steke saugomas grįžimo adresas. Tačiau jeigu kreipinys į funkciją yra paskutinis veiksmas funkcijoje, ir funkcijos į kurią kreipiamasi argumentų dydis yra toks pats kaip funkcijos, iš kurios kreipiamasi, tuomet galima steke palikti anksčiau buvusią grįžimo funkciją, o dabartinės neįrašyti, taigi po kreipimosi, bus iš karto grįžtama į aukštesnę funkciją.

Pavyzdys[taisyti | redaguoti kodą]

Pavyzdžiai pateikti C kalba. Pirmoji funkcija, naudojanti paprastą rekursiją:

 int factorial(int n) {
   if (n == 0) {
     return 1;
   } else {
     return n * factorial(n-1);
   }
 }

Anksčiau pateikta funkcija nėra optimizuojama, kadangi paskutinis sakinys programoje yra ne kreipinys į funkciją, o daugybos veiksmas. Kompiliatorius nėra pakankamai gudrus, kad tai suprastų. Tačiau galima funkciją perrašyti taip:

 int factorial(int n, int m) {
   if (n == 0) {
     return m;
   } else {
     return factorial(n-1, n*m);
   }
 }

Tiesa, visus factorial(N) kreipinius reikia pakeisti į factorial(N, 1), arba naująją funkciją factorial apgaubti kita funkcija, kuri tai darytų automatiškai. Antrojo tipo funkcijos paskutinis sakinys yra kreipinys į funkciją su tokiais pačiais argumentais, tad steko vieta gali būti atlaisvinta prieš kreipinį.

Funkcijų perrašymas į šią formą kartais yra sudėtingas, tačiau dažnai tai vis tiek paprasčiau negu parašyti efektyvų nerekursinį problemos sprendimą.