Ö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.