Temeller Posts

Recursion (Özyineleme)

recursion

Programlamaya yeni başladığım zamanlarda bir arkadaşım kendi web sitesinde kendisinin tanımlayabileceği bir ağaç yapısı yazmak için yardımımı istemişti. Ağacın ana dallarını çok basit bir şekilde yazmıştık ama karşımıza çok zor bir sorun çıkmıştı; “ana dallara bağlı olan alt dalların uzunluğu ve sayısı sabit değil idi”.

 

Dalların sayısı ve uzunluğu belirsiz olduğu için, basit bir (yada birkaç) for döngüsü ile ağacı oluşturmamız pek olası durmuyordu. Eğer uzunluklar ve sayılar sabit olsa işimiz kolaydı ama ne yazık ki (aslında ne iyi ki, programlama her zaman karşımıza çözmemiz gereken problemler çıkarır) karşımızda çözülmeyi bekleyen kocaman bir problem vardı. BELİRSİZ UZUNLUKTA TEKRARLILIK.

 

Bu kısıma devam etmeden önce ALGORİTMA yazımı okumanızı tavsiye ederim.

 

Şimdi gelelim problemin yapısına ve çözümüne; elimizde aşağıdaki gibi bir tablo olduğunu varsayalım.

Numara Üst Numara Numara Üst Numara Numara Üst Numara
1 2 1,2,1 1,2
1,1 1 2,1 2 1,2,2 1,2
1,2 1 2,2 2 1,2,3 1,2
1,3 1 2,3 2 1,2,4 1,2
1,4 1 2,4 2 2,2,1 2,2
1,1,1 1,1 2,1,1 2,1 2,2,2 2,2
1,1,2 1,1,1 2,1,2 2,1,1 2,2,3 2,2
1,1,1,1 1,1,1 2,1,1,1 2,1,1 2,2,4 2,2
1,1,1,2 1,1,1 2,1,1,2 2,1,1 2,2,5 2,2

 

Bu tablo içerisindeki verileri birer kart yada taş gibi fiziksel nesneler olarak düşünelim ve bunları elimizle masanın üzerine dizdiğimizi düşünelim. Ne yapardık? Öncelikle üst numarası olmayan taşları dizeriz.

  1. 1 numaralı taşın altına üst numarası 1 olan taşları dizeriz.
  2. 2 numaralı taşın altına üst numarası 2 olan taşları dizeriz.
  3. 1.1 numaralı taşın altına üst numarası 1.1 olan taşları dizeriz.
  4. 1.2 numaralı taşın altına üst numarası 1.2 olan taşları dizeriz.
  5. 2.1 numaralı taşın altına üst numarası 2.1 olan taşları dizeriz.
  6. 2.2 numaralı taşın altına üst numarası 2.2 olan taşları dizeriz.
  7. 1.1.1 numaralı taşın altına üst numarası 1.1.1 olan taşları dizeriz.
  8. 1.1.2 numaralı taşın altına üst numarası 1.1.2 olan taşları dizeriz.

Yukarı da ki işlemleri sürekli bir şeyi tekrar ettik fark ettiyseniz, sıradaki üst numarasını taşıyan taşları bul ve yerleştir. Ama bu akış insan için görece kolay olsa bile makina için zorludur. Bu akışı makina için daha kolay olacak bir düzene sokmamız gerekiyor o da aşağıdaki gibidir.

  1. Üst numarası olmayan taşları dizeriz.
  2. 1 numaralı taşın altına üst numarası 1 olan taşları dizeriz.
  3. 1.1 numaralı taşın altına üst numarası 1.1 olan taşları dizeriz.
  4. 1.1.1 numaralı taşın altına üst numarası 1.1.1 olan taşları dizeriz.
  5. 1.1.2 numaralı taşın altına üst numarası 1.1.2 olan taşları dizeriz.
  6. 1.2 numaralı taşın altına üst numarası 1.2 olan taşları dizeriz.
  7. 2 numaralı taşın altına üst numarası 2 olan taşları dizeriz.
  8. 2.1 numaralı taşın altına üst numarası 2.1 olan taşları dizeriz.
  9. 2.2 numaralı taşın altına üst numarası 2.2 olan taşları dizeriz.

