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.

Algoritma Nedir?

Yazılım ile uğraşanların ya da bir yazılımcı ile azıcık bile olsa sohbet etmiş herkesin duyduğu bir kelimedir algoritma. Peki bu kelimenin anlamı nedir? Ne işe yarar? Yenir mi, içilir mi yoksa üzerine binip gezilir mi?

Tabii ki böyle bir şey değildir. Wikipedia‘da “Belli bir problemi çözmek veya belirli bir amaca ulaşmak için çizilen yol” şeklinde tanımlanıyor. Bu tanım yanlıştır demiyorum elbette ama benim daha güzel bir tanımım var! Algoritma, kendini tanımaktır/anlamaktır (ve gerekiyorsa yeniden yapılandırmaktır). Bu kısa tanım çok açıklayıcı olmadı biliyorum bu yüzden biraz daha açmam gerek.

Algoritma tanımını açmadan önce yazılımın ne olduğundan kısaca bahsedeyim. Yazılım işinin insan (kullanıcı) tarafı ve makine tarafı olmak üzere iki yönü vardır. Konumuz gereği ben şimdi makine yönünden bahsedeceğim. Yazılımın insan yönü ise başka bir makale konusudur.

Yazılımın makine tarafı, özünde tercümanlık işidir. Yani elimizdeki bilgiyi (girdiler, iş akışları, süreçler vb.) yabancı bir dil yardımı ile yabancı bir kimseye (yazılım işinde bu kimse bilgisayardır) anlatma eylemidir. Yazılım işinde bir şeyler anlattığımız kişi, otizmli bir insana benzer. Yapabildiği bazı şeyler (hızlı hesaplama ya da söylediklerinizi harfi harfine aklında tutabilme becerisi gibi) sizde muazzam bir hayranlık oluştururken, anlatımlarınızda bulunan boşlukları kendi kendine dolduramaması, ille de herşeyi net bir biçimde anlatmanızı beklemesi, net olarak anlat(a)madığınız şeyleri yap(a)maması sizi rahatsız eder, hatta zaman zaman çileden bile çıkarabilir. İşimiz yazılım (tercümanlık) gereği karşımızda bulunan bilgisayara (sanki otizmli insana anlatıyormuş gibi) hedeflediğimiz çıktıyı(anlatmamız istenilen) elde etmek için yapılacak işleri uygun bir şekilde anlatmamız gerekir.

İşte algoritma yani kendimizi tanımamız/anlamamız burada devreye girer. İnsan olarak sahip olduğumuz bir çok beceri ve yapabildiğimiz çok fazla şey var ancak çoğu zaman yaptığımız şeyleri üzerinde düşünerek yapmayız. Örnek verecek olursak; Türkçe konuşan herkes herhangi bir kelimeyi hecelerine ayırma becerisine sahiptir. Ama hecelere ayırma işlemini nasıl yapacağımızı düşünerek yapmayız. Sadece heceleriz. Peki, heceleme işlemini, heceleme becerisine/bilgisine sahip olmayan birine nasıl anlatacağız? Bu işi yapmak için önce bilinçsiz şekilde yaptığımız hecele eylemini bilinçli yapabildiğimiz bir hale çevirmeliyiz. Yani kendimizi tanımalı/anlamalıyız.

Bilinçsiz bir şekilde yaptığımız bir şeyi bilinçli hale nasıl çevirebiliriz yani kendimizi daha iyi nasıl anlarız. Eğer deneyimli bir yazılımcı iseniz zaman içinde (deneyim edindiğiniz süreçte) beyninizi, bu işlemleri hızlıca yapacak şekilde yönlendirmişsinizdir/eğitmişsinizdir. Peki yeni başlamış bir yazılımcı iseniz yada yazılımcı bile değilseniz bu süreci nasıl işleteceksiniz?

Gelin bu bilinçli hale çevirme sürecini basitten zora 3 örnekle inceleyelim.

  • Çay demleme

Çay demleme işlemi en temel seviye algoritmalardandır. İçinde açıklığa kavuşması gereken bir yöntem yada düşüncemizi yeniden yapılandırmamızı gerektiren bir unsur yoktur. Yapılacak işlemler ve yapılma şartları vardır. Çay demleme işlemi, eylemlerin adımlanması ile halledilir. Bu adımlar aşağıdaki gibidir.

  1. Mutfağa git
  2. Dolabın kapağını aç
  3. Çaydanlığı çıkar
  4. Çaydanlığın altına su koy
  5. Ocağı yak
  6. Çaydanlığı ocağın üstüne koy
  7. Kaynayana kadar bekle
  8. Demliğe çay koy
  9. Demliğe çaydanlığın altındaki kaynar suyu koy
  10. Alt ve demliği ocağa koy
  11. 15 dk bekle.

Bu adımlar ile çayımızı demlemiş olduk. Yaptığımız işlem özünde, yapılan işi, anlamlı küçük parçalara ayırıp bir düzen içinde uygulamaktı.

  • Batak oyunu kart dağıtımı (İskambil kağıtlarının 4 kişiye dağıtılması)

