Uodeginė rekursija

Uodeginė rekursija (angl. tail recursion) – rekursijos atvejis, kai rekursiją galima pakeisti ciklu (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 įjungimas.

Principas

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

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ą.

Šaltiniai

1. Paul E. Black, «tail recursion», in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 14 August 2008.