Veri Yapısı - Özyineleme Temelleri

Bazı bilgisayar programlama dilleri, bir modülün veya işlevin kendisini çağırmasına izin verir. Bu teknik, özyineleme olarak bilinir. Özyinelemede bir işlevα ya kendisini doğrudan ya da bir işlevi çağırır β bu da orijinal işlevi çağırır α. İşlevα özyinelemeli işlev denir.

Example - kendisini çağıran bir işlev.

int function(int value) {
   if(value < 1)
      return;
   function(value - 1);

   printf("%d ",value);   
}

Example - başka bir işlevi çağıran ve ardından onu yeniden çağıran bir işlev.

int function1(int value1) {
   if(value1 < 1)
      return;
   function2(value1 - 1);
   printf("%d ",value1);   
}
int function2(int value2) {
   function1(value2);
}

Özellikleri

Özyinelemeli bir işlev, bir döngü gibi sonsuza gidebilir. Özyinelemeli işlevin sonsuz çalışmasını önlemek için özyinelemeli bir işlevin sahip olması gereken iki özellik vardır:

• Base criteria - En az bir temel ölçüt veya koşul olmalıdır, öyle ki bu koşul karşılandığında işlev kendini yinelemeli olarak çağırmayı durdurur.

• Progressive approach - Özyinelemeli aramalar, her yinelemeli arama yapıldığında temel kriterlere yaklaşacak şekilde ilerlemelidir.

Uygulama

Birçok programlama dili özyinelemeyi şu şekilde uygular: stacks. Genellikle, bir işlev (caller) başka bir işlevi çağırır (callee) veya kendisi aranan uç olarak, arayan işlevi yürütme kontrolünü aranan uca aktarır. Bu transfer işlemi ayrıca arayan uçtan aranan uca bazı verilerin aktarılmasını da içerebilir.

Bu, arayan işlevinin yürütmeyi geçici olarak askıya alması ve yürütme kontrolü aranan uç işlevinden döndüğünde daha sonra devam etmesi gerektiği anlamına gelir. Burada, çağıran işlevinin, kendisini beklemeye aldığı yürütme noktasından tam olarak başlaması gerekir. Ayrıca üzerinde çalıştığı aynı veri değerlerine de ihtiyaç duyar. Bu amaçla, arayan işlevi için bir aktivasyon kaydı (veya yığın çerçevesi) oluşturulur.

Bu aktivasyon kaydı yerel değişkenler, biçimsel parametreler, dönüş adresi ve arayan işlevine aktarılan tüm bilgiler hakkındaki bilgileri tutar.

Özyineleme Analizi

Aynı görev yinelemeyle yapılabildiğinden, neden yinelemenin kullanılacağı tartışılabilir. İlk neden, özyinelemenin bir programı daha okunabilir hale getirmesi ve en son geliştirilmiş CPU sistemleri nedeniyle özyinelemenin yinelemelerden daha verimli olmasıdır.

Zaman Karmaşıklığı

Yineleme durumunda, zaman karmaşıklığını saymak için yineleme sayısı alırız. Aynı şekilde, yineleme durumunda, her şeyin sabit olduğunu varsayarak, yinelemeli bir çağrının kaç kez yapıldığını anlamaya çalışırız. Bir işleve yapılan bir çağrı Ο (1) 'dir, dolayısıyla bir özyinelemeli çağrının yapıldığı (n) sayısı özyinelemeli işlevi Ο (n) yapar.

Uzay Karmaşıklığı

Alan karmaşıklığı, bir modülün çalışması için ne kadar ekstra alan gerektiği olarak sayılır. Yineleme durumunda, derleyici fazladan alan gerektirmez. Derleyici, yinelemelerde kullanılan değişkenlerin değerlerini güncellemeye devam eder. Ancak özyineleme durumunda, sistemin her özyinelemeli çağrı yapıldığında aktivasyon kaydını saklaması gerekir. Bu nedenle, yinelemeli fonksiyonun uzay karmaşıklığının yinelemeli bir fonksiyonunkinden daha yüksek olabileceği düşünülmektedir.