Tail-Recursion fonksiyonu nedir? Neden kullanırız?

Armağan Ersöz —  10 Haziran 2014 — Yorum bırakın

Fonksiyonel programlama dillerinde yaygın teknik; fonksiyonları mümkün olabilecek en alt fonksiyonlara ayırarak problemi çözme yönündedir. Yineleme yani ” recursion” fonksiyonları da bu noktada en iyi çözümlerden biridir. Yineleme fonksiyonu bildiğimiz üzere kendi kendini çağıran fonksiyondur.

Fakat yineleme fonksiyonları performans açısından yavaştır. Sebebi ise; fonksiyonlar, kendini her çağırdığında bellekte yeni bir yer açılır ve bu tarz fonksiyonlar, çağrılar sonucunda dönen değerleri kullanarak hesaplama yaptığı için hesaplama yapılana kadar tüm parametreler ve dönüş değerleri bellekte tutulur. Daha açık bir şekilde ifade edersek; son yineleme de dahil olmak üzere tüm yinelemeler bir değer döndürdükten sonra hesaplama yapıldığı için tüm değerler işlem sonuna kadar bellekte tutulur.

Böyle bir yöntem kullanınca da bellek fazla kullanıldığı için “StackOverflowException” ile karşılaşmak kaçınılmaz oluyor.

Fakat gelin görün ki Scala yineleme fonksiyonlarının bellek sorununu “tail recursion” adlı bir teknikle çözmüş görünüyor. Bu teknik, geleneksel yinelemeden farklı olarak fonksiyonu çağırdıktan sonra hesaplamayı yapıyor ve o değerlerle tekrar fonksiyonu çağırıyor.

Klasik olarak konuyu karşılaştırmalı örnekler vererek anlatacağım.
Öncelikle, bir string’i ters çeviren geleneksel yineleme fonksiyonu yazıyoruz.

def reverse(s: String): String = {
if (s == null) return null
if (s.tail.isEmpty) return s
reverse(s.tail) + s.head
}

Şimdi de aynı işlemi yapan tail-recursion fonksiyonu yazıyoruz.

@scala.annotation.tailrec //Tail-recursion fonksiyonunun geleceğini haberdar ediyor.
def reverse_tail(s: String, r: String): String = {
if (s == null) return null
if (s.tail.isEmpty) return s.head + r
reverse_tail(s.tail, s.head + r)
}

Fonksiyonların bu hali ile farklarını anlayamayabilirsiniz. Ama adım adım nasıl bir çıktı ürettiğine bakarsak herşey daha da anlamlanacaktır.

Geleneksel yineleme fonksiyonunun çıktılarına bakarsak;

reverse("scala")
reverse("cala")+"s"
reverse("ala")+"c"+"s"
reverse("la")+"a"+"c"+"s"
reverse("a")+"l"+"a"+"c"+"s"
"a"+"l"+"a"+"c"+"s"
"alacs"

Tail recursion fonksiyon çıkıtısına bakarsak;

reverse_tail("scala","")
reverse_tail("cala","s")
reverse_tail("ala","cs")
reverse_tail("la","acs")
reverse_tail("a","lacs")
"alacs"

Çıktılardan anlaşılacağı üzere; tail-recursion kullanılan örnekte geleneksel örneğin aksine bellekte her çağrı için yeni bir yer açılması gerekmiyor. Dolayısıyla bir noktadan sonra belleği aşırı kullanım gibi bir sorun oluşmayacağı için StackOverFlowException ile karşılaşma ihtimali de ortadan kalkmış oluyor.

Sonuç olarak; tail-recursion fonksiyon tipi hesaplamayı adım adım yaptığı ve sona bırakmadığı için tüm değerleri bellekte tutmak zorunda kalmıyor.

Fakat ne yazık ki; her dil tail-recursion kullanılan fonksiyonları optimize edemiyor. Yani geleneksel yineleme ve tail-recursion arasından performans açısından bir fark oluşmuyor. Mesela hangilerinde yok derseniz Python ve Java diyebilirim. Son olarak, Fonksiyonel diller bu optimizasyonu yapabiliyor diye genelleyebiliriz. Umarım yararlı olmuştur. Recursive fonksiyon yazarken bundan sonra dikkat edilecek bir husus daha eklendi listeye.

İyi kodlamalar!

Yararlandığım kaynaklar:

View story at Medium.com

Armağan Ersöz

Armağan Ersöz

Posts Twitter

Genelde web uygulamaları geliştiren özgür yazılım destekçisi bir yazılımcı. Java, Spring ve JSF en sevdiği oyuncaklar. Biraz DBA'liğe meraklı. Kadıköylü. Şu an Avustralya'da yaşıyor.

No Comments

Be the first to start the conversation.

Yorum yapmak için