Algoritma - Recursive algorithm

Naber yapraam nasılsın? benim durum aynı değişen bişi yok. Sıradan amk. Kafamı bulandırıp derslerimi engellediği için içkide içmiyorum artık. Bakalım sonumuz nolucak

Bugün yapraam sana Recursive(özyinelemeli) algoritma türünden bahsedicem. Recursive algoritmalar, halletmesi gereken işleri bölebileceği en küçük parçaya kadar bölüp sonra tekrardan toplayan algoritmalardır. Şimdi tabi pek bişey anlamamış olabilirsin. Ama anlıcaksın yapraam merak etme.

Recursive mantığı methodun içinde tekrardan kendisini çağırmasından ibarettir. Basit bir örnek vermek gerekirse;

Misal 1'den 4'e kadar olan sayıları toplatan bir algoritma yazalım. Bunu for döngüsüyle rahatlıkla yazabiliriz. Eğer bu şekilde yaparsak iterative olur. Peki recursive ile nasıl yaparız.

Önce fikir sahibi olmanız açısından bir çizimim var. Daha sonrada örnek kodu koyucam;

Şimdi napıyoruz burda ?
      girilen değer '1' olana kadar hep method içinde sayının 1 eksiğiyle methodu tekrardan çağırıyoruz. n değerimi 1 olduğu zamanda toplayarak sayıları ilk methodumuza kadar geri döndürüyoruz.

Şimdide içerdeki gerekli kodları gireyim.

Public Static Void main(String args[]){

  int x = Sum(4);  // Methodumuzu çağırıyoruz

  println(“Sum: ” + x); // Sonrada methodumuzdan dönen değeri(1+2+3+4) yazdırıyoruz.

} /* end-main */

Peki methodun içinde ne var ?

Static int Sum(int n){

  int partialSum = 0; // teker teker sayıları toplayacağımız integer, değişken

  if (n == 1) return 1; // eğer sayı 1 ise toplayarak dönmeye başla

  partialSum = Sum(n-1);// burda n değerimiz 1 olana kadar sayımızı 1 azaltarak method içinde                                                  //method çağırıyoruz

  return partialSum + n; // en son method(n'in 1 olduğu)'dan başlayarak toplaya toplaya ilk                                       //methodumuza dönüyoruz. eğer ilk methoddaysak değeri main methoda döndürüyoruz

}

Bilmem anlatabildim mi yapraam? okadar uğraştım resim fln çizdim amk. sizde biraz anlamaya çalışın.

Neyse genel mantık olarak recursive algoritması budur. Arkadaşlar, dostlar, gardaşlar, Recursive algoritması son derece güçlü ve hızlı bir türdür, bir çok sıkıntılı durumda hayat kurtarır bu yüzden bu algoritma türünü iyi irdelemeniz lazım. Bunun için bir kaç örnek daha yazıcam buraya. Ama bu sefer resim fln çizemem amk. Sadece mantığını yazıp örnek kodu koyucam.

İlk örneğimiz bir değerin kuvvetini yazdıran bir recursive algoritma olsun. 

Önce işin mantığını kavrayalım. Algoritmamız napıcak ? girilen değeleri önce en ilk kuvvet olan 1'e kadar açıcak ondan sonrada sayıyı çarpa çarpa geri döndürücek. Eğer sayının kuvveti 0 ise 1 değerini geri döndürücek.

Main method yazmama gerek olmadığını düşünüyorum.

double Power(double a, int n){

  double partialResult; // yine tabi parçalı bir sonuç değişkeni koyalım. teker teker çarpması için

  if (n == 0) return 1; // eğer sayımızın kuvveti 0 ise 1 değerini döndür

  else if (n == 1) return a; // eğer sayımızın kuvveti 1 ise sayımızı döndür.

  partialResult = Power(a, n-1); // işte burda methodu çağırıyoruz. n değeri 1 olana kadar method //içinde tekrar tekrar method açıyor ve sonunda n 1 olunca sayımızı döndürmeye başlıyor.

//dönen sayıyıda parçalı çarpım işlemimize eşitliyor.

  return partialResult*a;  // son olarakda sayımızla parçalı çarpımımızı kuvvet kadar çarpıp methodları

çarparak teker teker kapatıyor. ve geri döndürüyor.

}

Kapiş ? Bence anladın yapraam. Sadece biraz daha dikkatli incelemen gerekiyor.

Son örneğimizde fibonacci sayılarından gelsin madem amk.

Fibonacci sayıları bildiğiniz gibi bir sayı dizisidir, ama nasıl bir sayı dizisidir, bir sayının kendinden 

önceki sayıyla toplamının kendinden sonraki sayıya eşit olduğu bir sayı dizisidir. Yani;

0,1,1,2,3,5,8,13 ... diye giden sayı dizileri işte

Örneğin 40. fibonacci sayısını bulan bir algoritma yazalım. 

ilk iki örnek için ne var bunda amk ben bunu for döngüsüyle flnda 2 dakkada yazarım fln diyebilirsin.

Hadi yapraam yiyosa bunu yaz forla amk. Bunda sike sike recursive algoritma kullanman gerekli.

Neyse gelelim methodumuza, Ne demiştik? fibonacci dizisinde bir sayı kendisinden önceki 2 sayının toplamına eşittir dimi. Genel mantık olarak bunu alırsak çok rahat bir şekilde işin içinden çıkarız.

int Fibonacci(int n){

  if (n == 0) return 0; // eğer n değeri 0 ise hiç kurcalama n değerini döndür.

  if (n == 1) return 1; // eğer değerimiz 1 ise  1 döndürerek bir üstteki methoda çık

  return Fibonacci(n-1) + Fibonacci(n-2); /* şimdi genç bu bölümü iyi kavraman lazım gördüğün gibi burda 2 defa method çağırıyor. Önce değer 1 olana kadar n sayısını küçültüyor. n sayısı 1 olduktan sonra 1 değerini döndürüp n'in 2 olduğu bir üst methoda çıkıyor. sonra ikinci duruma geçiyor yani Fibonacci(n-2) durumuna. Burdada n = 2'ydi n-2'den 0 değeryile yine bir alt methoda iniyor. ordan 0 değeriyle geri dönüyor ve sonuçta 1 + 0  değerini alıp bir üst duruma geçiyor ve aynı işlemleri tekrarlıyor. */

} 

İnşallah anlatabilmişimdir. Biz 40. fibonacci sayısını istediğimiz için toplamda 300.000.000'dan fazla kez işlem yapılır. 

Bu recursive muhabbetini şimdilik burda bitiriyorum. Bir sonraki yazımdada yine recursivden faydalanarak linear ve binary searh algoritmalarından bahsedicem. Sizleri öpüyorum. Kendinize iyi bakın. Banada sevabına bi manita ayarlayın ya.