Kendini tekrarlayan ( özçağrı ) ve yığın

Bu bölümde fonksiyonlar daha derinlemesine incelenecektir.

İlk konu özçağrı olacaktır.

Eğer daha önce program yazdıysanız bir sonraki bölüme geçebilirsiniz.

Öz çağrı bir programlama desenidir. Bu desen bir görevin aynı türde daha basit görevcikler haline getirilmesini sağlar. Veya bir görev daha kolay aksiyonlara ve aynı şekilde görevlere dönüştürülebildiğinde, veya daha sonra göreceğiniz gibi, belirli veri yapılarında kullanılabilir.

Bir fonksiyon problemi çözerken birçok farklı fonksiyonu çağırabilir. Bu özel durumda ise fonksiyon kendisini çağırır. Bu olaya özçağrı, recursion denir.

Çift yönlü düşünme

BaÅŸlangıçta us(x,n) adında bir fonksiyon olsun ve bu n üssü x i hesaplasın. DiÄŸer bir ifadeyle x’i n defa kendisiyle çarpsın.

us(2, 2) = 4
us(2, 3) = 8
us(2, 4) = 16

Bunu uygulamanın iki yolu bulunmaktadır.

1. Tekrarlı düşünürseniz: for döngüsü:

   function us(x, n) {
     let sonuc = 1;
     // x'in x defa kendisiyle çarpımı.
     for(let i = 0; i < n; i++) {
       sonuc *= x;
     }
   
     return sonuc;
   }
   
   alert( us(2, 3) ); // 8

2. Özçağrı: işi daha basite indirgeyerek kendisini çağırsın:

   function us(x, n) {
     if (n == 1) {
       return x;
     } else {
       return x * us(x, n - 1);
     }
   }
   
   alert( us(2, 3) ); // 8

Dikkat ederseniz özçaÄŸrı fonksiyonu aslen farklıdır. us(x,n) çaÄŸrıldığında çalıştırılma iki dala ayrılır.

              if n==1  = x
             /
us(x, n) =
             \
              else     = x * us(x, n - 1)

1. EÄŸer n==1 ise geriye kalanlar önemsizdir. Buna temel özçaÄŸrı denir, çünkü bu belirli bir sonucu çıktı verir: us(x,1) eÅŸittir x

2. DiÄŸer türlü us(x,n) x*us(x,n-1) ÅŸeklinde ifade edilebilir. Matematiksel olarak xn = x * xn-1 ÅŸeklinde ifade edilebilir. Buna öztekrar basamağı denir. Görev daha küçük aksiyonlara ( x ile çarpma ) indirgenmiÅŸ olur. Ayrıca aynı görevi daha basit görevlerle ( us’ün daha küçük n deÄŸeri) indirgenmiÅŸ oldu. Bir sonraki sitep ise bunun daha basite indirgene indirgene n’in 1 e ulaÅŸmasını saÄŸlamaktır.

Buna us öz çaÄŸrı ile kendisini n==1 olana kadar çağırır diyebiliriz.

us(2,4)'ü hesaplayabilmek için özçaÄŸrı ÅŸu adımları gerçekleÅŸtirir:

1. us(2, 4) = 2 * us(2, 3)
2. us(2, 3) = 2 * us(2, 2)
3. us(2, 2) = 2 * us(2, 1)
4. us(2, 1) = 2

özçağrı böylece fonksiyon çağrılarını dah abasite indirgemiştir. Daha sonra daha basite ve en sonunda sonuç belirli olana kadar devam etmiştir.

function us(x, n) {
  return (n == 1) ? x : (x * us(x, n-1));
}

Maksimum iç içe çağırma sayısına özçaÄŸrı derinliÄŸi us fonksiyonunda bu n’dir.

JavaScript motorları maksimum özçağrı derinliğini sınırlamaktadır. Bazı motorlarda 10000, bazılarında 100000 limiti bulunmaktadır. Bunun için otomatik optimizasyonlar bulunmaktadır. Fakat yine de her motorda desteklenmemektedir ve çok basit durumlarda kullanılır.

Bu özçağrı uygulamalarını limitler, fakat yine de çoğu yerde kullanılmaktadırlar. Çoğu görevde özçağrı şeklinde düşünmek daha basit ve sürdürülebilir bod yazmanızı sağlayacaktır.

Çalıştırma Yığını

Peki özçağrılar nasıl çalışır. Bunun için fonksiyonların içinde ne yaptıklarına bakmak gerekmektedir.

