C’de Özyineleme

Bazı algoritmalarda tekrar eden adımların olduğunu zaten biliyoruz. Bu adımlar programlama dillerinde implement edilirken genellikle döngü yapılarından yararlanırız. C dilinde while ve for gibi yapılar algoritmaların bu kısımlarını implement etmek için fazlasıyla yeterli olmaktadır. Ancak algoritmalarda tekrar eden adımları implement etmenin tek yolu bu mudur? Bu yöntem gerçekten her konuda en etkili yöntem midir? Bu yazıda algoritmalarda tekrar eden kısımları implement etmenin bir başka yöntemi olan özyineleme (recursion) tekniğine değinecek ve bunun sıradan yineleme (iteration) tekniğinden ne gibi farkları olduğuna bakacağız.

Öncelikle yineleme kavramına bakalım. Yineleme (iteration) belli bir kod bloğunun yinelemeli yapılar ile tekrar tekrar çalıştırılmasıdır. Bu kavrama zaten while ve for gibi döngü yapılarından aşinasınız. Yinelemede belli bir kontrol değişkenine başvurulur ve bu kontrol değişkeni her dönüşte kontrol edilerek döngünün sonlanıp sonlanmadığına karar verilir. Bunun yanında herhangi bir kontrol değişkeni kullanılmadan oluşturulan sonsuz döngüler de olabilir. Yinelemede herhangi bir fonksiyon çağrısına ihtiyaç duyulmaz. Dolayısıyla yineleme ile implement edilen algoritmalar fonksiyonların fazlaca tükettiği yığın (stack) alanını tüketmez.

Özyineleme (recursion) ise bir algoritmanın tamamını veya bir kısmını problemin git gide daha küçülen parçaları için çalıştırma anlamına gelir. Bu teknikte while ve for gibi döngü yapılarına ihtiyaç duyulmaz, fonksiyonlardan yararlanılır. Yani özyineleme aslında programlamada bir fonksiyonun kendi kendini çağırması ve belli bir duruma gelince bu çağırma işleminin sonlanması anlamına gelir. Çağırma işleminin son bulduğu duruma Temel Durum (Base Case) adı verilir. Özyineli kodlarda temel durum gerçekleşinceye kadar fonksiyonlar kendi kendilerini çağırmaya devam eder. Dolayısıyla yığın (stack) alanı fazlaca kullanılır. Ancak bazı durumlarda kod daha kısa hale gelir.

Bunun yanında özyineli olarak implement edilen algoritmalar üzerinde hata ayıklama ve test yapmak bazen sancılı olabilir. Peki bu kadar olumsuz özelliğine rağmen neden özyineleme kullanalım? Çünkü bazı problemlere bu şekilde yaklaşmak daha kolay olabiliyor. Fark ettiyseniz yukarıda bahsettiğim bütün problemler aslında bu algoritmaların fiziksel bir ortamda implementasyonundan kaynaklanıyor. Ancak bir problemin çözümüne soyut olarak yaklaştığınızda bazen bu tip algoritmaların kullanılması daha iyi olabilir. Bunun yanında ağaç (tree) gibi veri yapıları üzerinde dolaşma ile ilgili algoritmalar bu yaklaşımla daha kolay ele alınabilir.

Şimdi biraz teorik bilgi verdikten sonra yavaş yavaş C tarafında bu yaklaşımı nasıl implement edebileceğimize geçelim. Öncelikle çok basit bir örnekle başlayalım. Bu örnekte bir for döngüsü kullanarak 1’den 10’a kadar olan sayıları toplayan bir kod parçası yazalım:

int result = 0;
for(int i=1; i<10; ++i)
{
    result += i;
}

printf("%d\n", result); // Output: 45

Şimdi de aynı işi yapan sum isimli fonksiyonumuzu yazalım. C’de kendi kendini çağıran fonksiyonlara Özyinelemeli Fonksiyonlar (Recursive Functions) adı verilir. Aşağıdaki sum fonksiyonu da böyle bir fonksiyondur:

int sum(int number)
{
    if(number == 1)
    {
        return 1;
    }

    return number + sum(number - 1);
}

Bu kodu sum(9) şeklinde çağırıp geri dönen değeri ekrana bastığımızda yine 45 çıktısını göreceğiz. İlk kodda neler döndüğünü zaten biliyorsunuz. Peki ikinci kodda neler dönüyor? Öncelikle bir if bloğu görüyorsunuz. Bu if bloğu aslında temel durumu belirtmektedir. Yani algoritmada bu kısım aslında “bu fonksiyonun parametresine 1 değeri gelirse, başka fonksiyon çağırma ve 1 geri döndür” kısmıdır. Bu bloğun altında kalan geri dönüş deyimi ise ilk bakışta kafanızı biraz karıştırabilir. İsterseniz bu fonksiyonun çalışma biçimini bir diyagramda göstererek anlatmaya çalışalım:

