Algoritma teknikleri

İki derstir borç biriktirdik: "özyinelemenin doğrusu", "böl-yönet genelleşecek", "memoization gelecek" dedik. Bu ders borçları kapatıyor — algoritma tasarımının dört genel stratejisi: özyineleme, böl ve yönet, açgözlü yaklaşım ve dinamik programlama. Bunlar tek tek algoritmalar değil, algoritma üretme kalıplarıdır; sınavda eşleştirme sorusu, mülakatta problem çözme dili, sahada ise ağaç gezme ve önbellekleme olarak her gün karşındadır.

01Ne öğreneceksin

02Özyineleme: kendine güvenen fonksiyon

Özyineleme (recursion), bir metodun problemi küçültüp kendini çağırmasıdır. Geçerli her özyinelemede iki parça bulunur — ikisinden biri eksikse program ya yanlıştır ya çöker:

• Taban durumu (base case): özyinelemesiz cevaplanan en küçük hâl — durma noktası.
• Özyineleme adımı: problemi kesinlikle küçülten kendine çağrı.

long Faktoriyel(int n)
{
    if (n <= 1) { return 1; }          // taban durumu
    return n * Faktoriyel(n - 1);      // küçülen problem: n → n-1
}
// Faktoriyel(4) → 4 * Faktoriyel(3) → 4 * 3 * Faktoriyel(2) → 4 * 3 * 2 * 1 = 24

Mekanikte sihir yok — 4. dersin (tb-bellek) çağrı yığını iş başında: her çağrı bir çerçeve push'lar, taban duruma inince çerçeveler sırayla pop'lanıp çarpımlar toplanır. Buradan iki bilinen sonuç çıkar: taban durumu yoksa (ya da ona hiç ulaşılmıyorsa) yığın taşar — StackOverflowException, 4. dersin alıştırmasında bilerek üretmiştin; ve n derinlikli özyineleme O(n) yığın belleği tüketir (10. dersin "gizli uzay" maddesi).

