Özyineleme ve Çözümleme

Konu Anlatımı

Özyineleme ve Çözümleme

Bir problemi çözmek için kural yazmak kadar, kuralın kendisini daha küçük bir problem için yeniden yazmak da mümkündür. Bu yaklaşıma özyineleme denir. Bir fonksiyon ya da yordum, kendisini daha küçük bir girdiyle çağırarak aynı işi yapar ve sonunda bir durma noktasına ulaşır. Ağaç yapılarında dolaşma, klasör taraması ve bazı arama problemleri bu yaklaşımla çok daha kısa kodla çözülür.

Bu derste ne öğreneceğiz?

Bu konuda özyinelemenin ne anlama geldiğini, bir özyinelemeli çözümün hangi iki parçadan oluştuğunu öğreneceğiz. Temel durum koşulunun neden zorunlu olduğunu, çağrı yığınının her çağrıda nasıl büyüdüğünü somut örneklerle izleyeceğiz. Faktorial, Fibonacci, dizi tersten yazdırma ve Hanoi problemi gibi klasik örnekleri adım adım çözeceğiz. Ayrıca böl ve çöz yaklaşımını, özyinelemenin döngüye göre avantaj ve dezavantajlarını karşılaştıracağız.

Ön bilgi

Ön bilgi olarak fonksiyon kavramı gerekir. Fonksiyon yazmak, belirli bir işi yapan ve adıyla çağrılan birimdir; girdi alır, işlem yapar ve sonuç döndürür. Fonksiyon başka bir fonksiyonu çağırabilir ve hatta kendisini de çağırabilir. Bu son durum özyinelemedir.

İkinci ön bilgi veri tipleri ve dizilerdir. Özyinelemeli çözümlerde çoğunlukla bir tam sayı ya da bir dizi üzerinde çalışılır ve her çağrıda bu girdinin küçüldüğü görülür. Dizi elemanlarına erişmek için sıra numarası kullanılır ve son elemanla başka elemanlara ayrı ayrı yaklaşılır.

Özyineleme nedir?

Özyineleme, bir fonksiyonun kendisini çağırmasıdır. Çağrı, kendisine verilen girdi daha küçük olduğunda tekrarlanır ve girdi artık indirgenemeyecek kadar küçüldüğünde işlem biter. Buradaki küçülme çok önemlidir: girdi hiç değişmeden aynı fonksiyon çağrılırsa işlem hiç bitmez ve program çöker.

Özyinelemeli bir çözüm iki parçadan oluşur. Birincisi temel durumdur; girdi indirgenemeyecek kadar küçüldüğünde doğrudan sonuç üretilir. İkincisi, girdiyi küçülterek kendini çağıran gövdedir. Bu iki parça birbirine karıştırılmamalıdır; temel durum olmadan özyineleme hiçbir zaman durmaz.

Temel durum ve ilerleme koşulu

Temel durum, sorunun en küçük hâlidir ve doğrudan çözülür. Bu durumda kendini çağırma yapılmaz, çünkü girdi artık indirgenemez. Örneğin bir dizinin tersten yazdırılmasında tek elemanlı dizi temel durumdur; tek eleman zaten ters kendisidir.

İlerleme koşulu ise çağrının her tekrarda girdiyi nasıl küçülttüğünü gösterir. Küçültme yalnızca bir döngü sayacı artırmakla olmaz; girdinin anlamlı biçimde değişmesi gerekir. Alt problem çözüldükten sonra elde edilen sonuç, üst çağrıya döndürülerek birleştirilir. Bu iki aşamalı yapı, böl ve çöz yaklaşımının çekirdeğidir.

Çağrı yığını nasıl çalışır?

Bir fonksiyon başka bir fonksiyonu çağırdığında, program hâlihazırda çalışan çağrının bilgisini bir çağrı yığını bölgesinde saklar. Bu saklama, bir kitapta anahtar kancalarını üst üste takmak gibidir: en son takılan anahtar en üstte durur ve program onu önce çıkarır.

Özyinelemede her yeni çağrı yığını bir büyütür. Yığın derinliği, henüz temel duruma ulaşmamış çağrı sayısına eşittir. Örneğin beş elemanlı bir diziyi tersten yazdıran özyinelemeli bir çözümde, son elemana kadar beş kez çağrı yapılır ve altıncı çağrı temel durumdur. Yığın büyüklüğünün bir sınırı olmadığı için çok derin özyineleme yığın taşmasına yol açar.

Faktoriyel ve basit özyinelemeli örnekler

