Yazılım

Örnekler ile Özyinelemeli Fonksiyon (Recursive Fonksiyon) Mantığı

Örnekler ile Özyinelemeli Fonksiyon (Recursive Fonksiyon) Mantığı

 

Bilgisayar mühendisliği öğrencilerinin en iyi kullanabildiği ve en güçlü programlama araçlarından biri özyineleme (recursion) kavramıdır. Özyineleme hem matematik hem bilgisayar biliminde çok önemli bir yere sahip olan bir problem çözme yöntemidir. Programlama dillerinde yazım hatalarının (syntax) denetlenmesinde ve veri yapılarında liste ve ağaç yapılarında tanımlanan temel işlemlerle arama ve sıralama algoritmalarının (quicksort, binarysort, heapsort) geliştirilmesinde etkin bir biçimde özyineleme yöntemi kullanılır. Özyinelemeli Fonskyion (Recursive Fonksiyon) kısaca kendi kendini çağırarak problemi adım adım azaltarak çözen fonksiyonlardır. Bu fonksiyonları daha iyi anlamanız açısından sizlere birkaç örnek ile anlatacağım.

1)Faktöriyel Fonksiyonu

Matematik ve istatistik çalışmalarında faktöriyel fonksiyonu önemli bir yere sahiptir ve verilen pozitif bir n tamsayısının 1 ile n arasındaki bütün tam sayılarla çarpımı olarak ifade edilir. Sıfır sayısının faktöriyeli 1’dir ve 4! = 4*3*2*1 ile hesaplanır.

0! = 1

1! = 1

2! = 2*1

3! = 3*2*1

4! = 4*3*2*1

Bu durumda pozitif bir n sayısının faktöriyeli aşağıdaki biçimde tanımlanabilir.

  • Eğer n == 0 ise n! = 1
  • Eğer n > 0 ise n! = (n)*(n-1)*(n-2)*(n-3)*…*3*2*1

Bu tanıma göre görebileceğiniz üzere problemi adım adım azalan bir yapıya çevirdik. Problemin çözümünün kodlamasını yaparken recursive fonksiyon yazacağımızı artık daha net bir şekilde görebiliyoruz.

Faktöriyel hesabının Recursive Fonksiyon yöntemi kullanılarak C dilinde kodlanması:

int faktöriyel_hesapla(int n) {

if (n == 0)

return 1;

else

return n* faktöriyel_hesapla(n-1);

}

2)Fibonacci Serisi

Özyinelemeli tanıma en uygun örneklerden birisi ise Fibonacci sayılarıdır. Bu sayılar aşağıdaki gibi sıralanmaktadır.

{0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 …}

Dizinin her elemanı kendisinden önceki iki elemanın toplamı olacak şekilde elde edilir.

  • Eğer n == 0 ya da n == 1 ise fib(n) = n
  • Eğer n >= 2 ise fib(n) = fib(n-2) + fib(n-1)

Bu tanımdan da görebileceğiniz gibi problemin çözümünü yine adım adım azaltarak elde ettiğimiz bir yapıya dönüştürdük. Bu yapıyı da en basit şekilde özyinelemeli fonksiyon yöntemi kullanarak çözebiliriz.

Fibonacci Serisi’nin Recursive Fonksiyon yöntemi kullanılarak C dilinde kodlanması:

int fibonacci_serisi (int n) {

if (n == 0 || n == 1)

return 1;

else

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

}

3)İkili Arama (Binary Search)

Elemanları küçükten büyüğe sıralanmış bir diziyi ele alalım. Bu dizide bir elemanın aranması için bir algoritma yazılacaktır. Dizi sıralı bir dizi olduğundan öncelikle dizinin ortasındaki elemanı bulup, aranan eleman bu ortadaki elemandan küçükse dizinin sol tarafında; büyükse sağ tarafında arama işlemine devam edilecektir. Yani sol tarafta ortadaki eleman bulunacak ve büyüklük küçüklük karşılaştırmasına tek eleman kalıncaya kadar aynı işlemler sol yarı dizide ya da sağ yarı dizide devam ettirilecektir. Çözümün tanımından özyinelemeli bir çözüm olduğu anlaşılmaktadır. Burada olduğu gibi, bir problemi her parçası orijinal problemin aynısı olan küçük parçalara bölerek çözme tekniğine böl ve yönet (divide and conquer) denir. Burada bu küçük parçaları kendi kendisini çağırarak çözebilen özyinelemeli bir algoritma tasarlanmış oldu.

İkili Arama (Binary Search) Recursive Fonksiyon yöntemi kullanılarak C dilinde kodlanması:

int binary_search (int dizi[], int x, int a, int b) {

if (a > b)

return -1;

c = (a + b) / 2;

return (x == dizi ? c : x < dizi ? binary_search(dizi, x, a, c-1) : binary_search(dizi, x, c+1, b));

}

Başa dön tuşu