Bu algoritma bir öncekine göre daha zor bir algoritmadır. Bunun nedeni ise insan olarak kolay yaptığımız bazı işlemlerin makineye anlatımı, yaptığımız kadar kolay değildir. Bu nedenle düşünce yapımızı değiştirmemiz gerekir. Gerçek hayatta, batak oyunu için kartları dağıtma işlemini algoritmaya dökersek;

  1. Kartları karıştır
  2. Birinci kişiye bir kağıt ver
  3. İkinci kişiye bir kağıt ver
  4. Üçüncü kişiye bir kağıt ver
  5. Dördüncü kişiye bir kağıt ver
  6. 2-5 arasındaki işlemleri kartlar bitene kadar tekrar et.

Bu algoritma yanlış bir algoritma değildir ama kartları karıştırma işlemi kendi başına bir algoritmaya sahiptir ki o algoritmayı çözmek ve uygulamak yerine yaklaşık aynı performansta(büyük ihitmalle daha yüksek performansta) çalışacak başka bir algoritma yazmayı tercih ederiz. Bu algoritma ise;

  1. Rastgele bir kart seç (rastgele, halihazırda (neredeyse) her programlama dilinin içinde bulunan bir komut olduğu için tekrardan keşfetmeden olduğu gibi kullanabiliriz)
  2. Seçilen kartı birinci kişiye ver
  3. Rastgele bir kart seç
  4. Seçilen kartı ikinci kişiye ver
  5. Rastgele bir kart seç
  6. Seçilen kartı üçüncü kişiye ver
  7. Rastgele bir kart seç
  8. Seçilen kartı dördüncü kişiye ver
  9. 1-8 arasındaki işlemleri kartlar bitene kadar tekrar et.

Burada yaptığımız insan için kolay ama makineye anlatımı zor olan, “karıştırma” işlemini kullanmaktan kaçınmak için mevcut düşünce yapımızı yani süreci yeniden şekillendirip uygulamak oldu. Bu algoritmayı bir önceki algoritmadan zor kılan şey, bu yeniden yapılandırma işlemimizdir.

  • He-ce-le-me 

Bu algoritma, üniversite 3. sınıfta yazıdan-sese uygulaması yapmayı denersem nelere ihtiyacım olur diye düşünürken “Türkçe aslında harflerden değil hecelerden oluşan bir dildir. Yani çıkardığımız her ses bir hecedir, dolayısı ile bütün hecelerin, vurguları ile beraber ses aralıkları belirlenirse çok kolay bir şekilde Türkçe yazıdan-sese uygulaması yazılabilir.” çıkarımımdan doğdu. Bu çıkarımın doğruluğu yada etkinliği tartışılır tabii ki ama bu çıkarımı doğru kabul edersek yazıdan-sese uygulaması yapmak şu şekilde olacaktır;

  1. Cümleyi kelimelere ayır
  2. Her kelimenin
    • Her hecesi için
      • İlgili sesi çal

Bu akışta, bir cümleyi kelimelerine ayırma işlemi kolaydır. Boşluklara göre bölerek bir dizi oluşturabiliriz. Ama heceleme işlemine geldiğimiz zaman işimiz zorlaşacak çünkü dilimize en kolay gelen şekilde bir kelimeyi hecelerine ayırırız ama makine, insan diline sahip olmadığı için kendisine kolay gelen şekilde ayırmak gibi bir yeteneğe de sahip değildir. Peki bu zorluk karşısında ne yaptım? Nasıl hecelediğimizin cevabını aradım ve aradığım cevabı istatistik yardımı (dağılım düzeni) ile buldum. Hecelerin içindeki harf miktarları çeşitli olacak şekilde 20-30 kelimeyi hecelerine ayırdım. Sonra bu hecelerde bulunan sessiz harflere “0” sesli harflere “1” dedim. İlk bakışta gördüğüm (ki aslında ilk okul zamanında birçoğumuza öğretildiği şekilde) her hecede yalnızca bir tane “1” olduğu idi. İkinci farkındalığım; sessiz harflerin dağılım şeklinde, tek “0” ile başlayanların ezici bir çoğunluk olduğu idi. “1” ile başlamayan hecelere baktığım zaman ise bu hecelerin ya ilk hece yada “1” ile biten hecenin ardından geldiği idi (Ör: Sa-at). Son tespitim ise birden çok “0” ile başlayan hecelerin yalnızca ilk hece olması idi.

Bu tespitler ışığında şu sonuca ulaştım; “Mümkün olduğu sürece her hece tek sessiz ile başlar.” Bu sonucu ise şu şekilde bir algoritmaya döktüm;

  1. İlk sesli harfi bul
    • Eğer bulamazsan bu bir kelime değildir
  2. İkinci sesli harfi bul
    • Eğer bulamazsan metnin tümü hecedir.
  3. İki sesli harf arasındaki harf sayısını bul
    • Ardışık değerler ise ikinci sesli harfe kadar olan kısım hecedir.
    • Diğer durumlarda ise ikinci sesli harfin bir gerisindeki harfe kadar olan kısım hecedir. (Sonucun kullanıldığı işlem)
  4. İlk heceyi yok sayarak, 1-3 arası adımları bütün 2. adım başarısız olana kadar tekrar et.

 

Yukarıda anlattığım örneklerde; “yaptığımız işin adımları üzerine düşünüp sıraya koyduk”, “işi yapış şeklimizi daha kolay anlatılabilecek bir formata soktuk” ve son olarak “kurallarına hakim olmadığımız bir düzenin kurallarını netleştirdik”. İşte algoritma dediğimiz şey bu işlemlerin bir yada bir kaçıdır.

 

Gelecek makale de görüşmek dileği ile.

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.