Bu akış makina için daha kolay ve anlamlıdır. Akışı açıklayacak olursak; Üst numarası olmayan taşı yerleştir, üst numarası az önce yerleştirdiğim olan taşı yerleştir, üst numarası az önce yerleştirdiğim olan taşı yerleştir,üst numarası az önce yerleştirdiğim olan taşı yerleştir şeklinde taşlar bitene kadar devam eder.

 

Fark ettiyseniz işleyişin yapısı, “ÜstNumarası-X-OlanTaşlarıYerlestir” akışının/methodunun (X ilk sefer için boş oluyor) her eklenen taş yeni X değerimiz olarak tekrar tekrar çağırılmasıdır. Yani “ÜstNumarası-X-OlanTaşlarıYerlestir” methodu kendi kendini çağıran bir method olması gerekiyor.

Şimdi gelin bunu bir gerçek kodlar ile yazalım.

 

 

 

Örnekte de gördüğünüz üzere, methodun kendi kendisini çağırması yardımı ile belirsiz uzunlukta ve yapıdaki bir ağacın bütün dallarında dolaştık. Örnekte yaptığımız, bir methodun kendisini çağırması işlemine Recursion(Öz Yineleme) denir.

 

Makale de kullanılan örneği içeren projeyi Github‘da bulabilirsiniz.

 

Bir sonraki yazıda görüşmek ümidiyle.

Sen de kimsin “YIELD”?

whoareyou

Bir zamanlar yakışıklı ama insanı yoran IteratorPattern (Başka bir yazının konusu) adında bir yapı yaşarmış. Ta ki .Net 2.0 ile birlikte gelen “yield” keywordu’ne kadar. yield büyük bir hızla bu yapıyı unutturup kendi hükümdarlığını kurdu.

Peki bu yield adındaki arkadaş ne iş yapar?

Kabaca; çalışma yapısı ??kullanıcıya?? gösterilmek istenmeyen, sıralı nesnelerin (dizi) akışının beslenmesini sağlar. Biliyorum çok anlaşılır olmadı ama bir örnek ile anlatırsam daha anlaşılır olacak.

Varsayalım; sizden bir klasör ve onun alt klasörü içinde bulunan bütün dosyaların listeleyecek bir method yazmanız istendi. Ama bu methodun bir özel durumu var; bütün listeyi tek seferde almak istemiyor. Çünkü her dosya ile yapacağı işlem uzun ve bu süre zarfında hafızada o kadar veriyi tutmak istemiyor.

Eskiden olsa IteratorPattern ile bu işi hallederdik ama onu yazmak başlı başına bir sıkıntı zaten. Sağolsun yield bizi bu dertten kurtarıyor. Nasıl derseniz, aşağıdaki kodu beraber inceleyelim.

İlk aşamada, belirtilen klasordeki dosyaların listesi  alınır ve liste içerisinde bulunan dosya isimleri yield yardımı ile teker teker bu bilgiyi kullanacak kaynağa iletilir. yield return satırı her iletim anında bekleme durumuna geçer, ta ki sıradaki eleman okunmak istenene kadar kodumuz bu satır üzerinde bekler. Okuma istediği geldiği zaman, bir sonraki yield return e kadar çalışır ve yeni okuma talebini bekler.

İkinci aşamada, klasör içerindeki klasorlerin listesi alınır ve her klasor için, methodumuz tekrar çağırılır. (Bu işleme recursion denir ki bu da başka bir makale konusu)

YIELD arkadaşımızın tanıtımı bu kadar. Umarım sizde kendisini benim onu sevdiğim kadar sevmişsinizdir. 🙂

 

NOT: Eğer .Net Framework 4.0 yada daha üst bir sürüm ile uygulama geliştiriyorsanız yukarıdaki kodu kullanmak yerine Directory.EnumerateFiles methodunu kullanmanızı tavsiye ederim.

 

NOT2:  Önünüzde bir problem olduğu zaman (örneğimizde kısıtlı ram kullanımı ile büyük verinin aktarımı problemini çözdük) öncelikle kullandığınız dilin kendi standart kütüphanesinde probleminizin çözümü var mı diye araştırın. Eğer varsa Amerika’yı yeniden keşfetmek yerine hazır çözümü kullanın.