Özyineli Fonksiyonlar (Recursive Functions)

Yazan: Şadi Evren ŞEKER

Fonksiyonlar tekrarlama yapılarına göre temel olarak iki türlü düşünülebilir. Buna göre bir fonksiyonun içinde yine kendisinden bir parça bulunuyorsa bu fonksiyonlara özyineli (recursive) fonksiyon denilirken, fonksiyonun kendisini tekrar etmemesi durumunda döngülü (iterative) fonksiyon ismi verilir.
Teorik olarak bütün döngülü (iterative) fonksiyonlar özyineli (recursive) fonksiyon olarak yazılabilir (tersi de doğrudur).
Öreğin 1′den verilen sayıya kadar olan sayıları toplayan bir fonksiyonu hem özyineli hem de döngülü olarak yazalım:

//özyineli olarak:

int topla(int a){

  if(a==1)

    return 1;

  return a+ topla(a-1);

//döngülü olarak

int topla(int a){

  int toplam= 0;

  for(int i = 0 ;i

    toplam= toplam+a;

  return toplam;

Dikkat edilirse ilk foksiyonun içerisinde kendisini çağıran bir satır bulunmaktayken ikinci fonksiyonda çözüm bir döngü yardımı ile (for döngüsü) yapılmıştır.

Ekrana 1′den 10′a kadar olan sayıları bastıran kod (Fatih Bey’in sualine cevaben)

Örneğin ekrana 1′den 10′a kadar olan sayıları bastıran bir kod yazmak isteyelim. Kodu özyineli (recursive) bir fonksiyonla yazdıralım ve kullanıcı aslında ekrana kaça kadar basılmak istediğini fonksiyona parametre olarak geçirsin (bu soruda 10 olacak)

Aşağıdaki kodu ele alalım:

Yukarıdaki kodun çalışan hali aşağıda verilmiştir:

Görüldüğü üzere kod ekrana 1′den 10′a kadar olan sayıları bastırmıştır.

Burada ekrana bastırma işlemini yapan fonksiyon koddaki 4-8 satırlar arasında tanımlı olan f() fonksiyonudur. Fonksiyon bir n değerinden başlayarak ekrana anlık olarak n değerini bastırmış ve her adımda n-1 değeri ile fonksiyonu tekrar çağırmıştır.

Şayet yukarıdaki şekilde bir if kontrolü ile çağırmayı engellemek yerine her adımda kendisini tekrar çağırmasını isteseydik aşağıdaki şekilde kodu yazabilirdik:

Kodda görüldüğü üzere özyineli olarak fonksiyonun kendisini çağırması işlemi ve ekrana printf fonksiyonu marfietiyle yazma işlemi aynı sırada verilmiştir. Ancak fonksiyonun bitişini belirten if kontrolü, n değerinin 0 olması durumunda return 0; yaparak işlemi durdurmuştur.

Burada return 0 yapılmasının veya return 1234 yapılmasının bir önemi yoktur, fonksiyon herhangi birşey return ederek artık bittiğini belirtmektedir.

Yukarıdaki kod benzer şekilde return void yapacak halde yani integer bir değer döndürmeyecek halde yeniden yazılabilir:

Yukarıdaki kodun yeni halinde fonksiyonun döndürdüğü değer tipi int yerine void haline gelmiştir. Bunun sebebi aslında fonksiyonun geri değer döndürmüyor oluşudur. Ayrıca fonksiyondaki 6. satırda return teriminden sonra bir değer bulunmaz, yani sadece return edilir ve fonksiyon nihayete erer.

Yukarıdaki bu özyineli fonksiyonlarda 3 temel unsur her zaman dikkate alınmalıdır:

başlangıç değeri
bitiş değeri
adım değeri

Yukarıdaki basit 1′den 10′a kadar olan sayıları basan kodda başlangıç değeri 10 olarak kullanıcı tarafından veriliyor. Ayrıca özyineli devam işlemi 0′a ulaşınca bitiyor. Bunu kontrol eden bir if kodun ilk satırında bulunuyor. Kodun her adımında n-1 değeri fonksiyona yeniden veriliyor. Bu değer de adım değerini oluşturuyor.

Örneğin yukarıdaki fonksiyonu yine özyineli bir görüntü altında iteratif olarak yazabiliriz. Bu yazılış şekline geçiş tarzı şekli (continuation by passing style) ismi verilir:

Yukarıdaki kodun yeni halinde, 12. satırd bulunan f fonksiyonuna dikkat edilirse, 10′a kadar olan sayılar 1′den başlanarak basılsın diye iki ayrı parametre verilmiştir. Fonksiyonumuz i değerini her adımda arttırmakta ve n değerine eşit olunca durmaktadır. Durma işlemi yine bir önceki fonksiyonda olduğu üzere void değer return edilerek olmaktadır.

Yukarıdaki kod aslında iteratif bir koddur, bunun sebebi fonksiyonlardan herhangi birisinin çalışması için kendi içerisinden çağırdığı f(n,i+1) fonksiyonun çalışması beklenmemektedir. Ancak döngü ile yazılmış bir fonksiyondan da farkldır.

Ekrana Yıldızlar kullanılarak X harfi basan kod (Duygu Hanımın talebi üzerine ekliyorum)

Amacımız ekrana aşağıdaki şekilde bir X harfi basmak olsun:

*   *

* *

* *

*   *

Yukarıda görülen şekil kullanıcıdan 5 girişi için çizilen şekildir. Bizim amacımız bu şekli çizen bir kodu özyineli (recursive) fonksiyonlar marifetiyle ekrana çizdirmek.

Yukarıdaki şekil 2 boyutlu bir şekil olduğu için hem satır hemde sütun boyutlarında işlem yapmamız gerekiyor. Öncelikle satır boyutunda çözüm üretip sonra bu satır işlemini tekrarlayan bir işlemle şekli çizdirebiliriz.

Satırlara dikkat edilirse her satırda 2 yıldız ve 3 boşluk bulunuyor. Bu durum nxn boyutunda bir x harfi için n-2 boşluk ve 2 yıldız olarak formüllenebilir.

Yukarıdaki X harfinde dikkat edilirse bir karenin iki köşegeni * diğer değerler ise boşluk olarak çizilmiştir. Bu durumda karenin köşegenlerini nasıl bulacağımızı düşünürsek, satırları tutan bir i değişkeni ve sütunları tutan bir j değişkeni için i==j ve i==n-j durumlarında köşegen değerleri bulunduğu görülür.

Bu durumu aşağıdaki i ve j indislerinin yazılı olduğu tabloda görebiliriz:

i,j	1	2	3	4	5
1	1,1	1,2	1,3	1,4	1,5
2	2,1	2,2	2,3	2,4	2,5
3	3,1	3,2	3,3	3,4	3,5
4	4,1	4,2	4,3	4,4	4,5
5	5,1	5,2	5,3	5,4	5,5

Yukarıdaki tablodan da anlaşılacağı üzere her satır için bulunduğumuz satır numarası (i) ve karenin boyutu- satır numarası (n-i) koordinatlarına * sembolü koyuyoruz. Bunu yapan bir özyineli fonksiyonu (recursive function) aşağıdaki şekilde kodlayabiliriz:

Yukarıdaki kodda, n kullanıcının girdiği ve X harfinin boyutlarını tutan değişken, i satır, j ise sütun sayısı olmak üzere kodun 5. satırında bulunan if döngüsü i ve j ikilisinin köşegen olup olmadığını kontrol etmektedir. Şayet köşegen olan bir hücre ise * koymakta diğer durumlarda da boşluk koymaktadır.

Yukarıdaki fonksiyon her satır için yeniden çalışmakta ve n+1 değerine ulaştığında hiçbir işlem yapmadan nihayete ermektedir.

Yukarıdaki yeni fonksiyon, ilk fonksiyonu n kere çağırmakta ve her çağırma işleminde satır sayısı olan i değişkeninin değerini 1 arttırmaktadır. Böylelikle ilk fonksiyonumuz hangi satır için yazma işlemi yaptığını bilmektedir.

Yukarıdaki iki fonksiyonu birleştirip main fonksiyonu ekleyince aşağıdaki şekilde olur:

Kodun çalışan hali ise aşağıda verilmiştir:

int yildiz2(int n,int i,int j){

if(j==n+1)

return -1;

if((i+j)==n+1 || i==j)

printf(”*”);

else

printf(” “);

yildiz2(n,i,j+1) ;

}

« Körilemek (Currying) | Fibonacci Sayıları (Fibonacci Numbers) »

Yorumlar

Toplam 7 yorum var.

Fibonacci Sayıları (Fibonacci Numbers) : bilgisayar.kavramlari.com | 05 Aug 2008, 10:19
[...] bilimlerinde çok sık kullanılan sayı serileridir. Bu sayıların önemi özyineli (recursive) fonksiyonlar ile kolayca yazılabilmesidir. Fibonacci serisinin ilk iki sayısı 1′dir. [...]
Fibonacci Arama Algoritması (Fibonacci Search Algorithm) : bilgisayar.kavramlari.com | 05 Aug 2008, 10:46
[...] : Şadi Evren ŞEKER Bu arama algoritması, özyineli (recursive) bir seri olan fibonacci sayılarını kullanarak sıralı bir dizi üzerinde arama yapmaktadır. [...]
Hızlı Sıralama Algoritması (Quick Sort Algorithm) : bilgisayar.kavramlari.com | 09 Aug 2008, 22:22
[...] üzere yukarıdaki kod özyineli (recursive) bir koddur ve kendi içerisinde orta değeri bulmak için partition adı verile harici bir [...]
fatih | 08 Dec 2009, 02:55
int f(int a){
if(a==11){
return -1;
}
hocam recursive fonksiyonda diyelimki 1 den 10 a kadar sayıları yazmak istersek,bu bolumdeki kod return -1 in gorevi nedir? aynı bolumde if a=10 oldugunda neden 10 u dahil etmez?Burdan anlayacagımız return 0 -1 ve 1 in gorevleri farklımıdır?
duygu | 09 Dec 2009, 13:36
Mrb hocam recusive olarak yazılan yıldız sorusu kdunu tam olarak anlayamadım daha kolay anlayabilmem için bir kaç ipucu verebilirseniz sevinirim şimdiden teşekkürler.

int yıldız2(int n, int i,,int j){
if(j==n+1)
return-1;
if((i+j)==n+1|| i==j)
printf(”*”);
else
printf(” “);
yıldız2(n,i,j+1);
}
int yıldız(intn, inti){
if(i==n+1)
return-1;
yıldız2(n,i,1);
printf(”\n”);
yıldız(n,i+1);
}
int main(){
printf(”bir sayı giriniz”)
int n;
scanf(”%d”,&n);
yıldız(n,1);
getch();
}
efes | 01 Jan 2010, 19:40
merhaba;
kendim recursive olarak fibonacci yazmak istedim sadece girilen değerin sonucunu ekrana çıkartıyor nerede eksiklik var ?

#include
#include
int fib(int n){
if(n==0||n==1){
return 1;
}
return fib(n-1)+fib(n-2);
}
int main(){
int n;
printf(”fibonacci icin bir sayi giriniz”);
scanf(”%d”,&n);
printf(”%d”,fib(n));
getch();
return 0;
}
Şadi Evren ŞEKER | 01 Jan 2010, 21:34
sorunuzun cevabı http://www.bilgisayarkavramlari.com/2008/08/05/fibonacci-sayilari-fibonacci-numbers/ başlıklı yazıda daha önce anlatılmıştı. Kısaca fibonacci sayıları özyineli (recursive) olarak bastırmak için uygun değildir.

başarılar

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Özyineli Fonksiyonlar (Recursive Functions)' isimli yazı 05 Aug 2008 tarihinde, saat: 10:14 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 1562 defa okunmuştur.

Benzer yazıları C/C++, JAVA, Programlama Dilleri, algoritma analizi (teory of algorithms) kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar