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.

Özçağrı genelde tekrarlı olana göre daha kısadır

Aşağıda aynı fonksiyonun ? ile tekrar yazılmış hali bulunmaktadır.

function us(x, n) {
  return (n == 1) ? x : (x * pow(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.next.next;
list.next.next = null;

Birleştirme:

list.next.next = 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.

Görevler

önem: 5

topla(n) fonksiyonu 1+2+....+n şeklinde toplama işlemi yapar.

Örneğin:

topla(1) = 1
topla(2) = 2 + 1 = 3
topla(3) = 3 + 2 + 1 = 6
topla(4) = 4 + 3 + 2 + 1 = 10
...
topla(100) = 100 + 99 + ... + 2 + 1 = 5050

3 farklı şekilde yapınız:

  1. Döngü kullanarak
  2. Özçağrı kullanarak, topla(n) = n + topla(n-1) her n > 1 için.
  3. Aritmetik işlem kullanarak

Sonuc:

function topla(n) { /*... kodunuz ... */ }

alert( topla(100) ); // 5050

Not: Hangi yöntem daha hızlıdır? Hangisi yavaştır? Neden?

Not2: Özçağrı ile topla(100000) çalıştırılabilir mi?

Döngü kullanarak çözümü:

function topla(n) {
  let toplam = 0;
  for (let i = 1; i <= n; i++) {
    toplam += i;
  }
  return toplam;
}

alert( topla(100) );

Özçağrı kullanarak toplama:

function topla(n) {
  if (n == 1) return 1;
  return n + topla(n - 1);
}

alert( topla(100) );

Aritmetik işlemler ile toplama: topla(n) = n*(n+1)/2:

function topla(n) {
  return n * (n + 1) / 2;
}

alert( topla(100) );

Not: Doğal olarak formül en hızlı olanırıd. n'in her değeri için 3 defa operasyon yapmaktadır. Matematik yardımcı olur!

Döngü hız bakımından ikinci sırada yer alır. Döngüde ve özçağrıda aynı sayılar toplanır. Fakat özçağrı iç içe çağrılar kullanarak çalışıtırma yığını yönetimi gerektirir. Bu da ayrıca bir kaynak demektir, bundan dolayı yavaştır.

Not2: Eğer özçağrının son fonksiyonunda ise ( topla gibi ) dıştaki fonksiyon çalışmayı devam ettirmez ve çalıştırma kaynağının bilinmesine gerek yoktur. Bundan dolayı topla(100000) hesaplanabilirdir. Fakat JavaScript motoru bunu desteklemiyor ise bu durumda maksimum yığın geçildi hatası verecektir. Bunun nedeni yığının belirli bir sınırının olmasıdır.

önem: 4

Faktöriyel (https://en.wikipedia.org/wiki/Factorial) bir sayının "bir önceki" ile "bir önceki"'nin vs. vs. şeklinde 1 olana kadar çarpılmasıdır. n in faktöriyeli n! şeklinde gösterilir.

Faktöriyelin tanımı aşağıdaki gibidir:

n! = n * (n - 1) * (n - 2) * ...*1

Farklı n değerlerinin faktöriyelleri şu şekildedir:

1! = 1
2! = 2 * 1 = 2
3! = 3 * 2 * 1 = 6
4! = 4 * 3 * 2 * 1 = 24
5! = 5 * 4 * 3 * 2 * 1 = 120

Göreviniz faktoriyel(n) fonksiyonunu özçağrı kullanarak hesaplamak.

alert( faktoriyel(5) ); // 120

Not: n!, n * (n-1)! şeklinde yazılabilir. Örneğin: 3! = 3*2! = 3*2*1! = 6

Tanım olarak n! faktöriyel n * (n-1)! şeklinde çalışır.

Diğer bir deyişle faktoriyel(n) n in factorial(n-1) ile çarpılmasıdır. Sonrasında n-1 1 olana kadar basamak basamak azalır.

function faktoriyel(n) {
  return (n != 1) ? n * faktoriyel(n - 1) : 1;
}

alert( faktoriyel(5) ); // 120

Özçağrı’nın tabanı 1'dir. 0'da yapılabilir, çok önemli değildir, fakat 1 özçağrı daha yapmak gerekir.

function faktoriyel(n) {
  return n ? n * faktoriyel(n - 1) : 1;
}

alert( faktoriyel(5) ); // 120
önem: 5

Fibonacci sayıları’nın akışı şu formüle göredir: Fn = Fn-1 + Fn-2. Anlamı, bir sonraki sayı kendinden önce gelen iki sayının toplamıdır.

İlk iki sayı 1'dir, sonra 2(1+1), sonra 3(1+2), 5(2+3) şeklinde devam eder: 1, 1, 2, 3, 5, 8, 13, 21...

Fibonacci sayıları Altın oran ile ilgilidir ve birçok doğal olay bunun etrafında gerçekleşir.

fib(n) fonksiyonu yazını ve bu fonksiyon n. fibonacci sayisini dönsün.

Örnek:

function fib(n) { /* kodunuz */ }

alert(fib(3)); // 2
alert(fib(7)); // 13
alert(fib(77)); // 5527939700884757

Not: Çözüm çok hızlı olmalıdır. fib(77) 1 saniyeden uzun sürmemelidir.

İlk olarak özçağrı çözümü denenebilir.

Fibonacci sayıları tanım olarak özçağrıya uygundur:

function fib(n) {
  return n <= 1 ? n : fib(n - 1) + fib(n - 2);
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
// fib(77); // aşırı derecede yavaş olacaktır!

n'in büyük değerleri için oldukça yavaştır. Örneğin fib(77) JavaScript motorunun durmasına bile neden olabilir, tüm CPU kaynağını harcayabilir.

Bunun nedeni fonksiyonun çok fazla alt çağrı yapmasıdır. Aynı değerler defalarca hesaplanır ve hesaplanır.

Örneğin fib(5) şu şekilde hesaplanır:

...
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
...

Görüldüğü gibi burada fib(3), fib(4) ve fib(5) için gereklidir. Bundan dolayı fib(5) iki defa bir birinden bağımsız olarak çalışacaktır.

Aşağıda tüm özçağrı ağacını görebilirsiniz. Öz çağrı ağacı

Gördüğünüz gibi fib(3) iki defa fib(2) ise üç defa çalıştırılır. Toplamda hesaplama n den daha hızlı bir şekilde büyür. n=77 için bu sayı çok büyük olur.

Bu daha önceden hesaplanmış değerleri hatırlayarak çözülebilir: Eğer fib(3) bir defa hesaplanırsa, bu gelecekteki hesaplamalar için tekrar kullanılabilir.

Diğer bir yöntem ise özçağrıyı hiç kullanmayıp döngü bazlı bir algoritma geliştirmektir.

n'den daha küçüğe giden sayılar yerine 1 den ve 2 den başlayıp bunları fib(3)ün değeri olarak tanımlamak mümkündür. Sonrasında fib(4) bir iki önceki değerin toplamı olur. Bu şekilde gerekli olan n değerine kadar gider. Her bir adımda sadece iki önceki değeri hatırlamak yeterli olacaktır.

Yeni algoritmanın basamakları aşağıdaki gibi olacaktır

Başlangıç:

// a = fib(1), b = fib(2), bunlar 1'in tanımıdır.
let a = 1, b = 1;

//  c'yi al = fib(3) toplamı
let c = a + b;

/* şimdi fib(1), fib(2), fib(3)'e sahibiz.
a  b  c
1, 1, 2
*/

Eğer fib(4) istenirse bu fib(4) = fib(2) + fib(3)'tür.

Değişkenlere kaydırılırsa: a,b , fib(2),fib(3) alacaktır, c ise toplamı olacaktır:

a = b; // şimdi a = fib(2)
b = c; // şimdi b = fib(3)
c = a + b; // c = fib(4)

/* akış şu şekildedir:
   a  b  c
1, 1, 2, 3
*/

Bir sonraki adım, sıradaki sayıyı vermektir:

a = b; // şimdi a = fib(3)
b = c; // şimdi b = fib(4)
c = a + b; // c = fib(5)


/* şimdiki akış ( 1 sayı fazla ):
      a  b  c
1, 1, 2, 3, 5
*/

… Bu şekilde istenen sayıya kadar devam eder. Özçağrı’dan daha hızlıdır ve aynı işlemi tekrar yapmaz.

Kodun tamamı:

function fib(n) {
  let a = 1;
  let b = 1;
  for (let i = 3; i <= n; i++) {
    let c = a + b;
    a = b;
    b = c;
  }
  return b;
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
alert( fib(77) ); // 5527939700884757

Döngü i=3 ile başlar çünkü birinci ve ikinci değerler a=1 ve b=1 şeklinde elle atanmıştır.

Bu yaklaşıma dinamik alttan yukarı programlama denir.

önem: 5

Aşağıdaki gibi bir tane tek-bağlı ( Kendini tekrarlayan ( özçağrı ) ve yığın’da gösterildiği gibi) liste olsun:

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

listeYaz(list) adında bir fonksiyon yazın ve bu tüm liste elemanlarını birer birer ekrana bassın.

Hem döngü hem de özçağrı kullanan versiyonlarını yazınız.

Hangisi daha iyidir: özçağrı ile mi yoksa döngü ile mi?

Döngü-tabanlı Çözüm

Döngü tabanlı çözüm aşağıdaki gibidir:

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

function listeYaz(list) {
  let tmp = list;

  while (tmp) {
    alert(tmp.deger);
    tmp = tmp.sonraki;
  }

}

listeYaz(list);

Dikkat ederseniz tmp adında geçici bir değişken tutarak listeni üzerinden geçildi. Bunun yerine list fonksiyon parametresi de kullanılabilir:

function listeYaz(list) {

  while(list) {
    alert(list.deger);
    list = list.sonraki;
  }

}

… Fakat çok akıllıca bir yöntem değil. İleride fonksiyonu genişletmek gerekebilir. Liste ile birşeyler yapmak gerekebilir. Eğer list değişirse bu gerekliliklerin hiç biri yerine getirilemez.

Değişken isimlerinden konuşmak gerekirse list burada liste’nin kendisidir, ilk elemanıdır ve öyle kalmalıdır. Temiz ve güvenilir.

Diğer taraftan tmp liste için aynı i'nin for için gerekliliği gibidir.

Öz çağrı çözümü

listeYaz(list)'in öz çağrı çözümü şu mantığa dayanır: Liste’nin çıktısını almak için o anki list elemanının çıktısı basılmalıdır. Sonra diğer list.sonraki elemanlarının yapılmalıdır.

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

function listeYaz(list) {

  alert(list.deger); // elemanın çıktısını bas

  if (list.sonraki) {
    listeYaz(list.sonraki); // listenin geri kalan elemanları için de aynısını yap
  }

}

listeYaz(list);

Hangisi daha iyi?

Teknik olarak döngü versiyonu daha etkilidir. İki yöntem de aynı işi yapar, fakat döngü versiyonu iç içe fonksiyonlar için kaynak harcamaz.

Diğer taraftan özçağrı versiyonu daha kısa ve bazen anlaşılması daha kolaydır.

önem: 5

Bir önceki görevde Tek-bağlı(single-linked) List'in çıktısı yazdırılan listenin tersten çıktısını yazdırınız:

Bu işlemleri döngü ve özçağrı kullanarak yapınız.

Özçağrı kullanarak

Özçağrı çözümü burada biraz çetrefilli.

Önce listenin ggeri kalanını yazdırmak sonra ise o anki değerini yazdırmak gerekmektedir.

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

function geriListeYazdır(list) {

  if (list.sonraki) {
    geriListeYazdır(list.sonraki);
  }

  alert(list.deger);
}

geriListeYazdır(list);

Döngü versiyonu

Döngü versiyonu da bir öncekine göre biraz daha karmaşıktır.

list'teki son değerin alınması gibi bir yol yoktur. Ayrıca “geri doğru” gidilemez.

Bundan dolayı elemanlar sıra ile bir diziye yazılıp sonra bu dizi sondan başa okunarak bu problem çözülebilir.

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

function geriListeYazdır(list) {
  let dizi = [];
  let tmp = list;

  while (tmp) {
    dizi.push(tmp.deger);
    tmp = tmp.sonraki;
  }

  for (let i = dizi.length - 1; i >= 0; i--) {
    alert( dizi[i] );
  }
}

geriListeYazdır(list);

İki çözüm de aynı şekilde listeyi dolanıyor ve çalıştırma yığınındaki çağrıları hatırlayıp bunları ekrana basıyor.

Eğitim haritası

Yorumlar

yorum yapmadan önce lütfen okuyun...
  • Eğer geliştirme ile alakalı bir öneriniz var ise yorum yerine github konusu gönderiniz.
  • Eğer makalede bir yeri anlamadıysanız lütfen belirtiniz.
  • Koda birkaç satır eklemek için <code> kullanınız, birkaç satır eklemek için ise <pre> kullanın. Eğer 10 satırdan fazla kod ekleyecekseniz plnkr kullanabilirsiniz)