Çalışan fonksiyon hakkında bilgi çalıştırma kaynağında tutulur.

Çalıştırma Kaynağı – Execution Context fonksiyonun çalışması hakkında detayları tutan dahili bir veri yapısıdır: Kontrol akışı nerede, o anki deÄŸiÅŸkenlerin deÄŸeri, this neye denk gelir ve bunun gibi detaylar dahili detaylar tutar.

Her fonksiyon çağrısı kendine ait çalıştırma kaynağı tutar.

Eğer bir fonksiyon içeride başka bir çağrı yaparsa şunlar olur:

• O anki fonksiyon durur.
• Bu fonksiyon ile ilintili çalışma kaynağı çalışma kaynağı yığını veri yapısı ÅŸeklinde kaydedilir.
• Dallanılan çaÄŸrı çalıştırılır.
• Bu iÅŸlem bittikten sonra çalışma kaynağı yığınından daha önceki çalışmakta olan yer geri alınır, böylece fonksiyon kaldığı yerden görevini tamamlayabilir.

AÅŸağıda us(2,3)'ün çalışması gösterilmiÅŸtir.

us(2, 3)

us(2,3) çaÄŸrısının baÅŸlangıcında, çalışma kaynağı deÄŸiÅŸkenleri x=2,n=3 olacak ÅŸekilde tutar. Çalışma ÅŸu anda birinci satırdadır.

Bu aşağıdaki gibi gösterilebilir:

• Çalışma kaynağı: { x: 2, n: 3, birinci satırda } us(2, 3)

Ardından fonksiyon çalışmaya baÅŸlar. n==1 ÅŸartı yanlıştır, bundan dolayı ikinci if’e geçer.

function us(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * us(x, n - 1);
  }
}

alert( us(2, 3) );

Değişkenler aynı fakat satır değiştir, şimdiki kaynak şu şekilde:

• Kaynak: { x: 2, n: 3, 5. satırda } us(2, 3)

x*pow(x, n-1)'i hesaplayabilmek için us fonksiyonuna us(2,2) ÅŸeklinde yeni bir çaÄŸrı yapılmalıdır.

us(2, 2)

Dallanma işleminin yapılabilmesi için JavaScript’in öncelikle o anki çalışma durumunu çalışma kaynağı yığınına atması gerekmektedir.

Burada us fonksiyonu çaÄŸrılmıştır. Bu herhangi bir fonksiyon da olabilirdi, aralarında bu yönden hiçbir farklılık bulunmamaktadır:

1. O anki kaynak yığının en üstüne “hatırlatılır”
2. Alt çağrı için yeni bir kaynak yaratılır.
3. Alt çağrılar bittiğinde – bir önceki kaynak yığından alınır ve çalışmasına devam eder.

AÅŸağıda pow(2,2) altçaÄŸrısına girildiÄŸinde kaynak yığınının durumu gösterilmektedir.

• Kaynak: { x: 2, n: 2, 1. satırda } us(2, 2)
• Kaynak: { x: 2, n: 3, 5. satırda } us(2, 3)

Üst tarafta o anda çalışan kaynak ( kalın harflerle ), alt tarafta ise “hatırlatılan” kaynak bulunmaktadır.

Altçağrı bittiğinde, daha önceki kalınan kaynaktan devam etmek kolaydır. Çünkü bu her iki değişkeni ve kaldığı satırı tutmaktadır. Burada “satır” denmesine rağmen aslında bunun daha net bir şey olduğu bilinmelidir.

us(2, 1)

Ä°ÅŸlem tekrar ediyor: 5. satırda yeni bir altçaÄŸrı yapılmaktadır, argümanlar ise x=2, n=1 ÅŸeklindedir.

Yeni çalışma yığını oluşturur, bir önceki yığının üstüne itelenir. A new execution context is created, the previous one is pushed on top of the stack:

• Kaynak: { x: 2, n: 1, 1. satır } us(2, 1)
• Kaynak: { x: 2, n: 2, 5. satır } us(2, 2)
• Kaynak: { x: 2, n: 3, 5.satır } us(2, 3)

Åžu anda 2 eski kaynak ve 1 tane çalışmakta olan kaynak bulunmaktadır us(2,1)

Çıkış

us(2,1) çalışırken diÄŸerlerinin aksine n==1 ÅŸartı saÄŸlanır, bundan dolayı ilk defa birinci if çalışır.

function us(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * us(x, n - 1);
  }
}

Daha fazla dallanan çağrı olmadığından dolayı fonksiyon sona erer ve değeri döner.

