Uodeginė rekursija
Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
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.
[taisyti] 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 kreipiamąsi, 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ą.
[taisyti] 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); } }
Ankšč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 vistiek paprasčiau negu parašyti efektyvų nerekursinį problemos sprendimą.