Faktoriyel, bir sayının kendisiyle bir altındaki sayının çarpımıdır. Beş için sonuç 1 × 2 × 3 × 4 × 5 = 120 olur. Özyinelemeli çözümde fonksiyon, sayı sıfırdan küçük veya bire eşitse bir döner; değilse kendi sonucunu bir alt sayının faktoriyeliyle çarpar.

Dizi toplamı da benzer biçimde çözülür. Bir elemanlı dizi için toplam, o elemanın kendisidir. Daha uzun dizilerde son eleman, kalan bölümün toplamına eklenir. Bu iki örnek, özyinelemeli bir çözümün iskeletini öğretmek için idealdir; çünkü hem temel durum hem de indirgeme açıkça görünür.

Fibonacci dizisi ve ağaç yapılarında gezinme

Fibonacci dizisinde her terim, kendinden önceki iki terimin toplamıdır. İlk altı terimin toplamı 1 + 1 + 2 + 3 + 5 + 8 = 20 eder. Bu dizi özyinelemeyle kolay yazılır fakat verimsizdir; çünkü aynı alt problem defalarca yeniden hesaplanır ve hesap sayısı terim sayısına göre çok hızlı büyür.

Verimli hâli, hesaplanan alt problemlerin saklanmasıyla elde edilir. Ağaç yapılarında dolaşım da özyinelemenin doğal alanıdır. Bir düğümün sol dalı için yapılan işlem, sağ dalı için de birebir aynıdır. Bu nedenle hiyerarşik veriler, özyineleme olmadan çok daha uzun ve hataya açık kod yazmayı gerektirir.

Böl ve çöz yaklaşımı

Böl ve çöz yaklaşımında problem önce benzer alt problemlere ayrılır, alt problemler çözülür ve sonuçlar birleştirilir. Sıralama örneğinde dizi ikiye bölünür, parçalar ayrı ayrı sıralanır ve sonra uygun sırada göre birleştirilir. Bu yöntemin karşılaştırma sayısı veri sayısına çok daha yavaş büyür.

Özyineleme, bu yaklaşımı uygulamak için en uygun araçtır. Sekiz elemanlı bir dizide bölme işlemi 8 / 2 = 4 elemanlı iki parça üretir, sonraki adımda 4 / 2 = 2 elemanlı parçalar oluşur. Sayısal iddianın ikisini de ara adımda doğrulamak, yöntemin mantığını kavramak için faydalıdır.

Özyineleme mi döngü mü?

İki yaklaşım aynı işi yapabilir. Döngü, tekrarlayan sayacı takip eder ve ek bellek gerektirmez. Özyineleme ise problemi doğrudan problemciğe benzer biçimde küçük parçalara indirger; bu yüzden hiyerarşik verilerde ve matematiksel tanımlarda çok daha anlaşılır olur. Hangisinin seçileceği, kodun okunabilirliğine ve derinliğine göre belirlenir.

Performans açısından özyinelemenin bedeli vardır. Her çağrı için yeni bir çerçeve oluşur ve oluşturulan çerçeve ancak döndüğünde serbest kalır. Bu nedenle derin özyinelemelerde döngüye göre daha fazla bellek ve zaman harcanır. Sonsuz özyineleme ise yığını taşırarak programın çökmesine yol açar.

Sonsuz özyineleme ve yığın taşması

Yığın taşması, çağrı yığınının izin verilen sınırı aşmasıdır. En yaygın nedeni, girdiyi küçültmeden kendini çağırmaktır. Böyle bir durumda hiçbir zaman temel duruma ulaşılamaz ve program belleği doldurup kapanır. Bu nedenle özyinelemeli bir yazılımı denetlerken ilk bakılacak yer temel durum koşuludur.

İkinci neden, indirgemenin başarısız olmasıdır. Girdi bir altına düşmek yerine aynı değerde kalıyorsa koşul sağlanmaz. Üçüncü neden, iki koşuldan yalnızca birinin doğru yazılmasıdır. Temel durum ve çağrı adımının birlikte doğru kurulması, özyinelemeli bir çözümün temel güvenlik kuralıdır.

Basit örnek

Tek elemanlı bir dizi düşünülsün: 7. Özyinelemeli tersten yazdırma fonksiyonu çağrıldığında ilk olarak dizi uzunluğu bir mi diye bakılır. Uzunluk bire eşit olduğu için temel durum çalışır ve 7 doğrudan yazdırılır. Çağrı daha derinlere gitmeden sonlanır ve program kapanır.