Yukarıdaki figürde her bir adımda yapılan fonksiyon çağrılarını ve çağrılar sona ulaşınca fonksiyonların teker teker hangi değerleri geri döndürdüğünü net bir şekilde görmeniz mümkündür. İşte özyinelemeli algoritmaların temel çalışma mantığı budur; temel duruma ulaşana kadar fonksiyon çağrısı yap ve temel duruma ulaşınca ilk fonksiyona kadar değer geri döndür. Elbette bu figürde bir başka şey daha dikkatinizi çekmiştir: Yığın. Yazının başından beri bahsediyorum, ancak bilmeyenleriniz olabilir. Bu nedenle biraz yığından ve fonksiyon çağrılarıyla ilgili ne gibi bir ilişkisi olduğundan bahsedeceğim.

Yığın (Stack), aslında “son giren ilk çıkar (Last-In-First-Out, LIFO)” mantığına göre çalışan bir veri yapısıdır. Kendisi en temel veri yapılarından biridir ve bilişim sektörünün pek çok alanında sıkça kullanılır. Bu kullanım alanlarından biri de ana bellekte çağrılan fonksiyonların bilgilerini geri dönünceye kadar saklamaktır. Peki neden bu iş için böyle bir veri yapısına ihtiyaç duyulmuştur? Bildiğiniz gibi bir fonksiyonun içinde başka bir fonksiyon ve onun içinde de başka bir fonksiyon çağırabiliriz. En son çağırdığımız fonksiyon işini bitirmeden onu çağıran bir önceki fonksiyonun da işini bitirmesi mümkün değildir. Bu nedenle böyle bir veri yapısına ihtiyaç duyulur.

Yığın veri yapısını tek bir ağzı olan bir çuvala benzetebilirsiniz. Çuvala bir şeyler koyma eylemini bu ağızdan yapar, çuvaldan bir şeyler alma eylemini de yine bu ağızdan yaparız. Yani alabileceğimiz (veya koyabileceğimiz) başka yer olmadığından, altlarda kalan bir malzemeyi çuvaldan almak istediğimizde önce üstlerdeki malzemeleri almamız gerekir. İşte yığın veri yapısının temel çalışma mantığı budur. Yığına bir veri ekleme işlemine Push (Eleman Ekle) adı verilirken, yığından veri alma (silme) işlemine Pop (Eleman Çıkar) adı verilmektedir. Bu işlemlerin ismi kısa ve öz olduğundan çevirmeye ihtiyaç duymadım. Aşağıdaki figürde bu işlemlerin nasıl gerçekleştiği ile ilgili örneği inceleyebilirsiniz:

Çalıştırdığınız her bir programın bellekte kendine has ve belirli boyutu olan bir yığın alanı olur. Bu yığın alanına Program Yığını (Program Stack) veya Çağrı Yığını (Call Stack) adı verilmektedir. Program yığını bir programda bir fonksiyon çağrısı yapıldığında, o fonksiyonla ilgili yerel değişkenleri, parametreleri ve geri dönüş adresini tutar. Bu yığında yer alan her bir girdi Yığın Çerçevesi (Stack Frame) olarak adlandırılır. Bir fonksiyon çağrıldığında program yığınına bu fonksiyon ile ilgili bir Push işlemi gerçekleştirilir. Fonksiyonun işi bitip çağırana geri dönüldüğünde ise Pop işlemi ile o fonksiyona ait yığın çerçevesi silinir. Yığınlar ile ilgili bu kadar bilgi yeterlidir. Daha ayrıntılı bilgileri bu veri yapılarını anlatırken vereceğim.

Şimdi konumuza geri dönelim. İlk örnekte özyineli bir çağrının nasıl yapıldığını az çok kavramış olduk. Ancak bu örnek, özyinelemeyi anlatmak için oldukça basit kalmaktadır. Bu örnekte kullandığımız özyineleme, işleri daha karmaşık hale getirmektedir. Şimdi kendisi ile çok sık karşılaşabileceğimiz bir başka örneğe geçelim; matematikte adını çok duyduğunuz Fibonacci Serisi (Fibonacci Series). Bu seride her bir sayı kendinden önce gelen iki sayının toplamından meydana gelmektedir. Aşağıda tipik bir Fibonacci Serisi görülmektedir:

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

Şimdiki örneğimizde kullanıcıdan bir n sayısı alacak ve baştan n Fibonacci sayısını ekrana bastırmaya çalışacağız. Önce yinelemeli olarak ilk 10 Fibonacci sayısını ekrana basmaya çalışalım:

#include <stdio.h>

int fibonacci(int n)
{
    int first = 0;
    int second = 1;
    int sum = 0;

    for(int i=1; i<=n; i++)
    {
        sum = first + second;
        first = second;
        second = sum;
    }

    return sum;
}

int main()
{
    for(int i=0; i<10; i++)
    {
        printf("%d ", fibonacci(i));
    }
    printf("\n");

    return 0;
}

