Merhaba arkadaşlar,

Bugün sizlere ilk başta anlaşılması zor gibi görünen recursion ın tam olarak nasıl çalıştığını anlatacağım. Bu yazıyı okuduktan sonra hangi problemle karşılaşırsanız karşılaşın, o problemi özyinelemeli olarak çözebilmek için gerekli olan bakış açısını kazanacaksınız.

Recursion ı anlamak için herhangi bir programlama dilinde bir tane temel fonksiyon kuralını bilmemiz çok önemlidir:

Kural 1. Herhangi bir fonksiyon(metot) yapacağı işlemi bitirdikten sonra, program fonksiyonun çağrıldığı satıra geri döner.

Peki program fonksiyonun çağrıldığı satıra nasıl geri döner?

Programlama dillerinde fonksiyonun çağrıldığı yerde fonksiyona gönderilen parametreler ve fonksiyonun çağrıldığı satır numarası arka planda ide tarafından stack de push() metodu kullanılarak depolanır. Fonksiyon işlemini bitirdikten sonra stack teki satır numarası sayesinde fonksiyonun ilk çağrıldığı satıra geri dönülür. Daha sonra bu satır değeri pop() metodu kullanılarak stack ten atılır.

Recursion ı anlamak için gerekli olan bu kuralı ilk önce recursive olmayan bir fonksiyon üzerinde ele alalım. Bu mantığı kavradıktan sonra, recursive fonksiyon örneklerimize geçeceğiz.

1. public static void main(String [] args) {

2. print();

3. System.out.println(“Hello Mars!”);

}

4. public static print() {

5. System.out.println(“Hello World!”);

}

Yukarıdaki kod örneğine baktığımızda program ilk önce 1. satırdan çalışmaya başlar. Birinci satırdan sonra program 2. satıra geçer ve burada print() fonksiyonu çağrılır. print() fonksiyonu çağrıldıktan sonra program 4. satıra geçer ve daha sonra 5. satıra geçer. Program 5. satıra ulaştığında ekrana Hello World! yazısını yazdırır. Daha sonra print() fonksiyonu işlemini tamamladığı için program print() fonksiyonundan çıkar. Sonrasında program print() fonksiyonunun çağrıldığı satır olan 2.satıra geri döner. Sonrasında program 3.satıra geçer ve ekrana Hello Mars! yazısını yazdırır.

Burada önemli olan nokta, fonksiyon işlemini tamamladıktan sonra çağrıldığı yer olan 2.satıra geri dönmesidir.(Kural 1)

Kural 1' in yukarıdaki örnekle iyi bir şekilde kavrandığını düşünüyorum. Şimdi klasik bir problem olan faktöriyel hesaplamayı Kural 1 i kullanarak recursive bir bakış açısıyla ele alalım.

1. public static void main(String [] args) {

2. int fact = factorial(4);

3. System.out.println(fact);

}

4. public int factorial(int n) {

5. if(n == 1) { // Base case

6. return 1;

}

7. else {

8. return n * factorial(n-1);

}

}

Yukarıdaki koda baktığımızda program 2. satıra geldiğinde factorial(4) fonksiyonu çağrılır ve program 4.satıra gider. Buradan 5. satırdaki if ifadesine girilmez çünkü n=4 tür. Bu yüzden program else kısmına girer ve burada geriye 4*factorial(3) satırı çalışır. Bu satırda fonksiyon kendini tekrardan çağırmış olur ve fonksiyonun başına yani 4.satıra tekrardan geri dönülür. Burada n=3 olduğu için program else kısmına girerek 3*factorial(2) satırı çalıştırılır. Sonrasında aynı mantıkla n=1 olana kadar fonksiyon kendini çağırmaya devam eder. n=1 olduğunda ise program if kısmına girer ve 6. satır çalıştırılarak geriye 1 sayısını geri dönerek factorial(1) fonksiyon işlemini tamamlamış olur. Şimdi fonksiyonların hangi satırlarda çağrıldığını çağrılma sıralarına göre ele alalım:

factorial(4) → 2. satırda çağrıldı. (int fact = factorial(4))

factorial(3) → 8. satırda çağrıldı. (4*factorial(3))

factorial(2) → 8. satırda çağrıldı. (3*factorial(2))

factorial(1) → 8. satırda çağrıldı. (2*factorial(1))

factorial(1) fonksiyonu 1 değerini geriye döndürerek işlemini tamamladığı için Kural1 i uygulayarak, factorial(1) in çağrıldığı yer olan 8.satıra geri dönmemiz gerekir. 8. satırda 2*factorial(1) ifadesi vardı. factorial(1) = 1 olduğu için geriye döndürülen değer 2*1 = 2 olur.

Sonrasında program 2 değerini factorial(2) nin çağrıldığı 8.satıra geri döner. 8.satırda 3*factorial(2) ifadesi vardı. factorial(2) = 2 olduğu için geriye dönülen değer 3*2 = 6 olur.

Daha sonra program 6 değerini factorial(3) ün çağrıldığı 8.satıra geri döner. 8.satırda 4*factorial(3) ifadesi vardı. factorial(3) = 6 olduğu için geriye dönülen değer 4*6 = 24 olur.

Daha sonrasında olarak program 24 değerini factorial(4) ün çağrıldığı yer olan 2. satıra döner. 2. satırda ise int fact = factorial(4) ifadesi vardı. factorial(4) = 24 olduğu için int fact = 24 olmuş olur.

Son olarak program 2. satırı çalıştırdıktan sonra 3. satıra gider ve ekrana 24 değerini yazdırmış oluruz. 3. satırdan sonra main metodu bittiği için programımız sona erer.

Yukarıda anlattığım işlemleri aşağıdaki recursion tree ye bakarak daha rahat bir şekilde anlayabilirsiniz:

Image for post

Recursive fonksiyonlarda fonksiyonun belirli bir durumda durmasını istediğimiz kısma “BASE CASE” denir.

Yukarıda farkettiyseniz fonksiyonu tekrardan çağırmadığımız tek kısım if(n==1) ifadesinin içerisidir. Burada return 1 ifadesi vardır. Eğer if(n==1) return 1 kısmı kodumuzda olmasaydı, fonksiyonumuz sonsuza dek kendini çağırmaya devam edecekti. Fonksiyonumuzun 1 değerinde durmasını sağlamak için “BASE CASE” i kodumuza ekledik.

Yukarıda faktöriyel koduna bakarak recursion tree oluşturduk. Peki herhangi bir recursion tree ye bakarak recursive bir fonksiyon nasıl yazabiliriz? Bu soruyu yanıtlamak için fibonacci sayı dizisinin recursion tree sine bakalım ve bu problem için birlikte java kodu yazalım.

Fibonacci kodunu yazmak için gerekli olan ilk kısım base case i belirlemektir. Peki biz fonksiyonumuzun hangi değerlere ulaştığında kendini çağırmasını durdurmak istiyoruz? Yukarıdaki şekile baktığımızda fib(1) ve fib(0) değerleri için fonksiyonumuz duruyor. fib(1) her seferinde geriye 1 değerini dönüyor, fib(0) ise geriye her seferinde 0 değerini dönüyor. Bu çıkarımlara bakarak fonksiyonumuzun base case kısmını yazabiliriz:

public int fib(int n) {

if(n == 0) // Base case 1

return 0;

else if(n==1) // Base case 2

return 1;

else

// Some code

}

Fibonacci fonksiyonumuzu tamamlamak için geriye kalan tek kısım fonksiyonun kendisini çağırma kısmıdır. Peki fonksiyonumuzu kaç kere çağırmamız gerekiyor?

ÖNEMLİ NOKTA: Herhangi bir recursion fonksiyonun içinde fonksiyonu n kere çağırırsak, recursion tree de her bir kökün(root) n tane çocuğu(child) olur.

Faktöriyel hesaplamada farkettiyseniz recursive faktöriyel metodunun içinde faktöriyel metodunu 1 kere çağırmıştık. Bunun sonucunda recursion tree de her bir kökün(root) 1 tane çocuğu(child) olmuştu. Fibonacci nin recursion tree sine baktığımızda ise her bir kökün 2 tane çocuğu var. Bu da demek oluyor ki fib fonksiyonunun içinde fib metodunu 2 kere çağırmamız gerekir. Matematiksel olarak fib(n-1) + fib(n-2) = fib(n) olduğu için programın else kısmında fib fonksiyonunu 2 kere çağırarak, fib(n-1) + fib(n-2) değerini geriye döndürmeliyiz.

Böylece recursive fib() fonksiyonunu aşağıdaki şekilde tamamlayabiliriz :

public int fib(int n) {

if(n == 0) // Base case 1

return 0;

else if(n==1) // Base case 2

return 1;

else

return fib(n-1)+fib(n-2);

}

İçeriğimi okuduğunuz için teşekkürler, sağlıcakla kalın.

Semih Ataman