tail recursion
-
programin, cevap olarak kendinin degisik argumanlarla cagirilmasini vermesidir. ornegin:
int
faktoryel2(int carpilacak, int carpim) {
if(carpilacak==0) return carpim;
else return faktoryel2(carpilacak-1, carpim*carpilacak);
}
int
faktoryel(int arg) {
return faktoryel2(arguman, 1);
}
"faktoryel2" fonksyonunda onemli olan, kendisini cagirdigi durumlarda, gelen cevabi hic manipule etmeden direk return etmesi. bu durumda faktoryel2 baska bir faktoryel2'yi cagirdiktan sonra, ilkini stack'te tutmanin geregi yoktur. sonucta ilk faktoryel2'nin cevabi cagirdigi kendi cocugu olan faktoryel2(hesaplanan_yeni_argumanlar)'in cevabi olacaktir. iyi bir derleyici tarafindan derlenmisse, program ikinci faktoryel2'i cagirip yeniden baslatmak yerine, sanki argumanlar degismis ve goto ile programin basina donulmus gibi bir program akisi yaratir. bu sayede fonkston istedigi kadar kendini cagirsin, stack bitmez. sonsuz dongu'ye girse bile stack overflow olmaz.
edit: yani olayin mantigi budur elbet ama bir cok derleyici bu optimizasyonu yapmaz. gcc'nin yapmadigini az once test edip onayladim, her bir cagri icin yeni stack yeri aciyor arkadas. -
scheme ile kod yazarken surekli kullanilan, genelde "breh breh breh, adamlar yapmis" tepkisiyle eslik edilen teknik.
(bkz: recurse ediyorum recurse ediyorum stack kuru kaliyor) -
c/c++ gibi dillerin tasarimlarindan oturu bu diller icin yazilmis compiler'lar isteseler dahi tail recursion'i optimize edemezler zira bu dillerde compiler sizin ne yapmak istediginizi bilemez.
-
kuyrugu yeniden lanetlemek.. bu kadar da duz ceviririm.
-
-
optimizasyonu f#'a ek olarak bizzat .net framework jit'i tarafından da uzun zamandır destekleniyormuş:
http://blogs.msdn.com/…ail-call-jit-conditions.aspx -
fonksiyonel programlamanin tuzu biberi.
(bkz: tail recursion is its own reward)
http://www.xkcd.com/1270/ -
(bkz: tail call optimization)
-
recursive fonksiyonlarda kodun aynı stack frame'i kullanmasını bu sayede stack overflow exceptionları alınmamasını sağlar.
-
aslinda tail call ayri tail call optimization ayri ve tail recursion da ayri basliklarda incelenmeli ve aciklanmalidir.
ekşi sözlük kullanıcılarıyla mesajlaşmak ve yazdıkları entry'leri
takip etmek için giriş yapmalısın.
hesabın var mı? giriş yap