Fonksiyon bittiğinden dolayı, çalışma kaynağına gerek kalmamıştır ve dolayısıyla hafızadan silinir. Bir önceki yığından alınır:

• Kaynak: { x: 2, n: 2, 5. satırda } us(2, 2)
• Kaynak: { x: 2, n: 3, 5. satırda } us(2, 3)

us(2,2) nin çalışması devam etti. us(2,1)'in sonucuna sahip olduÄŸundan x * us(x,n-1)'in sonucunu bulabilir, bu da 4’tür.

Ardından bir önceki kaynak geri yüklenir:

• Kaynak: { x: 2, n: 3, 5. satırda } us(2, 3)

Ä°ÅŸlemler bittiÄŸinde, us(2,3) = 8 sonucu alınır.

Bu durumda özçağrı derinliği 3tür

Yukarıda da görüldüğü üzere, özçaÄŸrı derinliÄŸi yığındaki kaynak sayısı demektir. Bu drumda n’in üssü deÄŸiÅŸtirildiÄŸinde daha fazla hafıza kullanacaktır.

Döngü bazlı algoritma daha az hafıza kullanacaktır:

function us(x, n) {
  let sonuc = 1;

  for(let i = 0; i < n; i++) {
    sonuc *= x;
  }

  return sonuc;
}

Tekrar eden us fonksiyonu i ve sonuc kaynağını kullanır ve sürekli bunları deÄŸiÅŸtirir. Hafıza gereksinimleri oldukça azdır ve bu hafıza büyüklüğü n’e baÄŸlı deÄŸildir.

Tüm özçağrılar döngü olarak yazılabilir. Döngü versiyonu daha az kaynak gerektirecektir

… Bazen yeniden yazmak çok kolay değildir, özellikle fonksiyon alt çağrılarda özçağrı kullanıyorsa, bu çağrılar sonucunda daha karmaşık dallanmalar oluyor ise optimizasyon değmeyebilir.

Özçağrı fonksiyonun daha kısa kod ile yazılmasını sağlar, ayrıca anlaşılmayı da kolaylaştırır. Optimizasyon her yerde gerekli değildir, genelde iyi kod gereklidir, bunun için kullanılır.

Özçağrı Akışı

Özçağrıların kullanılabileceği diğer bir uygulama özçağrı akışıdır.

Bir firma hayal edin. Çalışanların yapısı obje olarak şu şekilde tanımlanabilir:

let firma = {
  satis: [{
    adi: 'Ahmet',
    maasi: 1000
  }, {
    adi: 'Mehmet',
    salary: 150
  }],

  gelistirme: {
    siteler: [{
      adi: 'Mustafa',
      ucret: 200
    }, {
      adi: 'Mazlum',
      ucret: 50
    }],

    dahili: [{
      adi: 'Zafer',
      ucret: 1300
    }]
  }
};

Diğer bir deyişle bu firmanın departmanları bulunmaktadır.

• Bir departman çalışanlar dizilerinden oluÅŸabilir. ÖreÄŸin satis departmanı 2 tane çalışana sahiptir: Ahmet ve Mehmet.

• Veya bazen departmanlar alt departmanlara ayrılabilirler. ÖrneÄŸin gelistirme departmanı siteler ve dahili olmak üzere ikiye ayrılmıştır. Her bir alt departmanın kendine ait çalışanları vardır.

• Bunun yanında departmanların büyüyüp alt departmanlara ayrılması da mümkündür.

  ÖrneÄŸin siteler departmanı ileride iki ayrı takıma siteA ve siteB ÅŸeklinde ayrılabilirler. Ve yine potansiyele göre ileride bu takımlar da alt takımlara ayrılabilirler.

Öyle bir fonksiyon olsun ki tüm çalışanların maaşlarının toplamını dönsün. Bu nasıl yapılır?

Döngü yaklaşımı kolay deÄŸildir, çünkü yapı kolay deÄŸildir. Önce firma için bir for döngüsü kullanıldığını ve bununla ilk seviye departmanları bulduÄŸunuzu varsayın. Sonrasında bunun içine bir döngü daha yapıp siteler’i bulmanız gerekir. Ayrıca ilerisi için bir tane daha for döngüsü yapmanız lazım ve belki yine onun içerisine de bir döngü koymanız lazım. 3. basamakta mı 4. basamakta mı durmalı? EÄŸer ileride bu yapı sadece bir seviyeye indirilirse kodda karmaşıklık meydana gelir.

Özçağrı yaklaşımıyla.

