16 MAYIS 2017
CUMARTESİ
13.24
Ayrık Matematik - Recursion

Recursion, temel olarak bir fonksiyonun sürekli kendisini tekrar etmesi anlamına gelir diyebiliriz. Bazı durumlarda soruya ve soruna bağlı olarak kendi kendini çağıran fonksiyonlar işlerimizi kolaylaştırdığı gibi hızlandırabilir de.. Bu sebeple çoğu alanda tercih sebebidir. Şimdi genel olarak bir kaç örnek üzerinden gidelim.

 

ÖRNEK

Faktöriyel hesabı yapan bir (recursive) uygulama gerçekleştirin.

İNCELEME

Programımız içerisinde kendi kendini tekrar eden bir yapı oluşturmamız isteniyor. Bu yapıyı oluştururken mantığı kavramaya çalışalım;

  • Kod Çalışma Koşulu: Eğer girilen n sayısı 1'den büyükse işlem gerçekleşecek ve fonksiyon kendisini çağıracak.
  • Kod Durdurma Koşulu: Eğer girilen n sayısı 0'a veya 1'e eşitse fonksiyon duracak.
  • Hata Koşulu: Eğer girilen n sayısı 0'dan küçükse hata verecek.

Öyleyse yapımızı kurabiliriz;

if ( n > 1 )
işlem gerçekleşsin ve fonksiyon tekrar etsin

else if ( n == 0 || n == 1 )
fonksiyon dursun

else
hata versin

ÇÖZÜM

int fact(int n) {
	int sonuc = 1;
	if(n>1) {
		sonuc = n*fact(n-1);
	} else if(n == 0 || n == 1) {
		return sonuc;
	} else {
		return 0;
	}
}

İNCELEME

Oluşturduğumuz kod yapısında aslında bir önceki incelememizde belirttiğimiz 3 koşulu girdik. Farklı olarak bir sonuc değişkeni oluşturduk ve bu değişkene faktöriyel hesabından elde dilen sonucu döndürdük. return işlemleri ile de bu fonksiyonumuzdan dışarıya ya girilen sayının faktöriyeli çıkacaktır ya da eğer sayı 0'dan küçükse 0 döndürülecektir.

ÇIKTI


Bir başka örneğe bakalım.


ÖRNEK

Üslü sayı işlemini recursive olarak yapan bir program yazın.

İNCELEME

Yazacağımız program için 2 adet girdimiz olacaktır.

  • taban
  • ust

Bu bilgileri kullanıcıdan istedikten sonra yapacağımız matematik işlemi;

return taban * fonksiyonAdi ( taban, ust-1 )

Şimdi çözüm aşamamıza geçelim ve sonrasında kodları inceleyelim.

ÇÖZÜM

int usluSayi(int taban, int ust) {
	if(ust <= 0) {
		return 1;
	} else {
		return taban * usluSayi(taban, ust-1);
	}
}

İNCELEME

Oluşturduğumuz kod yapısında taban ve ust değerlerini aldık. Eğer ust değeri 0'a eşit ve küçük ise 1 değerini döndürdük. Eğer değilse tabanı fonksiyonda üstü bir azaltarak kendisi ile çarptık.

ÇIKTI


Bir başka örneğe bakalım.


ÖRNEK

Linear Search işlemini recursive ile yapalım.

İNCELEME

Sırası ile tüm sayıları karşılaştırarak aranan değere eşit olup olmadığına baktırmamız gerekiyor. Bu işlemi yapmak için fonksiyona diziyi, aranan sayıyı, dizinin başlangıç değerini ve bitiş değerini göndermemiz gerekiyor. Dizinin bitiş değerini dizinin eleman sayısından bir düşük olarak göndermeliyiz. Çünkü diziler 0'dan başlıyor ve 10 elemanlı bir dizi varsayarsak 9. elemanda son buluyor.

Dizimiz: int dizi[10] = {1,5,10,15,20,22,24,32,50,125};

ÇÖZÜM

int linearSearch(int dizi[], int aranan, int baslangic, int bitis) {
	if(dizi[baslangic] == aranan) {
		return 1;
	} else if(baslangic == bitis) {
		return 0;
	} else {
		return linearSearch(dizi, aranan, baslangic+1, bitis);
	}
}