Burada toplanan iki sayıyı tutan first ve second isimli iki değişken tanımlıyoruz. Bu değişkenlere ilk değer olarak 1 ve 0 değerlerini, yani ilk iki Fibonacci sayısının değerini atıyoruz. Daha sonra aşağıdaki for döngüsü ile belli adımdaki sayıyı bulup sum değişkenine atıyoruz. Son olarak ise bu değişkeni geri döndürüryoruz. main fonksiyonunda ilk 10 Fibonacci sayısını ekrana basmak için bir for döngüsü yazıyoruz. Gördüğünüz gibi fibonacci fonksiyonunun içeriği biraz uzun ve anlaması zor görünüyor. Şimdi de bunu özyinelemeli bir fonksiyon ile yapalım:

#include <stdio.h>

int fibonacci(int n)
{
    if(n == 0 || n == 1)
    {
        return n;
    }

    return fibonacci(n-1) + fibonacci(n-2);
}

int main()
{
    for(int i=0; i<10; i++)
    {
        printf("%d ", fibonacci(i));
    }
    printf("\n");

    return 0;
}

Bu seferki fibonacci fonksiyonunda ise özyineleme tekniğini kullanıyoruz. İlk iki durum için fonksiyonu doğrudan o sayılara geri döndürüyoruz. Bu algoritmanın temel durumu oluyor. Geri dönüş deyiminde ise fonksiyonun parametresinin 1 eksik hali ile 2 eksik halini topluyoruz. Özyinelemeyi bu şekilde yapmamız da mümkündür. Böylelike boşluklar ve parantezler dahil 12 satır olan fonksiyonu 6 satıra düşürüp %50 oranında kod tasarrufu sağlıyoruz. Ancak her ne olursa olsun özyinelemeli teknik daha büyük n değerleri için çok daha maliyetli hale gelecektir. Bu iki örnekten özyinelemeli tekniğin satır sayısı anlamında ve okunabilirlik anlamında nasıl faydalı olabildiğini görmekteyiz.

Özyineleme ile ilgili bu örneklerde anladığınız üzere, özyinelemenin çoğu zaman performans açısından oldukça sıkıntılı bir seçenek olduğu aşikardır. Bazı algoritmaları onunla implement etmek bize fayda sağlasa da bu algoritmalar şu ana kadar gördüğümüz konuların çok daha ilerisinde yer almaktadır. Yani şimdilik bir fonksiyonun kendi kendini çağırmasının temel mantığını anlamanız yeterlidir. Son olarak özyineleme ile ilgili karşınıza çıkacak temel problemlerden bahsedelim. Özyineleme ile ilgili en büyük problemlerden biri temel duruma ulaşamayıp sonsuz çalıştırmaya girmektir. Bu durumda elbette program için atanan yığın alanı kısıtlı olduğundan, yığın dolduğunda Yığın Taşması (Stack Overflow) denilen bir sorun oluşur. Bu durumda programınız hata ile sonlanacaktır.

int fibonacci(int n)
{
    if(n == 0 || n == 1)
    {
        return n;
    }

    return fibonacci(n) + fibonacci(n-2);
}

Örneğin yukarıdaki kodda n-1 yerine n yazarsak program sürekli fonksiyonu aynı argüman ile çağıracak ve sonsuz döngüye girilecektir. Bu durumda yığın taşması durumu gerçekleşir ve program kapatılır. Bu nedenle özyinelemeli algoritmaları tasarlarken ve implement ederken oldukça dikkatli olmak gerekir. Temel duruma hiç ulaşamamasından ziyade, temel durumun hiç yazılmaması da bir başka sorundur:

int test(int n)
{
    return test(n-1);
}

Muhtemelen böyle bir durumda derleyiciniz size bir uyarı gösterecektir. Yine geri dönüş deyiminin kullanım sırasına dikkat etmek gerekir:

int fibonacci(int n)
{
    return fibonacci(n-1) + fibonacci(n-2);

    if(n == 0 || n == 1)
    {
        return n;
    }
}

Bu yazıda özyineleme tekniğinin ne olduğundan ve yineleme tekniği ile arasında ne farklar bulunduğundan kısaca bahsettik. Bunun yanında C’de özyinelemeli fonksiyonları nasıl yazabileceğimizi ve bir özyinelemeli fonksiyonun bellek üzerinde nasıl bir davranış sergilediğini örneklerle gösterdik. En son ise özyinelemeli fonksiyonlarda karşımıza çıkacak temel sorunları ele aldık. Bu yazı ile “C’de Fonksiyonlar” ünitemizin sonuna geliyoruz. Artık diziler ve göstericiler gibi C dilinin kalbi diyebileceğimiz bazı konulara geçme vaktimiz gelmiştir.

REFERANSLAR

1. https://cdn.buttercms.com/PuR6MmOQQdqAP6xfh6JO