Ne zaman özyineleme, ne zaman döngü? İlke: problemin kendisi özyinelemeliyse özyineleme yaz. Ağaç ve hiyerarşi gezme (9. dersteki klasör ağacın: "her çocuk kendi alt ağacının köküdür"), iç içe yapılar (JSON/XML — Hat 06'da), böl-yönet algoritmaları — bunlarda özyinelemeli kod, döngülü eşdeğerinden kat kat okunaklıdır. Faktöriyel gibi düz sayaç işlerinde ise döngü hem hızlı hem yığın dostudur; özyineleme burada yalnızca öğretim aracıdır. Derinlik binlere çıkabiliyorsa (çok derin dizin ağacı, uzun zincir) özyinelemeyi açık stack'li döngüye çevirmek (8. dersin yapısı — DFS'in iki yazımı) üretim refleksidir. "Kuyruk özyineleme" (tail recursion) terimini de tanı: son işi kendine çağrı olan biçim; bazı diller bunu döngüye çevirir, C# derleyicisi garanti etmez — güvenme, bil yeter.

03Böl ve yönet: üç tanıdığın ortak iskeleti

Böl ve yönet (divide & conquer), özyinelemenin en verimli kullanım şablonudur: problemi bağımsız alt problemlere böl, her birini (özyinelemeyle) çöz, sonuçları birleştir. Farkında olmadan üçünü gördün bile:

Maliyet sezgisi 10. dersten tanıdık: bölme, log n seviye üretir; toplam maliyet "seviye sayısı × seviye başına iş"tir. Her seviyede n iş varsa n log n (merge), her seviyede tek yarıyla devam ediyorsan log n (ikili arama). Bu kaba hesap, sınav ve mülakat düzeyinde yeterlidir — resmî genel formül (Master teoremi) lisans dersinin işidir, adını bilmen yeter. Stratejinin modern yankısını da not et: alt problemler bağımsız olduğu için böl-yönet, paralelleştirmeye en yatkın kalıptır — iki yarıyı iki çekirdeğe vermek (5. dersin dünyası) doğal gelir; "böl, dağıt, birleştir" fikri veri işleme sistemlerinde (MapReduce soyu) sistem ölçeğine büyümüştür.

04Açgözlü yaklaşım: hızlı, zarif, bazen yanlış

Açgözlü (greedy) strateji: her adımda, o an en iyi görünen seçimi yap ve geri dönme. Klasik örnek para üstü: 87 TL'yi en az kupürle ver — hep en büyük sığanı seç: 50 + 20 + 10 + 5 + 1 + 1. Türk kupür sisteminde bu her zaman en az adettir; algoritma tek geçişte, sıralamadan sonra neredeyse bedavaya çalışır.

Şimdi kritik ders — açgözlünün karanlık yüzü: kupürler {1, 3, 4} olsun ve 6 birim ver. Açgözlü: 4 + 1 + 1 = 3 kupür. Oysa en iyi: 3 + 3 = 2 kupür. Açgözlü çalıştı, hata vermedi, makul görünen bir cevap verdi — ama cevap yanlıştı. Tehlikesi tam budur: açgözlü asla "bilmiyorum" demez. Yerel en iyi seçimlerin toplamının küresel en iyiyi verdiği kanıtlanabilen problemlerde (etkinlik seçimi, Dijkstra'nın en kısa yolu — 9. dersin öncelik kuyruğu müşterisi, Huffman kodlaması) açgözlü hem en hızlı hem doğru çözümdür; bu özellik yoksa yalnızca "fena olmayan" bir yaklaşıktır. Mühendis dili: "açgözlü öneriyorum, çünkü bu problemde yerel seçim küreseli bozamaz — işte gerekçesi" diyebiliyorsan kullan; diyemiyorsan sıradaki tekniğe geç.

05Dinamik programlama: aynı hesabı iki kez yapma

Bazı problemlerde alt problemler bağımsız değil örtüşüktür — aynı alt problem tekrar tekrar karşına çıkar. Ders kitabı örneği Fibonacci (F(n) = F(n−1) + F(n−2)):

long Fib(int n) => n <= 1 ? n : Fib(n - 1) + Fib(n - 2);

Fib(5) çağrı ağacı:            Fib(5)
                          Fib(4)      Fib(3)
                      Fib(3) Fib(2)  Fib(2) Fib(1)
                      ...
Fib(3) İKİ kez, Fib(2) ÜÇ kez hesaplanır → çağrı sayısı ikiye katlanarak büyür: O(2ⁿ)
Fib(50) ≈ milyarlarca çağrı — 10. dersin "üstel bölgesi", pratikte bitmez

Dinamik programlama (DP) tek fikirdir: çözdüğün alt problemi kaydet; ikinci kez sorulunca hesaplamadan oku. İki yazım biçimi vardır:

• Memoization (yukarıdan aşağı): özyinelemeli kodun başına önbellek koy — 10. dersin vaadi:

  Dictionary<int, long> ezber = new();
  long Fib(int n)
  {
      if (n <= 1) { return n; }
      if (ezber.TryGetValue(n, out long varOlan)) { return varOlan; }  // kayıtlıysa OKU
      long sonuc = Fib(n - 1) + Fib(n - 2);
      ezber[n] = sonuc;                                                // değilse KAYDET
      return sonuc;
  }
  // her n en fazla BİR kez hesaplanır: O(2ⁿ) → O(n). İki satırlık fark.

• Tablolama (aşağıdan yukarı): özyinelemeyi at, küçükten büyüğe bir dizi doldur: f[0]=0; f[1]=1; f[i]=f[i-1]+f[i-2]; — aynı O(n), yığın yok; hatta yalnız son iki değeri tutarak O(1) belleğe iner.

DP'nin uygulanma şartı ikilidir: örtüşen alt problemler (yoksa kayıt tutmanın faydası yok — merge sort'un yarıları örtüşmez, DP'lik değildir) ve optimal alt yapı (büyük problemin en iyisi, küçüklerin en iyisinden kurulur). Ünlü DP problemlerini isim düzeyinde tanı: en uzun ortak alt dizi (diff algoritmalarının temeli — git'in yaptığı iş, Hat 16), sırt çantası (knapsack), düzenleme mesafesi ("bunu mu demek istediniz?"). Genel fikrin sahadaki adı ise zaten günlük pratiğin: önbellekleme — 10. dersin zaman-uzay takası. Pahalı hesabı/sorguyu bir kez yap, sonucu sakla; memoization bunun fonksiyon ölçeği, Redis (Hat 19) sistem ölçeğidir.

06Teknik seçimi: problemden stratejiye

Dört tekniği tek karar tablosuna bağla — sınavın eşleştirme, mülakatın "nasıl yaklaşırsın" sorusu buradan çıkar:

Kaba kuvveti (brute force) küçümseme: doğru cevabı garanti eder ve n küçükse (10. ders: küçük n'de mertebe önemsiz) çoğu zaman doğru mühendislik kararıdır — akıllı algoritmayı, kaba kuvvetin yetmediği kanıtlanınca yazarsın. Mülakat stratejisi de budur: önce kaba kuvvetle çöz, karmaşıklığını söyle, sonra "şurada aynı hesabı tekrar yapıyorum → memoization" diye iyileştir — düşünce sürecini göstermek, ezber çözümden değerlidir.

07Sahada bu teknikler: teoriden günlük işe

Üretim kodunda "sırt çantası problemi" nadiren gelir; teknikler ise her gün gelir — kılık değiştirmiş hâlde:

• Özyineleme = hiyerarşi işleme: organizasyon ağacında yetki toplama, yorum-cevap zincirleri, menü ağaçları (bu sitenin yan menüsü dahil), dosya tarayıcıları. Derinlik sınırı koymak (sonsuz döngülü referanslara karşı) üretim disiplinidir.
• Böl-yönet = büyük işi parçalara bölüp paralel işleme; büyük dosyayı parça parça yükleme; "sorunu yarıya böl" hata ayıklama taktiği (git bisect — Hat 16 — ikili aramanın commit geçmişine uygulanmışıdır).
• Açgözlü = kaynak atama sezgileri: en yakın boş kuryeye işi ver, en dolu diske yazma. "Yeterince iyi + çok hızlı" istenen yerlerde bilinçli tercih; en iyilik iddia etme.
• Memoization = önbellekleme kültürünün tamamı: hesaplanan raporu sakla, API cevabını TTL ile tut (7. dersin DNS önbelleği aynı desendi), pahalı sorgunun sonucunu Redis'e koy. "Önbelleği ne zaman geçersiz kılacağım?" sorusuyla birlikte gelir — mesleğin ünlü zor problemi; Hat 19'da büyüyecek.

08Mini alıştırma — Üç Fibonacci, bir borç kapama

09Kendini sına

Geçerli bir özyinelemenin iki zorunlu parçası nedir? Taban durumu ulaşılmaz olursa ne olur ve neden?

Taban durumu (özyinelemesiz cevaplanan en küçük hâl) ve problemi kesin küçülten özyineleme adımı. Taban duruma ulaşılamazsa her çağrı, çağrı yığınına yeni bir çerçeve ekler; yığın sabit boyutlu olduğundan sınır aşılır ve süreç StackOverflowException ile çöker. Ayrıca n derinlikli sağlıklı özyineleme bile O(n) yığın belleği kullanır — çok derin yapılarda açık stack'li döngüye çevrilir.

Böl ve yönet şablonunu üç adımıyla anlat; merge sort ile quicksort'un asıl işi hangi adımda yaptığını karşılaştır.

Böl (problemi bağımsız alt problemlere ayır), çöz (her birini özyinelemeyle), birleştir (sonuçları kaynaştır). Merge sort bölmeyi mekanik yapar (ortadan ikiye) ve asıl işi birleştirmede görür — iki sıralı diziyi kaynaştırma. Quicksort tam tersidir: asıl iş bölmededir (pivotla bölümleme); bölümleme bitince pivot yerindedir, ayrı birleştirme adımı yoktur. İkisinde de log n seviye × seviye başına n iş = O(n log n) sezgisi geçerlidir.

Açgözlü yaklaşımın riskini {1, 3, 4} kupür örneğiyle anlat. Açgözlünün doğru olduğu iki ünlü algoritma söyle.

Açgözlü her adımda yerel en iyiyi seçer ve geri dönmez; 6 birimi {1,3,4} kupürleriyle verirken 4+1+1 = 3 kupür bulur, oysa en iyi 3+3 = 2 kupürdür — hata vermez, sessizce en iyi olmayan cevabı verir. Yerel seçimin küreseli bozmadığı kanıtlanabilen problemlerde ise hem en hızlı hem doğrudur: Dijkstra'nın en kısa yol algoritması ve Huffman kodlaması (ayrıca standart kupür sisteminde para üstü).

Dinamik programlamanın iki şartı nedir? Memoization ile tablolamayı karşılaştır ve Fibonacci'de kazancı söyle.

Şartlar: örtüşen alt problemler (aynı alt problem tekrar sorulur) ve optimal alt yapı (büyüğün en iyisi küçüklerin en iyisinden kurulur). Memoization yukarıdan aşağı çalışır: özyinelemeli koda önbellek eklenir, istenen alt problemler hesaplanır; kod doğal kalır ama yığın kullanır. Tablolama aşağıdan yukarı diziyi doldurur: yığın yok, çoğu kez daha az bellek (Fibonacci'de son iki değerle O(1)). Kazanç: saf özyinelemeli Fibonacci O(2ⁿ) iken her alt problem bir kez hesaplanınca O(n) olur.

10Sınav köşesi