Fonksiyon toplanacak departmanı aldığında iki muhtemel durum mevcuttur:

1. Bu “basit” bir departman olabilir içerisinde çalışanlar bulunur – sonra bunların maaşları basit bir döngüyle toplanabilir.
2. Veya N alt departmana sahip obje olabilir – öyleyse N defa özçaÄŸrı yapıp her bir alt departmanın toplamının sonucunu döndürülür.

(1) özçağrının temelidir.

(2) Özçağrının tekrar eden adımlarıdır. Karmaşık görev daha küçük departman görevlerine ayrılır. Sonrasında yine ayrılabilir fakat en sonunda (1)'e erişecektir.

Algoritma kodunu okumak oldukça kolaydır:

let firma = {
  satis: [{
    adi: 'Ahmet',
    maasi: 1000
  }, {
    adi: 'Mehmet',
    salary: 150
  }],

  gelistirme: {
    siteler: [{
      adi: 'Mustafa',
      ucret: 200
    }, {
      adi: 'Mazlum',
      ucret: 50
    }],

    dahili: [{
      adi: 'Zafer',
      ucret: 1300
    }]
  }
};

// Ä°ÅŸi yapan fonksiyon
function maaslariTopla(firma) {
  if (Array.isArray(firma)) { // (1). durum
    return firma.reduce((onceki, suanki) => onceki + suanki.salary, 0); // diziyi topla
  } else { // (2.) durum
    let toplam = 0;
    for(let altDep of Object.values(altDep)) {
      sum += maaslariTopla(altDep); // özçağrı ile alt departmanların çağrılması, bunu sum ile topla.
    }
    return sum;
  }
}

alert(maaslariTopla(firma)); // 2700

Kod oldukça kısa ve anlaması kolay(umarım). Burada özçağrının gücünden bahsetmek mümkün, her seviye alt departman için çalışacaktır.

Aşağıda ise bu çağrının diyagramı bulunmaktadır.

Prensip basitçe ÅŸu ÅŸekilde açıklanabilir: Obje için {...} altçaÄŸrıları yapılır, [...] ise özçaÄŸrı aÄŸacının “yapraklarıdır”, anında sonucu dönerler.

Kodun akıllı özellikler kullandığına dikkat edin, bunlar daha önceki kolarda işlenmişti:

• arr.reduce metodu Dizi Metodları bölümünde bir dizinin toplamını almak için kullanılmıştı.
• for(val of Object.values(obj)) objenin deÄŸerlerini dönmek için kullanılmıştı: Object.values objenin deÄŸerlerini dizi olarak döner.

Özçağrı yapıları

Özçağrı yapıları, kendini bazı bölümlerde tekrar eden veri yapılarıdır.

Örnekte kullanılan firmalar objesi bu yapıyı kullanmaktadır.

Bir departman

• Dizi veya çalışanlardan oluÅŸur.
• Veya departmanlardan oluÅŸur.

Web-geliştiricileri için daha bilinen bir örneği: HTML ve XML dökümanlarıdır.

HTML dökümanında, HTML-tag’ı şunları içerebilir:

• Metinler
• HTML-yorumları
• DiÄŸer HTML-tagları ( bunlar da yine metinler, yorumlar ve diÄŸer tagları içerebilir)

Bu da yine özçağrı yapısıdır.

Daha iyi anlaşılması için “Linked list” yapısı üzerinden gitmek gerekir. Bu bazı durumlarda dizilere alternatif olarak kullanılabilir.

Linked list

Diyelim objelerin sıralı şekilde liste halinde tutmak istiyorsunuz.

Diziler ile aşağıdaki gibi yapılabilir:

let arr = [obj1, obj2, obj3];

… Fakat diziler “eleman silme”, “eleman ekle” gibi olaylar için çok iÅŸlem yaparlar. ÖrneÄŸin arr.unshift(ob) iÅŸlemi tüm elemanları yeni eleman için tekrardan sıraya dizer, eÄŸer dizi büyükse bu zaman alır. Aynısı arr.shift() için de geçerlidir.

Tekrardan numaralama gerektirmeyen arr.push/pop metodları kullanılabilir. Bunlar da dizinin sonuna ekler veya çıkarır. Çok elemanlı dizilerde bu iÅŸlemlerin yavaÅŸ olacağı söylenebilir.

Alternatif olarak, eğer hızlı bir şekilde, silme/yerleştirme istenirse diğer bir veri yapısı olan linked list kullanılabilir.

linked list elemanı özçağrı biçimde aşağıdaki obje gibi tanımlanır:

• deger.
• sonraki sonraki linked list elemanı’nı tenımlar, sonuncuysa null döner.

Örneğin:

let list = {
  deger: 1,
  sonraki: {
    deger: 2,
    sonraki: {
      deger: 3,
      sonraki: {
        deger: 4,
        sonraki: null
      }
    }
  }
};

Bu listenin grafiksel gösterimi şu şekildedir:

Bu yapıyı yaratmanın alternatif yolu şu şekildedir:

let list = { deger: 1 };
list.sonraki = { deger: 2 };
list.sonraki.sonraki = { deger: 3 };
list.sonraki.sonraki.sonraki = { deger: 4 };

Burada görüldüğü üzere her obje degere sahiptir ve komÅŸusu olan sonrakini gösterir. list deÄŸiÅŸkeni bu zincirin ilk halkasıdır, sonrasında sonraki pointer’ını takip eder.

Liste kolayca birçok parçaya bölünebilir ve sonradan tek bir yapı haline getirilebilir:

let ikinciList = list.sonraki.sonraki;
list.sonraki.sonraki = null;

BirleÅŸtirme:

list.sonraki.sonraki = ikinciList;

Ve istenildiÄŸi gibi elemanlar bir yerden silinebilir veya eklenebilir.

Örneğin yeni bir değer ekleneceği zaman, listenin başlangıcının güncellenmesi gerekir:

let list = { deger: 1 };
list.sonraki = { deger: 2 };
list.sonraki.sonraki = { deger: 3 };
list.sonraki.sonraki.sonraki = { deger: 4 };

// Yeni bir deÄŸer ekleneceÄŸi zaman
list = { deger: "yeni eleman", sonraki: list };

Yine ortalardan bir yerden veri silineceÄŸi zaman sonraki’nin bir öncekine getirilmesi gerekri.

list.sonraki = list.sonraki.sonraki;

list.sonraki’nin deÄŸeri 1’den 2’ye geçirildi. 1 deÄŸeri artık zincirden çıkarıldı. EÄŸer bu deÄŸer baÅŸka bir yerde tutulmuyor ise, bu deÄŸer ileride otomatik olarak hafızadan silinecektir.

Diziler gibi çok büyük sayida tekrar numaralama bulunmamaktadır, ve kolayca istenilen eleman istenilen yere koyulur.

Her zaman List diziden daha iyidir denemez. Öyle olsaydı herkes dizi yerine List kullanırdı.

En büyük handikapı List’te istenilen elemana kolayca eriÅŸim saÄŸlanamaz. Dizilerde bu oldukça kolaydır: dizi[n] doÄŸrudan referans verir. Fakat dizilerde ilk elemandan itibaren sonraki ÅŸeklinde N defa gitmek gerekir.

Fakat çoğu zaman böyle bir işleme ihtiyaç duymayız. Örneğin bir kuyruk ihtiyacı olduğunda hatta deque ihtiyacı olduğunda hızlı bir şekilde baştan veya sondan eleman eklenip silinmesi gerekir.

Bazen kuyruk adında bir deÄŸiÅŸken eklenerek ( yeni eleman eklendiÄŸinde/çıkarıldığında ) listenin son elemanı takip edilebilir. Büyük dizilerde listeye göre hız oldukça fazladır.

Özet

Tanımlar:

• Öz ÇaÄŸrı kendi kendini çağırma fonksiyonu demektir. Böyle fonksiyonlar belirli yapıdaki görevlerin çözülmesini saÄŸlar.

  Fonksiyon kendisini çağırdığında buna öztekrar adımı denir. temel ise öz çağrı fonksiyonun argümanının tekrar öz çağrı yapılamayacak kadar basite indirgenmesi olayıdır.

• ÖzçaÄŸrı yapısı kendisini tekrar kullanarak tanımlanan veri yapılarıdır.

  Örneğin, linked list objenin listeyi referans veren bir veri yapısı olarak tanımlanabilir.

  list = { deger, sonraki -> list }

  HTML elemanlarının ağacı veya departman ağacı gibi yapılar özçağrı yapısıdır: Bunların dalları ve dallarının yine dalları bulunmaktadır.

  ÖzçaÄŸrı fonksiyonları maaslariTopla fonksiyonunda olduÄŸu gibi elemanların üzerinden geçer.

Her özçağrı fonksiyonu tekrarlı şekile getirilebilir. Bazen optimize etmek için kullanılabilir. Fakat çoğu görev için özçağrı çözümleri yeteri kadar hızlı ve yazması kolaydır.