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