Özyineleme, bilgisayar bilimleri ve matematikte, işlevlerin kendilerini çağırmasına olanak tanıyan, karmaşık sorunların yinelemeli adımlarla çözülmesine olanak tanıyan temel bir kavramdır. Özyinelemeli işlevlerin yürütülmesini anlamak ve analiz etmek için yaygın olarak kullanılan görsel temsillerden biri özyineleme ağacıdır. Bu makalede özyineleme ağaçlarının ardındaki teoriyi, yapılarını ve özyinelemeli algoritmaları anlamadaki önemini inceleyeceğiz.
Özyineleme Ağacı Nedir?
Özyineleme ağacı, özyinelemeli bir işlevin yürütme akışını gösteren grafiksel bir temsildir. Özyinelemeli çağrıların görsel bir dökümünü sağlayarak, algoritmanın dallara ayrılarak en sonunda bir temel duruma ulaştıkça ilerleyişini gösterir. Ağaç yapısı, zaman karmaşıklığının analiz edilmesine ve ilgili özyinelemeli sürecin anlaşılmasına yardımcı olur.
Ağaç Yapısı
Özyineleme ağacındaki her düğüm belirli bir özyinelemeli çağrıyı temsil eder. İlk çağrı üstte gösterilir ve sonraki çağrılar onun altında dallara ayrılır. Ağaç aşağıya doğru büyüyerek hiyerarşik bir yapı oluşturur. Her düğümün dallanma faktörü, işlev içinde yapılan yinelemeli çağrıların sayısına bağlıdır. Ek olarak ağacın derinliği, temel duruma ulaşmadan önceki özyinelemeli çağrıların sayısına karşılık gelir.
Temel Durum
Temel durum özyinelemeli bir fonksiyon için sonlandırma koşulu görevi görür. Özyinelemenin durduğu ve fonksiyonun değer döndürmeye başladığı noktayı tanımlar. Bir özyineleme ağacında, temel durumu temsil eden düğümler, başka özyinelemeli çağrılarla sonuçlanmadığından genellikle yaprak düğümler olarak gösterilir.
Yinelenen Çağrılar
Özyineleme ağacındaki alt düğümler, işlev içinde yapılan özyinelemeli çağrıları temsil eder. Her alt düğüm ayrı bir özyinelemeli çağrıya karşılık gelir ve bu da yeni alt problemlerin yaratılmasına neden olur. Bu özyinelemeli çağrılara iletilen değerler veya parametreler farklılık gösterebilir ve bu da alt problemlerin özelliklerinde farklılıklara yol açabilir.
java eşittir
Yürütme Akışı:
Bir özyineleme ağacında geçiş yapmak, özyinelemeli bir işlevin yürütme akışına ilişkin bilgiler sağlar. Kök düğümdeki ilk çağrıdan başlayarak, temel durumla karşılaşıncaya kadar sonraki çağrılara ulaşmak için dalları takip ederiz. Temel durumlara ulaşıldığında, özyinelemeli çağrılar geri dönmeye başlar ve ağaçtaki ilgili düğümleri, döndürülen değerlerle işaretlenir. Geçiş, ağacın tamamı geçilene kadar devam eder.
Zaman Karmaşıklığı Analizi
Özyineleme ağaçları, özyinelemeli algoritmaların zaman karmaşıklığının analizine yardımcı olur. Ağacın yapısını inceleyerek yapılan özyinelemeli çağrı sayısını ve her seviyede yapılan işi belirleyebiliriz. Bu analiz, algoritmanın genel verimliliğinin anlaşılmasına ve olası verimsizliklerin veya optimizasyon fırsatlarının belirlenmesine yardımcı olur.
giriiş
- Bir sayının faktöriyelini belirleyen bir program düşünün. Bu fonksiyon girdi olarak N sayısını alır ve sonuç olarak N'nin faktöriyelini döndürür. Bu fonksiyonun sözde kodu şuna benzeyecektir:
// find factorial of a number factorial(n) { // Base case if n is less than 2: // Factorial of 0, 1 is 1 return n // Recursive step return n * factorial(n-1); // Factorial of 5 => 5 * Factorial(4)... } /* How function calls are made, Factorial(5) [ 120 ] | 5 * Factorial(4) ==> 120 | 4. * Factorial(3) ==> 24 | 3 * Factorial(2) ==> 6 | 2 * Factorial(1) ==> 2 | 1 */ - Özyineleme daha önce bahsedilen fonksiyonla örneklenmiştir. Bir sayının faktöriyelini belirlemek için bir fonksiyon çağırıyoruz. Daha sonra aynı sayının daha küçük bir değeri verildiğinde bu fonksiyon kendisini çağırır. Bu, artık işlev çağrısının olmadığı temel duruma ulaşana kadar devam eder.
- Özyineleme, sonucun aynı sorunun daha küçük örneklerinin sonuçlarına bağlı olduğu durumlarda karmaşık sorunları ele almak için kullanılan bir tekniktir.
- Fonksiyonları düşünürsek, bir fonksiyon temel duruma ulaşana kadar kendisini çağırmaya devam ediyorsa özyinelemeli olduğu söylenir.
- Herhangi bir özyinelemeli fonksiyonun iki temel bileşeni vardır: temel durum ve özyinelemeli adım. Temel duruma ulaştığımızda özyinelemeli aşamaya gitmeyi bırakırız. Sonsuz yinelemeyi önlemek için temel senaryoların uygun şekilde tanımlanması gerekir ve bu çok önemlidir. Sonsuz özyinelemenin tanımı, temel duruma asla ulaşmayan bir özyinelemedir. Bir program hiçbir zaman temel duruma ulaşmazsa yığın taşması meydana gelmeye devam eder.
Özyineleme Türleri
Genel olarak konuşursak, özyinelemenin iki farklı biçimi vardır:
- Doğrusal Özyineleme
- Ağaç Yinelemesi
- Doğrusal Özyineleme
Doğrusal Özyineleme
- Her yürütüldüğünde kendisini yalnızca bir kez çağıran bir fonksiyona doğrusal özyineli olduğu söylenir. Doğrusal özyinelemenin güzel bir örneği faktöriyel fonksiyondur. 'Doğrusal özyineleme' adı, doğrusal olarak özyinelemeli bir fonksiyonun yürütülmesinin doğrusal bir süre alması gerçeğini ifade eder.
- Aşağıdaki sözde koda bir göz atın:
function doSomething(n) { // base case to stop recursion if nis 0: return // here is some instructions // recursive step doSomething(n-1); } - doSomething(n) fonksiyonuna bakarsak, n adında bir parametre kabul eder ve aynı prosedürü bir kez daha ancak daha düşük değerlerle çağırmadan önce bazı hesaplamalar yapar.
- doSomething() yöntemi n argüman değeriyle çağrıldığında, T(n)'nin hesaplamayı tamamlamak için gereken toplam süreyi temsil ettiğini varsayalım. Bunun için yineleme ilişkisini de formüle edebiliriz, T(n) = T(n-1) + K. K burada bir sabit görevi görüyor. Fonksiyonun bir değişkene hafıza tahsis etmesi veya tahsisini kaldırması veya bir matematiksel işlem gerçekleştirmesi zaman aldığından K sabiti dahil edilmiştir. Çok küçük ve önemsiz olduğu için zamanı tanımlamak için K kullanıyoruz.
- Bu özyinelemeli programın zaman karmaşıklığı basit bir şekilde hesaplanabilir, çünkü en kötü senaryoda doSomething() yöntemi n kez çağrılır. Resmi olarak konuşursak, fonksiyonun zamansal karmaşıklığı O(N)'dir.
Ağaç Yinelemesi
- Özyinelemeli durumunuzda birden fazla özyinelemeli çağrı yaptığınızda buna ağaç özyinelemesi denir. Ağaç özyinelemesinin etkili bir örneği fibonacci dizisidir. Ağaç özyinelemeli işlevleri üstel zamanda çalışır; zamansal karmaşıklıkları bakımından doğrusal değildirler.
- Aşağıdaki sözde koda bir göz atın,
function doSomething(n) { // base case to stop recursion if n is less than 2: return n; // here is some instructions // recursive step return doSomething(n-1) + doSomething(n-2); } - Bu kodun öncekinden tek farkı, bu kodun aynı fonksiyona daha düşük n değeriyle bir çağrı daha yapmasıdır.
- Bu fonksiyonun yineleme ilişkisi olarak T(n) = T(n-1) + T(n-2) + k'yi koyalım. K bir kez daha sabit olarak görev yapıyor.
- Aynı işleve daha küçük değerlerle birden fazla çağrı yapıldığında, bu tür özyineleme ağaç özyinelemesi olarak bilinir. Şimdi işin ilginç yanı şu: Bu işlev ne kadar zaman alıyor?
- Aynı işlev için aşağıdaki özyineleme ağacını temel alarak bir tahminde bulunun.
- Özyinelemeli bir fonksiyona, özellikle de bir ağaç özyinelemesi söz konusu olduğunda, doğrudan bakarak zaman karmaşıklığını tahmin etmenin zor olduğunu düşünebilirsiniz. Özyineleme Ağacı Yöntemi, bu tür fonksiyonların zamansal karmaşıklığını hesaplamak için kullanılan çeşitli tekniklerden biridir. Daha ayrıntılı olarak inceleyelim.
Özyineleme Ağacı Yöntemi Nedir?
- T(N) = T(N/2) + N gibi yineleme ilişkileri veya daha önce özyineleme bölümü türlerinde ele aldığımız ikisi özyineleme ağacı yaklaşımı kullanılarak çözülür. Bu yinelenen ilişkiler, sorunları çözmek için sıklıkla böl ve yönet stratejisini kullanır.
- Daha büyük bir problem daha küçük alt problemlere bölündüğünde ortaya çıkan daha küçük alt problemlerin cevaplarını bütünleştirmek zaman alır.
- Örneğin, Birleştirme sıralaması için yineleme ilişkisi T(N) = 2 * T(N/2) + O(N) şeklindedir. T(N/2) birleşik boyutuna sahip iki alt problemin cevaplarını birleştirmek için gereken süre O(N)'dir ve bu uygulama düzeyinde de geçerlidir.
- Örneğin, ikili arama için yineleme ilişkisi T(N) = T(N/2) + 1 olduğundan, ikili aramanın her yinelemesinin yarıya kesilmiş bir arama alanıyla sonuçlandığını biliyoruz. Sonuç belirlendikten sonra fonksiyondan çıkıyoruz. Tekrarlama ilişkisine +1 eklenmiştir çünkü bu sabit zamanlı bir işlemdir.
- T(n) = 2T(n/2) + Kn yineleme ilişkisi dikkate alınması gereken bir ilişkidir. Kn, n/2 boyutlu alt problemlerin cevaplarını birleştirmek için gereken süreyi belirtir.
- Yukarıda bahsedilen yineleme ilişkisinin özyineleme ağacını çizelim.
Yukarıdaki özyineleme ağacını inceleyerek birkaç sonuç çıkarabiliriz:
1. Bir düğümün değerinin belirlenmesinde önemli olan her seviyedeki sorunun büyüklüğüdür. Sorun boyutu 0 düzeyinde n, 1 düzeyinde n/2, 2 düzeyinde n/2 vb. şeklindedir.
2. Genel olarak ağacın yüksekliğini log(n)'a eşit olarak tanımlarız, burada n konunun boyutudur ve bu özyineleme ağacının yüksekliği ağaçtaki düzey sayısına eşittir. Bu doğrudur, çünkü az önce belirlediğimiz gibi, böl ve yönet stratejisi sorunları çözmek için yineleme ilişkileri tarafından kullanılır ve n sorun boyutundan 1 sorun boyutuna ulaşmak basitçe log (n) adımların atılmasını gerektirir.
- Örneğin N = 16 değerini düşünün. Her adımda N'yi 2'ye bölmemize izin verilirse, N = 1 elde etmek için kaç adım gerekir? Her adımda ikiye böldüğümüzü düşünürsek doğru cevap log(16) tabanının 2 değeri olan 4'tür.
log(16) taban 2
log(2^4) taban 2
4 * log(2) tabanı 2, çünkü log(a) tabanı a = 1
yani, 4 * log(2) tabanı 2 = 4
3. Her düzeyde yinelemedeki ikinci terim kök olarak kabul edilir.
Bu stratejinin adında 'ağaç' kelimesi geçse de bunu anlamak için ağaç konusunda uzman olmanıza gerek yok.
Yineleme İlişkilerini Çözmek İçin Özyineleme Ağacı Nasıl Kullanılır?
Özyinelemeli ağaç tekniğinde alt problemin maliyeti, alt problemin çözümü için gereken süre miktarıdır. Bu nedenle, özyineleme ağacıyla bağlantılı 'maliyet' ifadesini fark ederseniz, bu sadece belirli bir alt problemi çözmek için gereken süreyi ifade eder.
Birkaç örnekle tüm bu adımları anlayalım.
Örnek
Tekrarlama ilişkisini düşünün,
T(n) = 2T(n/2) + K
Çözüm
Verilen yineleme ilişkisi aşağıdaki özellikleri gösterir:
n boyutunda bir problem, her biri n/2 boyutunda iki alt probleme bölünür. Çözümleri bu alt problemlere birleştirmenin maliyeti K'dır.
Her bir problem boyutu n/2, her biri n/4 boyutunda iki alt probleme bölünür ve bu şekilde devam eder.
Son aşamada alt problemin boyutu 1'e düşürülecek. Yani nihayet temel duruma ulaştık.
Bu yineleme ilişkisini çözmek için adımları takip edelim,
Adım 1: Özyineleme Ağacını Çizin
Adım 2: Ağacın Yüksekliğini Hesaplayın
Bildiğimiz için bir sayıyı sürekli olarak 2'ye böldüğümüzde, bu sayının 1'e düştüğü bir an gelir. N problem boyutunda olduğu gibi, varsayalım ki K 2'ye bölündükten sonra N 1'e eşit olur, bu da şu anlama gelir: ( n / 2^k) = 1
Burada n/2^k son seviyedeki problem boyutudur ve her zaman 1'e eşittir.
Artık log() fonksiyonunu her iki tarafa alarak k değerini yukarıdaki ifadeden kolayca hesaplayabiliriz. Aşağıda daha net bir çıkarım var,
n = 2^k
- log(n) = log(2^k)
- log(n) = k * log(2)
- k = log(n) / log(2)
- k = log(n) tabanı 2
Yani ağacın yüksekliği log (n) tabanı 2'dir.
3. Adım: Her seviyedeki maliyeti hesaplayın
- Düzey-0 = K'da Maliyet, iki alt problem birleştirilmiştir.
- Düzey-1'de Maliyet = K + K = 2*K, iki alt problem iki kez birleştirilir.
- Düzey-2'de Maliyet = K + K + K + K = 4*K, iki alt problem dört kez birleştirilir. ve benzeri....
Adım 4: Her seviyedeki düğüm sayısını hesaplayın
Öncelikle son seviyedeki düğüm sayısını belirleyelim. Özyineleme ağacından bunu çıkarabiliriz
- Seviye-0'da 1 (2^0) düğüm bulunur
- Seviye-1'de 2 (2^1) düğüm bulunur
- Seviye-2'de 4 (2^2) düğüm bulunur
- Seviye-3'te 8 (2^3) düğüm bulunur
Dolayısıyla log(n) düzeyinde 2^(log(n)) düğüm, yani n düğüm bulunmalıdır.
Adım 5: Tüm seviyelerin maliyetini toplayın
- Toplam maliyet şu şekilde yazılabilir:
- Toplam Maliyet = Son seviye hariç tüm seviyelerin maliyeti + Son seviyenin maliyeti
- Toplam Maliyet = Seviye-0 için Maliyet + Seviye-1 için Maliyet + Seviye-2 için Maliyet +.... + Seviye-log(n) için Maliyet + Son seviye için Maliyet
Son seviyenin maliyeti, temel durum olduğundan ve son seviyede birleştirme yapılmadığından ayrı olarak hesaplanır, dolayısıyla bu seviyede tek bir problemi çözmenin maliyeti sabit bir değerdir. O(1) olarak alalım.
Değerleri formüllere koyalım,
- T(n) = K + 2*K + 4*K + .... + log(n)` çarpı + `O(1) * n
- T(n) = K(1 + 2 + 4 + .... + log(n) çarpı)` + `O(n)
- T(n) = K(2^0 + 2^1 + 2^2 + ....+ log(n) çarpı + O(n)
Yukarıdaki ifadeye yakından bakarsanız Geometrik bir ilerleme oluşturur (a, ar, ar^2, ar^3 ...... sonsuz zaman). GP'nin toplamı S(N) = a / (r - 1) ile verilir. Burada ilk terim ve r ortak orandır.