İNCELEME

Kodda klasik if else yapımızı oluşturup kontrollerimizi yaptık. İlk kontrolümüzde aradığımız değer varsa doğrudan 1 değerini döndürdük. Eğer yoksa başlangıç değerinin bitiş değerine eşitliğini sorguladık. Bu satır demek oluyor ki "Benim arama yaptığım başlangıç değerim bitiş değerime geldiyse ve hala bir şey döndürmediyse demek ki bu sayı benim dizimde yok". Son satırda ise baslangic değişkeninin bir arttırarak gönderme sebebimiz bir sonraki dizi elemanını karşılaştırmak içindir.

ÇIKTI


Bir başka örnek daha çözelim.


ÖRNEK

Binary Search işlemini recursive olarak yapalım.

İNCELEME

Bu işlemi yaparken ortanca değer alınıyor ve aranan değere eşit olup olmadığı kontrol ediliyor. Dizi sıralı geldiği için bir sonraki adımımızda bulunan ortanca değerin aranan değerden büyük veya küçük olup olmadığı kontrol ediliyor. Duruma göre fonksiyon yeniden çalıştırılıyor.

Dizimiz: int dizi[10] = {1,2,4,5,7,15,25,30,45,64};

ÇÖZÜM

int bSearch (int dizi[], int aranan, int baslangic, int bitis) {
	int mid = (baslangic+bitis)/2;
	
	if(baslangic > bitis) {
		return 0;
	} else {
	
		if(dizi[mid] == aranan) {
			return 1;
		} else if(dizi[mid] > aranan) {
			return bSearch(dizi, aranan, baslangic, mid-1);
		} else {
			return bSearch(dizi, aranan, mid+1, bitis);
		}
	
	}
	
}

İNCELEME

Kodda ilk aşamadan baslangic değerinin bitis değerinden büyük olup olmadığını kontrol ettirdik. Bu kontrolün amacı eğer böyle bir durum söz konusu ise "ben arama alanımı tamamladım" demek istiyorum. Ve buna rağmen hala aradığım değeri bulamadığım için 0 değerini döndürüyorum. Else kısmını komple incelersek ilk inceleme de bahsettiğimiz gibi dizimizin ortanca elemanının aranan değere eşit olup olmadığını kontrol ettiriyoruz. Yani bizim aradığımız değer bu mu? sorusunu soruyoruz. Eğer aradığımız değer dizinin ortanca elemanına eşit ise 1 döndürüyoruz. Eğer dizinin ortanca elemanı aranan değerden büyükse bu demek oluyor ki benim yeni bitiş değerim dizimin ortanca elemanın bir fazlası olmalı. Bu sayede arama alanımı küçültüyorum. Aynı şekilde dizinin ortanca elemanı aranan değerimden küçükse bu kez başlangıç değerimi ortanca değerin bir fazlası ile değiştiriyorum.

ÇIKTI


Ve son bir örnek daha çözelim.


ÖRNEK

Fibonacci dizisini recursive ile yazın.

İNCELEME

Fibonacci dizisi, her sayının kendisinden önceki sayı ile toplanması sonucu elde edilen dizidir. Bu işlem için girilen sayının 1 eksiği ile 2 eksiğini toplarsak bize istediğimiz adımdaki sayıyı verebilir.

ÇÖZÜM

int fibo(int sayi) {
	if(sayi < 2) {
		return sayi;
	} else {
		return fibo(sayi-1)+fibo(sayi-2);
	}
}

İNCELEME

Görüldüğü üzere sayı 2'den küçük olduğu müddetçe 1 değeri dönecektir. Örneğin biz 10 sayısını girdiğimizde program 9. ve 8. sayılara kadar tüm sayıları tek tek alacaktır ve toplayacaktır.Sonuç ise girdiğimiz satırdaki sayı olacaktır.

ÇIKTI

YORUMLAR 0
Bu konuya henüz kimse yorum yapmadı.
İlk yorumu sen yapmak ister misin?
YORUM BIRAK
Şuanda bu yoruma cevap yazıyorsunuz:
İptal Et