Recursion (Özyineleme)
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 numaralı taşın altına üst numarası 1 olan taşları dizeriz.
- 2 numaralı taşın altına üst numarası 2 olan taşları dizeriz.
- 1.1 numaralı taşın altına üst numarası 1.1 olan taşları dizeriz.
- 1.2 numaralı taşın altına üst numarası 1.2 olan taşları dizeriz.
- 2.1 numaralı taşın altına üst numarası 2.1 olan taşları dizeriz.
- 2.2 numaralı taşın altına üst numarası 2.2 olan taşları dizeriz.
- 1.1.1 numaralı taşın altına üst numarası 1.1.1 olan taşları dizeriz.
- 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.
- Üst numarası olmayan taşları dizeriz.
- 1 numaralı taşın altına üst numarası 1 olan taşları dizeriz.
- 1.1 numaralı taşın altına üst numarası 1.1 olan taşları dizeriz.
- 1.1.1 numaralı taşın altına üst numarası 1.1.1 olan taşları dizeriz.
- 1.1.2 numaralı taşın altına üst numarası 1.1.2 olan taşları dizeriz.
- 1.2 numaralı taşın altına üst numarası 1.2 olan taşları dizeriz.
- 2 numaralı taşın altına üst numarası 2 olan taşları dizeriz.
- 2.1 numaralı taşın altına üst numarası 2.1 olan taşları dizeriz.
- 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Recursion recursion = new Recursion(); foreach (var tas in recursion.SirasizTaslar.Where(t => string.IsNullOrEmpty(t.UstNumara))) { recursion.TasYaz(tas); } public void UstNumarasi_X_OlanlariYerlestir(string X) { List<Tas> UstNumarasi_X_OlanTaslar = _sirasizTaslar.Where(t => t.UstNumara.Equals(X)).ToList(); foreach (Tas t in UstNumarasi_X_OlanTaslar) { TasYaz(t); } } |
Ö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.