Scala – Tail Recursive(Rekürsif) Function

Scala içerisinde yazdığımız recursive(rekürsif/öz yinemeli) kodların yazılış biçimleri ve sonuç verme biçimlerinde değişiklikler yaparak kodlarımızı daha uygun ve daha fazla hata vermeden çalışmasını sağlıyabiliriz. Bunlardan en önemlisi yazılmış olan recursive kodun tail recursive haline getirilmesidir.

Şimdi bunun neden önem teşkil ettiğine değinelim basit bir faktoriyel hesaplama recursif koduna bakalım. Bu koddan da görülebileceği üzere 10 sayısının faktöriyelini çok rahat bir biçimde hesaplayabilmektedir. Fakat 30000’i hesaplamayı denersek StackOverFlow hatasını alacağızdır.

 def factorial(n:Int):Int = {
    if(n <= 1) 1
    else{
       n * factorial(n-1)
    }
  }
  println(factorial(10))

Bu hatanın sebebi her bir önceki fonksiyon frame’inin devam ettirilmesidir. Daha iyi cümleler ile anlatılacak olursak, return kısmında yer alan n*factorial(n-1) ifadesi, bir önceki fonksiyonun sonucunun hesaplana bilmesi için bir sonrakinin sonucunun hesaplanmasının zorunlu olduğu anlamına gerekmektedir. Buda fonkisyonun tamamlanmadığını ve daha işi bitmediği için fonksiyonun halen yaşadığı anlamına gelir ve stack’imizi çokca doldurur.

Bu problemin ortadan kaldırılması için accumulator adlı bir değişken kullanılmaktadır. Aşağıda yer alan kodda verildiği gibi factorial fonksiyonu içerisinde yeni bir fonksiyon oluşturulmuş ve bu fonksiyonun yardımıyla accumulator ile fonksiyonun bitmesi için bir başka değeri beklemesi engellenmiş. Bu sayede fonkisyon için aynı frame üzerinden bellek dolmadan işlem yapılabilmektedir.

  def factorial(n:Int):Int ={
    @tailrec
    def factorialInner(x:Int,accumulator:Int):Int ={
      if( x<= 1) accumulator
      else factorialInner(x-1,x*accumulator)
    }
    factorialInner(n,1)
  }

@tailrec Anatosyonu IDE tarafından bu algoritmanın tailrec olup olmadığını kontrol etmesini saglamaktadir, böylelikle algoritma tail recursive değil ise hata alabiliriz. Aşağıda yine bir tail recursive asal sayı bulma kodu var.

  def isPrime(number:Int):Boolean = {
    @tailrec
    def isPrimeHelper(i:Int,number:Int,last: Boolean):Boolean ={
        if(!last) false
        else if(i > Math.sqrt(number)) true
        else isPrimeHelper(i+1,number,number % i != 0)
    }
    isPrimeHelper(3,number,true)
  }