Üç elemanlı 3, 5, 8 dizisinde ise çağrı zinciri oluşur: üç eleman görülür, son eleman olan 8 yazdırılır, kalan iki eleman için çağrı tekrarlanır. Sonunda 5, sonra 3 yazdırılır. Çıktı 8, 5, 3 sırasıyla olur; yığın derinliği üç çağrıdır.

İleri örnek

Bir klasör ağacında arama yapılacaktır. Klasörün içindeki dosya adları ve alt klasörler karışık sırada olabilir. Özyinelemeli bir çözümde ilk adımda klasörün adı aranır; eşleşme bulunursa işlem durdurulur. Eşleşme yoksa alt klasörlerin her biri için aynı arama yeniden çağrılır.

Bu tasarımda iki dikkat noktası vardır. Birincisi, hiçbir daldan dönüldüğünde aramanın kaldığı yerden devam etmesi gerekir. İkincisi, sonuç bulunduğunda diğer dallarda arama yapılmaması sağlanmalıdır. Bu iki koşul sağlanmazsa arama ya eksik kalır ya da gereksiz yere bütün ağacı dolaşır.

Adım adım çözülmüş örnek

Görev: Üç diskli Hanoi probleminde gereken hamle sayısını bulmak. Çözüm: Adım 1: Temel durum belirlenir; tek disk zaten yerindedir ve hamle gerekmez. Adım 2: Üç disk için önce üstteki iki disk yardımcı kuleye taşınır. Adım 3: En büyük disk hedef kuleye taşınır. Adım 4: Yardımcı kuledeki iki disk hedef kuleye taşınır.

Bu dört adımda alt problem kendi içinde çözülür ve sonuçları birleştirilir. Toplam hamle sayısı bir formülle verilir: üç disk için 2³ − 1 = 7, beş disk için 2⁵ − 1 = 31 hamle gerekir. Disk sayısı yalnızca bir arttığında hamle sayısı iki katına çıkar; bu nedenle bu problem, özyinelemeli yaklaşımın gücünü göstermek için sık kullanılır.

Kavram karşılaştırma tablosu

Sık Yapılan Hatalar

• Hata: Temel durum koşulunu yazmamak. Doğrusu: Çağrının duracağı en küçük hâl açıkça tanımlanır.
• Hata: Çağrıda girdiyi küçültmemek. Doğrusu: Her çağrıda daha küçük ve daha basit bir girdi verilir.
• Hata: Temel durumda da kendini çağırmak. Doğrusu: Temel durum doğrudan sonuç döndürür, çağrı yapılmaz.
• Hata: Alt problemin sonucunu döndürmeyi unutmak. Doğrusu: Çağrıdan dönen değer birleştirilerek üst çağrıya verilir.
• Hata: Fibonacci gibi tekrarlı hesaplarda önbellek kullanmamak. Doğrusu: Hesaplanan alt problemler saklanarak tekrar hesap önlenir.
• Hata: Derin özyinelemede yığın taşmasını hata sanmamak. Doğrusu: Taşma, koşullardan birinin hiç sağlanmadığı anlamına gelir.
• Hata: Her sorunu özyineleme ile çözmeyi seçmek. Doğrusu: Döngü yeterliyse döngü, okunabilirlik önceliklidir.
• Hata: Ağaç gezinmesinde dönüş noktasını atlamak. Doğrusu: Alt dala girildiğinde kaldığı yer hatırlanır ve taranan yer bitince geri dönülür.

Özet

Özyineleme, bir fonksiyonun kendisini çağırmasıdır ve iki parçadan oluşur: temel durum ile girdiyi küçülterek çağrıyı tekrarlayan gövde. Temel durum sağlanmazsa ya da girdi küçülmezse çağrı zinciri hiç bitmez ve yığın taşması oluşur. Ağaç dolaşımı, klasör taraması ve böl ve çöz yaklaşımı özyinelemeyi doğal kılan problemlerdir. Özyineleme hiyerarşik yapılarda anlaşılır olmakla birlikte her çağrı için ek yük getirdiğinden büyük girdilerde döngüye göre yavaştır. Tekrarlı hesap yapılan problemlerde alt sonuçları saklamak, hesap sayısını belirgin biçimde azaltır.

Kendini dene

Kendin dene bölümünde üç görev yap. Birincisi, verilen bir diziyi özyineleme ile tersten yazdıran bir çözüm yaz ve çağrı yığınının derinliğini belirt. İkincisi, aynı işi bir döngü ile yaz ve iki yöntemi satır sayısı ile süre açısından karşılaştır. Üçüncüsü, üç diskin Hanoi problemindeki hamleleri kâğıda çiz. Puanlama notu: temel durum koşulunu belirtmeyen bir özyinelemeli çözüm eksik kabul edilir.