Recursive - NonRecursive Functions

Merhaba,

     Bugun biraz teknik konulardan konuşuyor olucaz.Belki nette ufak tefek yazılımsal çözümler arayan arkadaşlara yardımcı olabilirim.En küçük örnek olarak bugün bir recursive fonksiyonun yani kendi kendini tekrar çağıran fonksiyonun verimliliği ile ilgili konuşalım.Bunun için en güzel örnek de Fibonacci dizisi olucaktır.Fibonacci dizisini duymamış olanlar için kısaca bahsedersek bir önceki sayı ve sıradaki sayının toplanmasıyla bir sonraki sayının oluşturulduğu sayı dizisidir yani 0 1 1 2 3 5 8 13 ... diye devam etmektedir.

Şimdi bazı fibonacci sayılarını bulmak için ufak bir algoritma yazalım hem recursive hemde non-recursive ve bunları karşılaştıralım.

Recursive Fibonacci algoritması Java implementasyonu aşağıdaki gibidir.

public static int Recursive_fibonacci(int n){
    if(n <= 1)
                return n;

     else
          return Recursive_fibonacci(n-1) + Recursive_fibonacci(n-2);

   }

Nonrecursive Fibonacci algoritmasın Java implementasyonu da aşağıdaki gibidir.

public static int Non_Recursive_fibo(int k){

   int sum;

   int result=1;

   int prev=0;

   for(int i =1 ; i < k ; i++){

                     sum = result + prev;

                     prev = result;

                     result = sum;

  }

    Aşağıdaki tabloda da çalışma zamanlarıyla ilgili test süreleri bulunuyor.

	Recursive Fibo	Non-Recursive Fibo
n = 10	12709 nanosec	4594 nanosec
n = 20	417462 nanosec	4594 nanosec
n = 30	11821715 nanosec	5083 nanosec

     Recursive fonksiyon küçük numaralar için non-recursive’e göre daha kısa sürede sonuç verirken büyük numaralar için ise çalışma zamanı daha hızlı büyüyerek uzun sürelerde sonuç vermeye başladı.N artarken recursive fonksiyonun çalışma zamanı diğerine göre daha hızlı büyüdüğü için büyük numaralarda verimsiz oldu.
     Recursive fonksiyon bize kolaylıklar sağlayabileceği gibi bazı durumlarda da verimsiz olabiliyor koşulları iyi değerlendirirseniz doğru algoritmayı seçebilirsiniz.