Bölüm 3: Özyineleme, İkili Arama ve Geri İzleme

3.1Özyinelemeli algoritmalar

Programlamaya yeni başlayan biri bir işi tekrarlamak için önce döngüyü öğrenir. Döngü, aynı gövdeyi bir koşul sağlandığı sürece yeniden çalıştırır. Özyineleme tekrarı başka bir yoldan elde eder: fonksiyon, işin küçük bir parçasını yapmak için kendini çağırır. İlk karşılaşmada tuhaf görünen bu fikir, matematikte çok eskidir. Tümevarımla yapılan tanımlar ve ispatlar aynı yapıdadır.

3.1.1Özyineleme nedir?

Bir problemin bütününde kullanılan çözüm mantığı, problemin parçalarında da geçerliyse özyinelemeli bir algoritma yazılabilir. Faktöriyel bunun en yalın örneğidir. n! = n · (n − 1)! eşitliği, n'nin faktöriyelini bir küçük sayının faktöriyeline bağlar. (n − 1)! de aynı kuralla (n − 2)!'ye bağlanır. Zincir 1! = 1'de durur.

Dolaylı özyinelemenin tanıdık bir örneği, ifade çözümleyicilerdir. Bir aritmetik ifadeyi çözümleyen ifade() fonksiyonu terimleri okumak için terim() fonksiyonunu çağırır. Parantez içinde yeni bir ifade başlayınca terim() yeniden ifade()'yi çağırır. İki fonksiyon kendilerini hiç doğrudan çağırmaz, ama zincir kapalı bir döngü oluşturur. C'de dolaylı özyineleme yazarken ikinci fonksiyonun bildirimi (prototipi) birinci fonksiyondan önce verilmelidir; derleyici aksi hâlde henüz görmediği bir adı tanımaz.

3.1.2Taban durum ve özyinelemeli adım

Kendini çağıran bir fonksiyonun bir yerde durması gerekir. Faktöriyel zinciri 1! = 1'de durur, çünkü bu değer başka bir faktöriyele başvurmadan bilinir. Her özyinelemeli algoritma bu iki parçadan oluşur.

Tanımdaki son cümle, özyinelemenin doğruluğu için şarttır. “Daha küçük” sözü bir ölçüyle ifade edilir: faktöriyelde n, ikili aramada aralıktaki öğe sayısı, Hanoi kulelerinde disk sayısı. Ölçü her çağrıda azalmalı ve taban durumda en küçük değerine ulaşmalıdır. Ölçü azalmıyorsa çağrılar sonsuza dek sürer. Gerçek bir makinede “sonsuza dek” uzun sürmez, çünkü her çağrı bellekte yer tutar ve ayrılan bellek kısa sürede biter.

Özyinelemeli bir fonksiyon yazarken iki soru sorulur. Birincisi, en küçük örnek hangisidir ve cevabı nedir? İkincisi, bir boy küçük örneğin cevabı bilinseydi asıl cevap nasıl kurulurdu? İkinci soru, özyinelemeli düşünmenin özüdür. Küçük örneğin nasıl çözüldüğü düşünülmez; çözüldüğü kabul edilir. Bu kabul, tümevarım ispatındaki “n − 1 için doğru olsun” varsayımının aynısıdır.

Yeni başlayanların sık sorduğu bir soru vardır: özyinelemeli çözüm çok bellek harcamaz mı? Bu soruya cevap vermek için önce özyinelemeli kodu yazabilmek, sonra o kodun karmaşıklığını hesaplayabilmek gerekir. Özyinelemeli kod yazmak öğrenilmeden yapılan bir “çok bellek harcar” yargısı temelsiz kalır. Bu notun sırası da bu yüzden böyledir: önce kod, sonra ölçüm. Bellek maliyeti çağrı yığını incelenince somut bir sayıya dönüşür.

3.1.3İlk örnek: faktöriyel

Faktöriyelin özyinelemeli tanımı, C'ye neredeyse birebir aktarılır:

long fakt(int n) {
  if (n <= 1)
    return 1;              /* taban durum */
  return n * fakt(n - 1);
}

int main(void) {
  printf("%ld\n", fakt(3));
  return 0;
}

Fonksiyon long türünde bir değer döndürür, çünkü faktöriyel çok hızlı büyür. İlk satırdaki if (n <= 1) taban durumu yakalar ve 1 döndürür. Son satır özyinelemeli adımdır: n * fakt(n - 1) ifadesi önce fakt(n - 1)'i hesaplatır, dönen değeri n ile çarpar. main fonksiyonu fakt(3)'ü çağırıp sonucu %ld biçimiyle yazar; çıktı 6'dır.

Kodun okunuşu tanımın okunuşuyla aynıdır: “n en çok 1 ise faktöriyel 1'dir, değilse n çarpı bir eksiğinin faktöriyelidir.” Döngülü bir sürümde bu cümle yoktur; onun yerine bir sayaç ve bir birikim değişkeni bulunur. Özyinelemenin en büyük kazancı bu okunabilirliktir.

Kodun doğruluğu tümevarımla gösterilir. n ≤ 1 için fonksiyon 1 döndürür ve 0! = 1! = 1'dir. n > 1 için fakt(n - 1)'in (n − 1)! döndürdüğü kabul edilirse, fonksiyon n · (n − 1)! = n! döndürür. Taban durum ve adım birlikte her n ≥ 0 için doğruluğu verir.

long türünün boyu sisteme göre değişir ve bu fark faktöriyelde hemen görünür. 64 bit Linux ve macOS'ta long 64 bittir; en büyük değeri 2⁶³ − 1 ≈ 9,2·10¹⁸'dir ve 20! ≈ 2,4·10¹⁸ bu sınıra sığar. Windows'ta ise long 32 bittir; en büyük değeri 2³¹ − 1 = 2.147.483.647'dir. 12! = 479.001.600 sığar, 13! = 6.227.020.800 sığmaz. İşaretli tamsayı taşması C'de tanımsız davranıştır: program yanlış bir sayı yazabilir, beklenmedik biçimde davranabilir. Bu notun kodları -fsanitize=undefined seçeneğiyle derlenip Windows'ta denendiğinde fakt(13) çağrısı tam da bu hatayı bildirdi. Büyük faktöriyeller için long long (en az 64 bit) ya da büyük sayı kitaplıkları kullanılır.

3.2Çağrı yığını

Özyineleme kâğıt üzerinde bir tanımdır, ama bilgisayarda gerçek bir mekanizmayla çalışır. Bu mekanizmayı anlamak hem özyinelemeli kodu izleyebilmek hem de bellek maliyetini hesaplayabilmek için gerekir. Mekanizmanın adı çağrı yığınıdır ve her fonksiyon çağrısında, özyinelemeli olsun olmasın, kullanılır.

3.2.1Yığın çerçevesi

Bir fonksiyon çağrıldığında denetim hemen fonksiyonun gövdesine geçmez. Önce bir hazırlık yapılır. Fonksiyon bittiğinde programın nereye döneceği, yani dönüş adresi saklanır. Parametrelerin değerleri fonksiyonun erişebileceği bir yere kopyalanır. Fonksiyonun yerel değişkenleri için yer ayrılır. Bütün bu bilgiler bellekte art arda duran tek bir kayıtta toplanır.

Çağrı yığını, adından da anlaşılacağı gibi bir yığın yapısıdır: son giren ilk çıkar. Bir fonksiyon çağrılınca çerçevesi yığının üstüne eklenir. Fonksiyon return ile bitince çerçevesi üstten kaldırılır ve denetim, çerçevedeki dönüş adresine geçer. Program başladığında yığında yalnız main'in çerçevesi vardır. Bu ilk çerçevede de dönüş adresi ve önceki çerçeveye işaretçi bulunur; main bittiğinde denetim işletim sistemine döner.

Şekil 3.1 bu düzeni gösterir. Yığın şekilde aşağıdan yukarı büyür; en alttaki çerçeve main'indir. binsearch çağrılınca onun çerçevesi üste eklenir. Bu çerçevede dört parametre (list, aranan, left, right), bir yerel değişken (middle) ve main'e dönüş adresi vardır. list parametresinin dizinin kendisi olmadığına dikkat etmek gerekir. C'de dizi parametresi, dizinin ilk öğesinin adresini taşıyan bir işaretçiye dönüşür. Çerçevede bu adres durur; dizinin on öğesi main'in çerçevesinde kalır ve kopyalanmaz.

Gerçek bir derleyicinin çerçeve düzeni işlemciye ve derleyiciye göre değişir. Bazı parametreler bellek yerine işlemci yazmaçlarında taşınabilir. Yine de mantık her yerde aynıdır: her etkin çağrının kendi çerçevesi vardır ve bu çerçeveler bir yığın düzeninde tutulur. Özyinelemeyi anlamak için bu mantık yeterlidir.

Özyinelemenin özel bir durumu yoktur. Fonksiyon kendini çağırdığında da yeni bir çerçeve açılır. Aynı fonksiyonun birden çok çağrısı aynı anda yığında bulunabilir ve her birinin kendi parametre ve yerel değişken kopyaları olur. Bir çağrıdaki n, öteki çağrıdaki n'den tamamen ayrıdır.

3.2.2Kod izleme: fakt(3)

fakt(3) çağrısının yığını nasıl değiştirdiği adım adım izlenebilir. Tablo 3.1, her adımda çalışan satırı, o anki n değerini ve yığının içeriğini verir. Yığın soldan sağa yazılmıştır; en sağdaki çerçeve yığının üstüdür.

İzlemenin ilk yarısı bir iniştir. Adım 3'te fakt(3), 3 * fakt(2) ifadesini hesaplamaya başlar ama çarpmayı yapamaz, çünkü ikinci çarpan henüz bilinmez. Bu yüzden fakt(2)'yi çağırır ve kendi çerçevesi yığında beklemeye geçer. Aynı şey adım 5'te fakt(2) için olur. Adım 6'da fakt(1) taban duruma ulaşır ve hiçbir çağrı yapmadan 1 döndürür. Bu anda yığında dört çerçeve vardır: main ve üç fakt çağrısı.

İkinci yarı bir çıkıştır. fakt(1)'in çerçevesi kaldırılır ve denetim fakt(2)'nin bıraktığı yere, yarım kalan çarpmaya döner. fakt(2)'nin çerçevesinde n hâlâ 2'dir. Şekil 3.2'deki her kutunun kendi n kopyası olması bu yüzden önemlidir. fakt(1) çalışırken n 1 olmuştu, ama bu değişiklik yalnız fakt(1)'in çerçevesindeydi. Çarpma 2 · 1 = 2 sonucunu verir ve fakt(2) biter. Aynı biçimde fakt(3) 3 · 2 = 6 hesaplar. Son olarak main 6 yazar ve yığında yalnız main kalır.

Bu izleme özyinelemeli fonksiyonların genel davranışını gösterir. Çağrılar önce taban duruma kadar iner; asıl hesaplama çoğunlukla dönüş yolunda yapılır. Faktöriyelde çarpmaların hepsi çıkış sırasında, en içteki çağrıdan dışa doğru yapılır: önce 2 · 1, sonra 3 · 2.

3.2.3Özyinelemenin bellek maliyeti

Her özyinelemeli çağrı yeni bir çerçeve demektir. Çerçeveler ancak çağrı bitince kalkar. Dolayısıyla bir anda yığında duran çerçeve sayısı, özyineleme zincirinin o anki uzunluğuna eşittir. Bu uzunluğun en büyük değerine özyineleme derinliği denir.

fakt(n) için derinlik n'dir: fakt(n), fakt(n − 1), …, fakt(1) zinciri n çerçeve açar. Ek bellek O(n)'dir. Zaman maliyeti de Θ(n)'dir, çünkü n çağrının her biri sabit sayıda işlem (bir karşılaştırma, bir çarpma, bir dönüş) yapar.

Çağrı yığınının boyu sınırlıdır. İşletim sistemi her iş parçacığına sabit bir yığın alanı ayırır; bu alan Windows'ta varsayılan olarak 1 MB, Linux'ta çoğunlukla 8 MB'tır. Çerçeve başına birkaç on bayt harcayan bir fonksiyon bile yüz binlerce derinliğe inerse bu alanı doldurur ve program yığın taşmasıyla çöker. Bu yüzden derinliği n olan özyineleme büyük n için tehlikelidir; derinliği log n olan özyineleme ise pratikte hiç sorun çıkarmaz. Bir milyar öğeli dizide ikili arama bile 30 çerçeveden derine inmez.

3.3Özyineleme mi, döngü mü?

Aynı problemi hem özyinelemeyle hem döngüyle çözmek çoğu zaman mümkündür. Hangisinin seçileceği, okunabilirlik, bellek ve hız arasında bir dengeye bağlıdır.

3.3.1İki faktöriyel

Faktöriyelin iki sürümü yan yana şöyledir:

/* ozyinelemeli */
long fakt(int n) {
  return n <= 1 ? 1 : n * fakt(n - 1);
}

/* dongulu */
long fakt_d(int n) {
  long f = 1;
  while (n > 1)
    f *= n--;
  return f;
}

Özyinelemeli sürüm tek satıra inmiştir. ?: koşul işleci, if–else yapısının ifade biçimidir: koşul doğruysa iki noktadan önceki, yanlışsa sonraki değeri verir. Döngülü sürüm f adında bir birikim değişkeni kullanır. f *= n--; satırı iki iş yapar: önce f'yi n ile çarpar, sonra n'yi bir azaltır. Sonek -- işleci, ifadede eski değeri kullanıp değişkeni sonra azaltır. fakt_d(4) çağrısında f sırasıyla 4, 12, 24 olur ve n = 1 olunca döngü durur.

Döngülü sürümde n parametresinin değiştirilmesi çağıranı etkilemez. C'de parametreler değerle aktarılır: fonksiyon, çağıranın değişkeninin bir kopyasıyla çalışır. fakt_d(x) çağrısından sonra x değişmeden kalır.

3.3.2Karşılaştırma

İki yaklaşımın farkları Tablo 3.2'de toplanmıştır.

Tablonun “çağrı maliyeti” satırı hızla ilgilidir. Her çağrıda çerçeve kurulur, parametreler kopyalanır, dönüşte çerçeve kaldırılır. Bu işler birkaç makine komutudur, ama döngünün bir turundan pahalıdır. Faktöriyel gibi basit bir işte özyinelemeli sürüm döngülü sürümden biraz yavaş çalışır. Asimptotik mertebe ise aynıdır; fark yalnız sabit çarpandadır.

“Doğal olduğu yer” satırı daha önemlidir. Faktöriyelde döngü de özyineleme kadar açıktır. Ağaç gezinmesinde, Hanoi kulelerinde ya da geri izlemede durum böyle değildir. Bu problemlerde bir çağrı birden çok alt çağrı yapar ve her alt çağrının nerede kaldığını hatırlamak gerekir. Özyineleme bu kaydı çağrı yığınına bırakır; döngülü sürüm aynı kaydı programcının elle tutmasını ister.

3.3.3Özyinelemeyi döngüye çevirmek

Her özyinelemeli algoritma döngüye çevrilebilir ve her döngü özyinelemeye çevrilebilir. Çeviri yöntemi çağrı yığınını taklit etmektir: programcı bir dizi ya da yığın yapısı tanımlar, özyinelemenin saklayacağı bilgileri oraya koyar ve bir döngüyle işler. Aşağıdaki fonksiyon faktöriyeli bu yolla hesaplar:

long fakt_y(int n) {
  int yigin[64], ust = 0;         /* cagri yiginini taklit eden dizi */
  long f = 1;
  while (n > 1)                   /* inis: carpanlari yigina it */
    yigin[ust++] = n--;
  while (ust > 0)                 /* donus: bekleyen carpmalari yap */
    f *= yigin[--ust];
  return f;
}

İlk döngü, özyinelemenin iniş aşamasına karşılık gelir. Her turda bekleyen bir çarpanı (n, n − 1, …, 2) diziye iter. İkinci döngü çıkış aşamasıdır: çarpanları ters sırayla alıp birikime ekler. yigin dizisinin boyu 64 seçilmiştir; faktöriyel n = 21'de zaten 64 bitlik sayıya sığmadığından bu boy yeterlidir. Özyinelemeli fakt'ın çağrı yığınında tuttuğu bilgi tam olarak bu dizidir. Faktöriyelde bu çeviri gereksiz bir zahmettir, çünkü çarpmalar sıradan bağımsızdır ve tek bir değişken yeter. Ağaç gezinmesi gibi problemlerde ise açık yığın, özyinelemesiz çözümün tek yoludur.

Seçim bir dengedir. Kod okunabilirliği öndeyse ve derinlik küçükse (örneğin O(log n)) özyineleme iyi bir seçimdir. Derinlik büyük olabiliyorsa ya da her çağrının maliyeti önemliyse döngü tercih edilir.

3.4Kuyruk özyinelemesi

Bazı özyinelemeli fonksiyonlar özel bir biçimdedir: özyinelemeli çağrı, fonksiyonun yaptığı son iştir. Bu biçimdeki fonksiyonlar döngüye mekanik olarak çevrilebilir ve derleyici bu çeviriyi kendisi yapabilir.

3.4.1Tanım ve birikimli parametre

fakt kuyruk özyinelemeli değildir. return n * fakt(n - 1); satırında özyinelemeli çağrı döndükten sonra bir çarpma yapılır. Bu çarpma için n'nin değeri saklanmalıdır; dolayısıyla çerçeve, alt çağrı bitene kadar yığında kalmak zorundadır. Faktöriyelin kuyruk özyinelemeli sürümü, bekleyen çarpmayı ortadan kaldırmak için ek bir parametre kullanır:

long fakt_k(int n, long acc) {
  if (n <= 1) return acc;
  return fakt_k(n - 1, n * acc);  /* son is: cagri */
}
/* ilk cagri: fakt_k(n, 1) */

acc (accumulator) birikimli parametredir ve o ana kadar hesaplanan kısmi çarpımı taşır. Çarpma, özyinelemeli çağrıdan önce, argüman hesaplanırken yapılır: n * acc. Çağrı döndüğünde yapılacak iş kalmaz; dönen değer olduğu gibi yukarı iletilir. Taban durumda birikim tam sonuçtur ve doğrudan döndürülür. İlk çağrıda birikim 1'dir, çünkü 1 çarpmanın etkisiz öğesidir.

3.4.2Derleyici ve kuyruk çağrısı

Kuyruk çağrısından sonra çerçevede bekleyen iş olmadığı için çerçeveyi saklamanın bir anlamı yoktur. Derleyici yeni çerçeve açmak yerine mevcut çerçevedeki parametreleri yeni değerlerle günceller ve fonksiyonun başına atlar. Bu dönüşüme kuyruk çağrısı eniyilemesi (tail call optimization) denir. Sonuç, döngülü sürümle aynı makine kodudur ve yığın maliyeti O(1)'e iner.

C standardı bu eniyilemeyi garanti etmez. GCC ve Clang, -O2 düzeyinde kuyruk çağrılarını çoğu zaman atlamaya çevirir; eniyileme kapalı derlemede (-O0) ise her çağrı yeni bir çerçeve açar. Dolayısıyla derinliği çok büyük olabilecek bir kuyruk özyinelemesine C'de güvenmek doğru değildir. Böyle bir fonksiyonu elle döngüye çevirmek kolaydır: parametreler döngü değişkeni olur, özyinelemeli çağrı yerine parametrelere yeni değerler atanır, taban durum döngünün çıkış koşulu olur. fakt_k bu yolla fakt_d'ye dönüşür.

3.5İkili arama

Arama, bir veri kümesinde istenen değeri bulma işidir. Sırasız bir dizide yapılabilecek en iyi şey öğelere tek tek bakmaktır; buna doğrusal arama denir ve en kötü durumda n karşılaştırma ister. Dizi sıralıysa çok daha iyisi yapılabilir. Sıralı bir dizide tek bir karşılaştırma, aranan değerin hangi yarıda olduğunu söyler. İkili arama bu bilgiyi her adımda kullanır.

3.5.1Problem ve COMPARE makrosu

Bu bölümdeki bütün ikili arama örnekleri aynı test dizisini kullanır:

Yordam aranan değerin kendisini değil, indisini döndürür. Bunun iki nedeni vardır. Birincisi, aranan değer zaten bilinir; asıl merak edilen onun dizideki yeridir. İndis bilinince o konumdaki kaydın başka alanlarına da ulaşılabilir. İkincisi, “bulunamadı” bilgisinin değerlerle karışmaması gerekir. Yordam list[i] döndürseydi, hata işareti olarak seçilen −1 dizideki gerçek bir −1 öğesiyle karışabilirdi. C'de dizi indisleri 0'dan başladığı için −1 hiçbir geçerli indise denk gelmez ve “yok” anlamını güvenle taşır.

Karşılaştırma sonucu üç durumdan biridir: küçük, eşit ya da büyük. Kodu sade tutmak için bu üç durumu bir sayıya çeviren bir makro tanımlanır:

#define COMPARE(x, y) ((x) < (y) ? -1 : (y) < (x) ? 1 : 0)

COMPARE(x, y), x < y ise −1, x > y ise 1, eşitse 0 verir. Makro iç içe iki koşul işleciyle yazılmıştır. İlk koşul (x) < (y) doğruysa sonuç −1'dir. Değilse ikinci koşul (y) < (x) sınanır; doğruysa 1, değilse 0 çıkar. Makro parametrelerinin her geçişte parantez içine alınması önişlemcinin metin değiştirme kuralından kaynaklanır. COMPARE(a + 1, b) gibi bir çağrıda parantezler, ifadenin işleç önceliği yüzünden yanlış gruplanmasını önler.

Makronun dönüşü, switch deyiminde üç ayrı dala bağlanabilir. Sayısal karşılaştırma için x - y farkı da kullanılabilirdi, ama büyük sayılarda fark taşabilir. Makro, çıkarma yapmadığı için bu riski taşımaz.

3.5.2Döngüsel binsearch()

İkili aramanın döngüyle yazılmış sürümü şöyledir:

int binsearch(int list[], int aranan,
              int left, int right) {
  while (left <= right) {
    int middle = (left + right) / 2;
    switch (COMPARE(list[middle], aranan)) {
      case -1: left = middle + 1; break;
      case 0: return middle;
      case 1: right = middle - 1;
    }
  }
  return -1;
}

Fonksiyon dört parametre alır. list sıralı dizinin başlangıç adresidir, aranan bulunacak değerdir. left ve right, aramanın sürdüğü aralığın sol ve sağ uç indisleridir. Tüm dizide aramak için binsearch(list, x, 0, n - 1) çağrılır. Aralık uçları kapalıdır: left ve right indislerindeki öğeler de aralığa dahildir.

while (left <= right) koşulu aralığın boş olmadığını denetler. Kapalı uçlu bir aralıkta left = right durumu tek öğeli bir aralıktır ve hâlâ aranmalıdır; bu yüzden koşul < değil <= ile yazılır. Döngünün her turunda orta indis middle = (left + right) / 2 ile hesaplanır. C'de iki tamsayının bölümü, kesirli kısmı atılmış bir tamsayıdır; (0 + 9)/2 sonucu 4'tür.

switch deyimi COMPARE(list[middle], aranan) sonucuna göre üç dala ayrılır:

• case -1: ortadaki öğe aranandan küçüktür. Aranan, varsa, middle'ın sağındadır. Sol uç middle + 1 yapılır; middle artık aralıkta değildir, çünkü ona bakıldı. break, switch'ten çıkıp döngünün başına dönmeyi sağlar.
• case 0: eşitlik. Aranan bulunmuştur ve indisi döndürülür. return, hem switch'ten hem döngüden hem fonksiyondan çıkar.
• case 1: ortadaki öğe aranandan büyüktür. Aranan, varsa, middle'ın solundadır; sağ uç middle - 1 yapılır. Bu son dal olduğundan break yazılmasa da switch zaten biter.

Döngü, aralık boşalınca (left > right) sona erer ve fonksiyon −1 döndürür. Döngünün her turunda aralık en az bir öğe küçülür: ya bir dal return ile biter ya da left artar ya da right azalır. Bu yüzden döngü her zaman sonlanır.

3.5.3Kod izleme: 18 aranıyor

binsearch(list, 18, 0, 9) çağrısı izlenirse aralığın nasıl daraldığı görülür. Tablo 3.3 her turdaki değişken değerlerini verir.

Birinci turda aralık bütün dizidir. Orta indis (0 + 9)/2 = 4, ortadaki öğe 24'tür. 24 > 18 olduğu için COMPARE 1 verir: 18 varsa 24'ün solundadır. Sağ yarı, yani 4–9 indisleri, tek karşılaştırmayla atılır ve right = 3 olur. İkinci turda orta (0 + 3)/2 = 1, öğe 13'tür. 13 < 18 olduğundan sol taraf atılır: left = 2. Üçüncü turda orta (2 + 3)/2 = 2'dir ve list[2] = 18 aranana eşittir. Fonksiyon 2 döndürür. On öğeli dizide değer üç karşılaştırmayla bulunmuştur.

3.5.4Kod izleme: 25 dizide yok

Başarısız bir arama, döngünün nasıl sona erdiğini gösterir. binsearch(list, 25, 0, 9) çağrısı Tablo 3.4'teki gibi ilerler.

Birinci turda 24 < 25 çıkar ve arama sağ yarıya geçer: left = 5. İkinci turda orta (5 + 9)/2 = 7'dir; 36 > 25 olduğundan right = 6 olur. Üçüncü turda orta (5 + 6)/2 = 5, öğe 27'dir; 27 > 25 olduğundan right = 4 olur. Artık left = 5 > right = 4'tür ve aralık boştur. Döngü koşulu yanlış çıkar, fonksiyon −1 döndürür.

Döngü bittiğinde left'in gösterdiği yer de bir bilgi taşır. left = 5, 25 dizide olsaydı sıralamayı bozmadan yerleşeceği indistir: 24 ile 27 arası. Döngü boyunca left'in solundaki her öğe aranandan küçük, right'ın sağındaki her öğe büyük kalır. Aralık boşaldığında bu iki bölge yan yana gelir ve left ilk büyük öğeyi gösterir. Sıralı bir diziye ekleme yapan programlar bu gözlemi kullanır.

3.5.5Özyinelemeli binsearch()

İkili arama özyinelemeli bir yapıdadır: aralığın yarısında yapılan arama da bir ikili aramadır. Döngü yerine aralığı küçülterek kendini çağıran sürüm şöyledir:

int binsearch(int list[], int x, int l, int r) {
  int m;
  if (l > r) return -1;          /* aralik bos */
  m = (l + r) / 2;
  switch (COMPARE(list[m], x)) {
    case -1: return binsearch(list, x, m + 1, r);
    case 0:  return m;
    case 1:  return binsearch(list, x, l, m - 1);
  }
  return -1;                     /* ulasilmaz */
}

Kodu kısa tutmak için parametre adları kısaltılmıştır: x aranan değer, l ve r aralığın sol ve sağ ucu, m orta indistir. Fonksiyonun iki taban durumu vardır. Birincisi aralığın boş olmasıdır (l > r); değer bulunamamıştır ve −1 döner. İkincisi case 0 dalıdır; değer bulunmuştur ve indisi döner. Öteki iki dal özyinelemeli adımdır. Ortadaki öğe küçükse arama [m + 1, r] aralığında, büyükse [l, m − 1] aralığında sürer.

İki özyinelemeli çağrı da return ile başlar: alt çağrının sonucu hiç değiştirilmeden yukarı iletilir. Bu çağrılar birer kuyruk çağrısıdır. Fonksiyonun sonundaki return -1; satırına hiçbir zaman ulaşılmaz, çünkü COMPARE yalnız −1, 0 ya da 1 verir ve üç dal da return ile biter. Satırın yazılma nedeni derleyicidir: switch'in her olasılığı kapsadığını bilemeyen derleyici, değer döndürmeden biten bir yol görür ve uyarı verir. Bu satır o uyarıyı önler.

3.5.6Kod izleme: özyinelemeli sürüm ve çağrı yığını

Özyinelemeli binsearch(list, 18, 0, 9) çağrısı, döngüsel sürümle aynı orta indisleri (4, 1, 2) dener. Fark, her turun ayrı bir çerçevede yapılmasıdır. Tablo 3.5 çağrı yığınının değişimini gösterir.

Tabloda bs(l, r), binsearch(list, 18, l, r) çağrısının kısaltmasıdır. İniş aşamasında her çağrı aralığı yarıya indirip yeni bir çerçeve açar. En derin noktada, adım 5 ve 6'da, yığında main'in üstünde üç binsearch çerçevesi vardır. Taban durum 2 döndürünce çıkış başlar. bs(2, 3), 2'yi case -1 dalında bekleyen bs(0, 3)'e döndürür. O da hiçbir işlem yapmadan 2'yi case 1 dalında bekleyen bs(0, 9)'a döndürür. Son olarak 2, main'e ulaşır.

Çıkış aşamasında hiçbir hesap yapılmaz. Faktöriyelde dönüş yolunda çarpmalar vardı; burada dönen değer olduğu gibi aktarılır. Bu fark, iki fonksiyonun kuyruk özyinelemeli olup olmamasından gelir. Kuyruk çağrısı eniyilemesi açıksa derleyici bu üç çerçeveyi tek çerçeveye indirir ve kod, döngüsel sürümle aynı biçimde çalışır.

Başarısız aramada derinlik bir fazla olabilir. binsearch(list, 25, 0, 9) çağrısı [0, 9], [5, 9], [5, 6] ve [5, 4] aralıklarıyla dört çerçeve açar. Son çerçeve boş aralığı görür ve hemen −1 döndürür. Döngüsel sürümde bu son denetim, döngü koşulunun yanlış çıkmasına karşılık gelir.

3.5.7Karmaşıklık

İkili aramanın hızı, her turda aralığın en az yarıya inmesinden gelir. Aralıktaki öğe sayısı n'den başlayarak n/2, n/4, … diye küçülür ve en geç 1'e indiğinde son karşılaştırma yapılır.

Aynı sonuç bir yineleme bağıntısıyla da elde edilir. T(n), n öğeli bir aralıkta aramanın maliyeti olsun. Bir tur sabit bir c maliyetiyle aralığı yarıya indirir:

T(n) = T(n/2) + c, T(1) = c

Bağıntı açılırsa T(n) = T(n/4) + 2c = T(n/8) + 3c = … = T(n/2^k) + kc bulunur. n/2^k = 1 olduğunda, yani k = log₂ n iken, T(n) = c(log₂ n + 1) çıkar. Bu, O(log n)'dir.

Logaritmik büyümenin ne demek olduğunu Tablo 3.6 gösterir. Doğrusal arama en kötü durumda dizideki her öğeye bakar; ikili arama ise yalnız birkaç öğeye.

Test dizisinde n = 10'dur ve en çok ⌊log₂ 10⌋ + 1 = 3 + 1 = 4 tur gerekir. 18 için üç tur yetti. Dört tur gerektiren bir örnek 40'tır: orta indisler 4, 7, 8 ve 9 sırasıyla denenir. Bu sayılar, test dizisinde 0'dan 41'e kadar bütün değerler aranarak doğrulanmıştır; hiçbir arama dört turu aşmaz. Bir milyon öğeli bir dizide de bütün başarılı ve başarısız aramalar denendiğinde en çok tur 20 çıkar.

Bellek maliyeti iki sürümde farklıdır. Döngüsel sürüm yalnız birkaç değişken kullanır; ek bellek O(1)'dir. Özyinelemeli sürüm her tur için bir çerçeve açar; derinlik tur sayısı kadardır ve ek bellek O(log n)'dir. Bir milyar öğede bu 30 çerçeve demektir; pratikte önemsizdir.

İkili aramanın iki ön koşulu vardır. Birincisi, dizi sıralı olmalıdır; sırasız bir dizide yarıyı atma kararı yanlış olur ve var olan değer bulunamayabilir. İkincisi, herhangi bir indisteki öğeye O(1) zamanda erişilebilmelidir. Dizi bu koşulu sağlar: list[middle], başlangıç adresine middle öğe boyu eklenerek tek adımda bulunur. Bağlı listede ise ortadaki düğüme ulaşmak için baştan itibaren düğüm düğüm ilerlemek gerekir. Her tur O(n) adım alır ve ikili aramanın kazancı kaybolur.

3.6Hanoi kuleleri

Faktöriyel ve ikili arama, her adımda tek bir özyinelemeli çağrı yapar. Hanoi kuleleri, iki özyinelemeli çağrı yapan ilk örnektir. İki çağrı, çağrı sayısını hızla büyütür ve algoritmanın maliyetini hesaplamak için yeni bir araç gerektirir: yineleme bağıntısı.

3.6.1Problem

Üç kule (çubuk) vardır: kaynak, ara ve hedef. Kaynak kulede n disk durur. Disklerin boyları farklıdır ve her disk, üzerindekinden büyüktür; en büyük disk en altta, en küçüğü en üsttedir. Amaç bütün diskleri, ara kuleden yardım alarak, hedef kuleye aynı düzende taşımaktır. İki kural vardır:

1. Her hamlede yalnız bir disk taşınır; bir kulenin en üstündeki disk alınıp başka bir kulenin en üstüne konur.
2. Bir disk kendinden küçük bir diskin üzerine konamaz.

Bir ya da iki diskle problem kolaydır. Tek disk doğrudan hedefe taşınır. İki diskte küçük disk araya, büyük disk hedefe, küçük disk de hedefe taşınır: üç hamle. Üç diskte deneme yanılmayla çözüm bulunabilir, ama on diskte bu yol işe yaramaz. Disk sayısından bağımsız, sistemli bir yönteme ihtiyaç vardır.

3.6.2Özyinelemeli çözüm

Çözümün anahtarı en büyük diske odaklanmaktır. En büyük disk hedef kuleye bir an taşınmalıdır. O anda en büyük diskin üstünde hiçbir disk olamaz, çünkü yalnız en üstteki disk taşınabilir. Hedef kule de boş olmalıdır, çünkü en büyük disk hiçbir diskin üzerine konamaz. Geriye kalan n − 1 diskin hepsi o anda ara kulede durmalıdır. Bu gözlem çözümü üç adıma böler:

1. Üstteki n − 1 disk, hedef kuleden yardım alınarak kaynaktan araya taşınır.
2. En büyük disk kaynaktan hedefe taşınır.
3. n − 1 disk, kaynak kuleden yardım alınarak aradan hedefe taşınır.

Birinci ve üçüncü adım, aynı problemin n − 1 diskli bir örneğidir; yalnız kulelerin rolleri değişmiştir. Bu adımlarda en büyük disk ya kaynakta en altta durur ya da hedefte tek başınadır. Her iki durumda da öteki bütün disklerden büyük olduğu için hiçbir hamleyi engellemez; sanki orada yokmuş gibi davranılabilir. Taban durum tek disktir ve bir hamleyle çözülür. Algoritmanın C kodu şöyledir:

void hanoi(int n, char *kaynak, char *ara,
           char *hedef) {
  if (n == 1)
    printf("%s -> %s\n", kaynak, hedef);
  else {
    hanoi(n - 1, kaynak, hedef, ara);
    printf("%s -> %s\n", kaynak, hedef);
    hanoi(n - 1, ara, kaynak, hedef);
  }
}
/* main: hanoi(3, "A", "B", "C"); */

Kuleler adlarıyla (char * türünde dizgiler) temsil edilir. Kod diskleri bellekte gerçekten taşımaz; yalnız yapılacak hamleleri yazar. printf("%s -> %s\n", kaynak, hedef), kaynak kulenin en üstündeki diskin hedef kuleye taşındığını bildirir. n = 1 ise tek hamle yazılır. Değilse ilk özyinelemeli çağrı hanoi(n - 1, kaynak, hedef, ara) yapılır. Bu çağrıda ikinci ve dördüncü argümanın yer değiştirdiğine dikkat etmek gerekir: n − 1 diskin hedefi asıl problemin ara kulesidir, yardımcı kule de asıl hedeftir. Ardından en büyük diskin hamlesi yazılır. İkinci çağrı hanoi(n - 1, ara, kaynak, hedef), n − 1 diski aradan hedefe, kaynağı yardımcı kullanarak taşır.

3.6.3Kod izleme: hanoi(3, "A", "B", "C")

Üç diskli problemde A kaynak, B ara, C hedeftir. Çağrıların sırası ve yazılan hamleler Tablo 3.7'de verilmiştir. Tablodaki çağrılar hanoi(n, kaynak, ara, hedef) biçimindedir.

Yığın derinliği main sayılmadan verilmiştir. Program yedi satır yazar: A -> C, A -> B, C -> B, A -> C, B -> A, B -> C, A -> C. İlk üç hamle küçük iki diski B'ye taşır. Dördüncü hamle en büyük diski C'ye götürür. Son üç hamle B'deki iki diski C'ye, en büyük diskin üstüne taşır. Her hamle kurala uygundur; bu, programın çıktısı adım adım tahtada oynanarak da doğrulanabilir.

Tabloda iki sayı dikkat çeker. Toplam çağrı sayısı yedidir ve her çağrı tam bir printf yapar; taban durumlar birer, öteki çağrılar ortadaki birer hamleyi yazar. Yığın derinliği ise hiçbir zaman 3'ü geçmez. n diskli problemde bir çağrı zinciri n, n − 1, …, 1 diye iner; derinlik n'dir ve yığın maliyeti O(n)'dir.

3.6.4Çağrı ağacı

Bir özyinelemeli algoritmanın bütün çağrıları bir ağaç olarak çizilebilir. Her düğüm bir çağrıdır; bir çağrının yaptığı alt çağrılar onun çocuklarıdır. Hanoi'de her çağrının iki çocuğu vardır: sol çocuk ilk özyinelemeli çağrı, sağ çocuk ikincisidir. Şekil 3.10, kuleleri 1, 2 ve 3 diye adlandırılmış hanoi(3, "1", "2", "3") çağrısının ağacını verir. Her kutuda sırasıyla n, kaynak, ara ve hedef yazılıdır.

Ağaç, çağrı yığınının bütün tarihçesini taşır. Herhangi bir anda yığının içeriği, kökten o an çalışan düğüme giden yoldur. Örneğin en soldaki yaprak (1, 1, 2, 3) çalışırken yığında kök (3, 1, 2, 3), onun sol çocuğu (2, 1, 3, 2) ve yaprağın kendisi vardır. Yolun uzunluğu en çok ağacın yüksekliği kadardır; bu da yığın derinliğinin n olduğunu bir kez daha gösterir.

Hamlelerin sırası, ağacın kök ortada (inorder) gezinmesiyle elde edilir: önce sol alt ağaç, sonra düğümün kendisi, sonra sağ alt ağaç. Kodda da sıra böyledir: ilk özyinelemeli çağrı, printf, ikinci özyinelemeli çağrı. Her düğümün hamlesi “kaynak → hedef”tir ve sol alt ağacı bittikten sonra yazılır. Bu gezinme şu yedi hamleyi verir:

1→3 · 1→2 · 3→2 · 1→3 · 2→1 · 2→3 · 1→3

Program aynı çağrıyla çalıştırıldığında da bu sıra çıkar.

3.6.5Yineleme bağıntısı: kaç hamle?

n diskli problemin hamle sayısı h(n) olsun. Algoritma n − 1 diski iki kez taşır ve arada bir hamle yapar. Taban durum tek hamledir:

h(1) = 1, h(n) = h(n − 1) + 1 + h(n − 1) = 2·h(n − 1) + 1

Özyinelemeli algoritmaların maliyeti doğal olarak yineleme bağıntısıyla ifade edilir, çünkü algoritmanın kendisi de aynı biçimdedir. En basit çözüm yöntemi bağıntıyı tekrar tekrar yerine koyarak açmaktır:

h(1) = 1
h(n) = 2·h(n−1) + 1
     = 4·h(n−2) + 2 + 1
     = 8·h(n−3) + 4 + 2 + 1
     = …
     = 2ⁿ⁻¹·h(1) + 2ⁿ⁻² + … + 1
     = 2ⁿ − 1

Her satırda h(n − k) yerine 2·h(n − k − 1) + 1 konur. k adım sonra katsayı 2^k olur ve sağda 2^k−1 + … + 2 + 1 toplamı birikir. k = n − 1'de taban duruma ulaşılır: h(n) = 2ⁿ⁻¹·h(1) + 2ⁿ⁻² + … + 2 + 1. h(1) = 1 olduğundan bu, 2ⁿ⁻¹ + 2ⁿ⁻² + … + 1 geometrik toplamıdır ve 2ⁿ − 1'e eşittir. Toplamın değeri ikili sayılarla kolayca görülür: n tane 1 bitinden oluşan sayı, 2ⁿ'nin bir eksiğidir.

Tablo 3.8 üstel büyümenin hızını gösterir. Her yeni disk hamle sayısını iki katına çıkarır. Efsaneye göre bir tapınakta rahipler 64 diskli kuleyi taşıyor ve iş bitince dünya sona erecektir. 2⁶⁴ − 1 ≈ 1,8·10¹⁹ hamle, saniyede bir hamleyle yaklaşık 585 milyar yıl sürer. Bu süre evrenin bugünkü yaşının kırk katından fazladır.

Algoritmanın zaman maliyeti Θ(2ⁿ)'dir. Çağrı sayısı da hamle sayısına eşittir, çünkü her çağrı tam bir hamle yazar ve c(n) = 2c(n − 1) + 1 bağıntısını sağlar. Yığın maliyeti O(n)'dir. Teorem gereği bundan iyisi yoktur: daha akıllı bir program yazmak hamle sayısını azaltamaz, çünkü bu sayı problemin kendisinden gelir. Hanoi, çıktısının boyu üstel olan bir problemdir ve hiçbir algoritma çıktıyı yazmadan bitemez.

Kimi problemlerin ancak özyinelemeyle çözülebileceği söylenir. Bu sözün kuramsal karşılığı tam olarak böyle değildir: her özyineleme, açık bir yığınla döngüye çevrilebilir. Sözün asıl vurgusu, Hanoi gibi problemlerde özyinelemenin tek doğal ifade olmasıdır. Hanoi'nin döngülü çözümleri de vardır, ama hiçbiri yukarıdaki üç satırlık fikir kadar açık değildir.

3.7Permütasyon üretimi

Hanoi'de çıktı üstel boydaydı. Permütasyon üretiminde çıktı daha da hızlı büyür: n öğenin n! dizilişi vardır. Bu problem, özyinelemeyi ilk kez bir döngünün içinde kullanır ve geri izlemenin temel fikrini, yapılan seçimi geri almayı, tanıtır.

3.7.1Problem ve özyinelemeli fikir

n! sayısı basit bir sayma kuralından gelir. Birinci konuma n öğeden herhangi biri gelebilir. İkinci konuma kalan n − 1 öğeden biri, üçüncüye kalan n − 2 öğeden biri gelir. Seçenekler çarpılır: n · (n − 1) · … · 1. Örneğin {a, b, c} kümesinin 3! = 6 dizilişi vardır: abc, acb, bac, bca, cab, cba.

Aynı sayma kuralı özyinelemeli bir algoritma verir. {a, b, c, d} kümesinin dizilişleri dört gruba ayrılır:

• a ile başlayan ve ardından {b, c, d}'nin bir dizilişi gelenler,
• b ile başlayan ve ardından {a, c, d}'nin bir dizilişi gelenler,
• c ile başlayan ve ardından {a, b, d}'nin bir dizilişi gelenler,
• d ile başlayan ve ardından {a, b, c}'nin bir dizilişi gelenler.

Her grup, üç öğeli bir kümenin dizilişlerini ister. Üç öğeli problem aynı biçimde iki öğeli problemlere, onlar da tek öğeli problemlere iner. Tek öğenin tek dizilişi vardır; bu taban durumdur.

3.7.2Takasla gerçekleme: perm()

Fikri koda dökmek için “kalan öğeler” kümesini ayrı bir dizide tutmak gerekmez. Bütün öğeler tek bir karakter dizisinde durur. i indisi, dizinin hangi konumunun şu an doldurulduğunu gösterir. list[0..i−1] konumları sabitlenmiş önektir; list[i..n−1] konumlarında henüz yerleştirilmemiş öğeler bulunur. i. konuma sırayla her aday takasla getirilir, kalan konumlar özyinelemeyle dizilir, sonra geri takasla dizi eski hâline döndürülür.

Takas için üç argümanlı bir makro kullanılır:

#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))

Makro, t geçici değişkeni üzerinden x ile y'nin değerlerini değiştirir. Üç atama virgül işleciyle tek bir ifadede birleştirilmiştir; virgül işleci ifadeleri soldan sağa sırayla hesaplar. Makronun fonksiyon yerine tercih edilme nedeni, C'de bir fonksiyonun çağıranın değişkenlerini değiştirmek için adres (işaretçi) alması gerekmesidir. Makro ise önişlemcide metin olarak yerine konur ve doğrudan list[i] ile list[j] üzerinde çalışır. Permütasyon fonksiyonu şöyledir:

void perm(char *list, int i, int n) {
  int j, temp;
  if (i == n) {                  /* bir dizilis */
    for (j = 0; j < n; j++) printf("%c", list[j]);
    printf("\n");
  } else
    for (j = i; j < n; j++) {
      SWAP(list[i], list[j], temp);
      perm(list, i + 1, n);
      SWAP(list[i], list[j], temp);
    }
}

perm(list, i, n), list dizisinin ilk i konumu sabitken kalan konumların bütün dizilişlerini yazar. i == n taban durumdur: bütün konumlar sabitlenmiştir ve dizi bir permütasyondur. İçteki for döngüsü n karakteri yazar, ardından satır sonu gelir. Taban durumda değilse dış for döngüsü j'yi i'den n − 1'e kadar götürür. Her turda üç iş yapılır:

1. SWAP(list[i], list[j], temp): j. konumdaki öğe i. konuma getirilir. j = i iken öğe kendisiyle takas edilir ve dizi değişmez.
2. perm(list, i + 1, n): i. konum artık sabittir; kalan konumların bütün dizilişleri yazılır.
3. SWAP(list[i], list[j], temp): aynı takas tekrarlanır ve dizi, döngü turunun başındaki hâline döner.

temp değişkeni int olarak bildirilmiştir; içine char konup yeniden char'a atanır. Bu dönüşüm değer kaybettirmez, çünkü her char değeri int'e sığar. Fonksiyonun ilk çağrısı, bütün diziyi düzenlemek için perm(list, 0, n) biçimindedir. list değiştirilebilir bir dizi olmalıdır: char s[] = "abc"; bildirimi böyle bir dizi oluşturur, ama perm("abc", 0, 3) biçiminde bir dizgi sabiti vermek tanımsız davranıştır. Dizgi sabitleri salt okunur bellekte durabilir ve takas programı çökertebilir.

3.7.3Kod izleme: perm("abc", 0, 3)

char list[] = "abc" dizisiyle yapılan perm(list, 0, 3) çağrısı altı diziliş yazar. Tablo 3.9 izlemenin bütün adımlarını verir. Yığın sütununda p(i), perm(list, i, 3) çağrısının kısaltmasıdır.

Tabloda p(2) çağrısının kendi döngüsü kısaltılmıştır. i = 2 iken j yalnız 2 değerini alır; kendisiyle takas yapılır, p(3) çağrılır ve geri takas yine kendisiyle olur. Bu adımlar diziyi değiştirmez.

Çıktı sırası abc, acb, bac, bca, cba, cab'dir. Son iki satır sözlük sırasına uymaz: cab'den önce cba gelir. Bunun nedeni adım 14'teki takastır. j = 2 turunda a ile c yer değiştirir ve dizi cba olur; ikinci konumda b, üçüncüde a durur. Alt çağrı bu sırayla başladığı için önce cba yazılır. Dizilişlerin hepsi tam bir kez çıkar; yalnız sıraları farklıdır.

Adım 13 ve 20'deki geri takaslar algoritmanın doğruluğu için şarttır. Dış döngünün her turu, diziyi abc hâlinde bulmayı bekler. j = 1 turu bittiğinde dizi bac olarak kalsaydı, j = 2 turu list[0] ile list[2]'yi, yani b ile c'yi takas ederdi. Bu durumda c ile başlayan dizilişler yerine b ile başlayanlar ikinci kez üretilirdi. Program çalıştırılıp çağrıdan sonra dizi yazdırıldığında abc görülür: her çağrı, diziyi aldığı gibi bırakır.

3.7.4Özyineleme ağacı ve karmaşıklık

perm'in çağrıları bir ağaç oluşturur. Kökte hiçbir konum sabit değildir. Her düzey bir konumu daha sabitler ve düğümün çocukları, o konuma gelebilecek öğelerdir. Yapraklar tamamlanmış dizilişlerdir.

Şekil 3.12'deki ağaçta kökün üç çocuğu (a, b, c), her birinin iki çocuğu (ab, ac, …), onların da birer çocuğu vardır. Kardeş dallar aynı başlangıç dizisini görmelidir; ikinci SWAP diziyi bu yüzden onarır. Ağacın her düzeyindeki düğüm sayısı çağrı sayısını verir. k. düzeyde ilk k konum sabittir ve bu konumlar n · (n − 1) · … · (n − k + 1) farklı biçimde doldurulabilir:

çağrı sayısı = 1 + n + n(n − 1) + … + n!

n = 3 için 1 + 3 + 6 + 6 = 16, n = 4 için 1 + 4 + 12 + 24 + 24 = 65 çağrı yapılır. Bu sayılar, fonksiyona bir sayaç eklenerek programla da doğrulanmıştır. Toplamın son iki terimi n!'dir ve öncekiler hızla küçülür; toplam yaklaşık e · n! ≈ 2,72 · n!'dir. Yaprak sayısı tam n!'dir.

Zamanı belirleyen yapraklardaki yazma işidir. Her yaprak n karakter yazar; n! yaprak toplam n · n! karakter eder. İç düğümlerde yapılan işler (takaslar ve döngü denetimleri) çağrı başına sabittir ve toplamı O(n!)'dir. Toplam zaman Θ(n · n!)'dir. Permütasyon problemi kimi kaynaklarda kısaca O(n!) diye anılır; bu yazım, diziliş sayısını anlatır ama her dizilişi yazmanın n çarpanını gözden kaçırır. Yığın maliyeti derinlik kadardır: n + 1 çerçeve, yani O(n).

Faktöriyel büyümesi üstel büyümeden de hızlıdır. n = 10'da 10! = 3.628.800 diziliş vardır ve yazılacak karakter sayısı 36 milyonu geçer. n = 20'de diziliş sayısı 2,4·10¹⁸'dir; saniyede bir milyar diziliş üreten bir makine bile bu işi 77 yılda bitirir. Bütün dizilişleri sırayla denemeye dayanan bir çözüm bu yüzden ancak çok küçük n için kullanılabilir.

3.8Kaba kuvvet ve geri izleme

Permütasyon ve alt küme üretimi, bir problemin bütün olası çözüm adaylarını sistemli biçimde dolaşmanın yollarıdır. Pek çok problem bu dolaşmayla çözülebilir: adaylar üretilir, her biri kurallara göre sınanır. Bu bölümün geri kalanı, bu yaklaşımı ve onun akıllı biçimini, geri izlemeyi, inceler.

3.8.1İki yaklaşım

Kaba kuvvet bilgisayarın hızına güvenir. Kurması kolaydır ve her zaman doğru cevabı verir, çünkü hiçbir adayı atlamaz. Sorunu aday sayısıdır. n evet/hayır kararından oluşan bir problemde 2ⁿ, n öğenin sıralanmasını isteyen bir problemde n! aday vardır. Her ikisi de n birkaç düzineyi geçince hiçbir makinenin bitiremeyeceği sayılara ulaşır.

Geri izleme aynı adayları dolaşır, ama bir farkla: bir aday tamamlanmadan önce sınanır. Kısmi bir çözümün kuralı bozduğu görülürse, o kısmi çözümle başlayan adayların hiçbiri üretilmez. Örneğin sekiz veziri yerleştirirken ilk iki vezir birbirini tehdit ediyorsa, öteki altı vezirin bütün yerleşimleri tek seferde elenir. Bu eleme işlemi ağacın bir dalını kesmeye benzediği için budama adını alır. En kötü durum maliyeti çoğu zaman kaba kuvvetle aynı mertebede kalır, ama pratikte denenen aday sayısı çok küçülür.

Bir problemi çözerken seçilen veri yapısından ve yöntemden asla tam emin olunmamalıdır. Kaba kuvvetle çalışan bir çözüm, daha iyisinin aranmasını gerektiren bir başlangıç noktasıdır. Bu tutum, “daha iyi bir çözüm yöntemi vardır da biz bulamıyoruz” cümlesiyle özetlenebilir. Geri izleme ve at gezisindeki sezgisel kural, böyle bir aramanın ürünleridir.

3.8.2Geri izlemenin genel kalıbı

Geri izleme algoritmalarının hepsi aynı iskeleti izler. Aşağıdaki sözde kod bu iskeleti verir:

void geri_izle(kismi_cozum) {
  if (tam_cozum_mu) { yaz; return; }
  for (her aday secim)
    if (kurallara_uygun) { sec; geri_izle(...); secimi_geri_al; }
}

Fonksiyon bir kısmi çözüm alır. Kısmi çözüm tamamlanmışsa yazılır ve fonksiyon döner; bu taban durumdur. Tamamlanmamışsa kısmi çözümü bir adım uzatabilecek her aday seçim sırayla denenir. Kurallara uyan seçim kısmi çözüme eklenir (sec), fonksiyon kendini çağırır ve çağrı dönünce seçim geri alınır (secimi_geri_al). Kurallara uymayan seçimler için özyinelemeli çağrı hiç yapılmaz; budama budur.

Permütasyon kodu bu kalıba tam uyar. Kısmi çözüm sabitlenmiş önektir. Aday seçimler list[i..n−1] öğeleridir. Seçmek ilk SWAP'tır, seçimi geri almak ikinci SWAP'tır. Permütasyonda her seçim kurallara uyar, dolayısıyla budama yoktur. n-vezir probleminde ise kurallara_uygun sınaması gerçek bir iş yapar ve dalların büyük kısmını keser.

Geri izleme kimi zaman “senaryoyu sondan başa geri sarmak” diye yanlış anlaşılır. Yöntem çözümü sondan başa kurmaz. Kısmi çözümü ileriye doğru kurar; çıkmaza girince yalnız son seçimi geri alır ve aynı noktadan ileriye doğru başka bir seçimle devam eder. Geri gidilen tek şey son karar noktasıdır.

3.8.3Alt küme üretimi

Bir kümenin bütün alt kümelerini yazdırmak, en sade geri izleme örneğidir. n öğeli bir kümenin 2ⁿ alt kümesi vardır, çünkü her öğe için iki seçenek bulunur: alt kümeye alınır ya da alınmaz. Algoritma bu kararları sırayla verir:

void altkume(char *s, int n, int i,
             int sec[]) {
  int j;
  if (i == n) {                  /* karar bitti */
    printf("{");
    for (j = 0; j < n; j++)
      if (sec[j]) printf("%c", s[j]);
    printf("}\n");
    return;
  }
  sec[i] = 1; altkume(s, n, i + 1, sec);
  sec[i] = 0; altkume(s, n, i + 1, sec);
}

s öğeleri tutan karakter dizisi, n öğe sayısıdır. sec dizisi kararları tutar: sec[j] 1 ise j. öğe alınmış, 0 ise alınmamıştır. i, sıradaki kararın hangi öğe için verileceğini gösterir. i == n taban durumdur: bütün kararlar verilmiştir ve sec dizisinde 1 olan öğeler küme parantezleri içinde yazılır. Taban durumda değilse iki çağrı yapılır. Önce sec[i] = 1 ile i. öğe alınır ve kalan kararlar için fonksiyon çağrılır. Sonra sec[i] = 0 ile öğe çıkarılır ve aynı çağrı tekrarlanır.

Kodda “seçimi geri al” adımı ayrı bir satır olarak görünmez. sec[i] = 0 ataması iki işi birden yapar: birinci dalın seçimini geri alır ve ikinci dalın seçimini yapar. Fonksiyondan çıkarken sec[i] 0 kalır, ama bunun bir zararı yoktur. Bir üst çağrı, sec[i]'yi okumadan önce her zaman yeniden atar; taban durumdaki yazdırma ise yalnız o ana kadar atanmış değerleri okur.

Tablo 3.10'da kararlar, bir ikili sayacın geriye doğru saymasına benzer: sec dizisi 111, 110, 101, …, 000 diye ilerler. Bunun nedeni “al” kararının “alma”dan önce denenmesidir. Son satırdaki {} boş kümedir; boş küme de her kümenin bir alt kümesidir.

Karmaşıklık hesabı Hanoi'ye benzer. Her çağrı iki çağrı yapar ve derinlik n'dir. Çağrı ağacı n düzeyli tam bir ikili ağaçtır: 2ⁿ yaprağı ve toplam 2ⁿ⁺¹ − 1 düğümü vardır. n = 3 için 15, n = 4 için 31 çağrı yapılır. Her yaprak sec dizisini baştan sona dolaşarak O(n) iş yapar. Toplam zaman Θ(n · 2ⁿ), yığın maliyeti O(n)'dir. sec dizisini çağıran fonksiyon bir kez ayırır ve bütün çağrılar aynı diziyi kullanır; her çerçevede yalnız diziye işaretçi durur.

3.9Sağlanabilirlik (SAT) problemi

Alt küme üretimi, her öğe için iki seçenek dolaşıyordu. Aynı dolaşma, mantık değişkenlerine doğru ya da yanlış değeri atamaya da uygulanabilir. Bu bölümün problemi, bilgisayar biliminin en ünlü problemlerinden biridir ve kaba kuvvetin sınırlarını açıkça gösterir.

3.9.1Problem

Bu bölümde incelenen formül şudur:

(x₁ ∧ ¬x₂) ∨ (¬x₁ ∧ x₃) ∨ ¬x₃

Formül üç terimin veyasıdır ve terimlerden biri doğruysa formül doğrudur. Örneğin x₃ = F ise son terim ¬x₃ doğrudur ve formül de doğrudur. Böylece formülün sağlanabilir olduğu hemen görülür. Soru, bir bilgisayar programının bunu nasıl bulacağıdır.

Kaba kuvvet çözümü bütün atamaları denemektir. Üç değişkenin her biri iki değer aldığından 2³ = 8 atama vardır: {F, F, F}, {F, F, T}, …, {T, T, T}. n değişkende atama sayısı 2ⁿ'dir. Her atamada formül bir kez değerlendirilir; formülün boyu |F| ise bu O(|F|) zaman alır. Toplam maliyet O(2ⁿ · |F|)'dir.

Üstel maliyet paralel donanımla da aşılamaz. İş m işlemciye eşit bölünse bile maliyet O(2ⁿ/m) olur. 100 değişkenli bir formülde 2¹⁰⁰ ≈ 1,3·10³⁰ atama vardır; bir milyon işlemci bile bu sayıyı ancak 10²⁴ mertebesine indirir.

SAT için polinom zamanlı bir algoritma bilinmiyor. Problem, NP-tam (NP-complete) denen problem sınıfının ilk üyesidir. Bu sınıftaki problemlerden biri için polinom zamanlı bir algoritma bulunursa, sınıftaki bütün problemler polinom zamanda çözülebilir. Bugüne kadar böyle bir algoritma bulunamamıştır, ama olmadığı da kanıtlanamamıştır. Her alt cümlesinde (clause) en çok iki değişken bulunan özel biçim (2-SAT) polinom zamanda çözülür; alt cümleler üç değişkenli olunca (3-SAT) problem yeniden NP-tam olur. Problemlerin bu biçimde sınıflandırılması hesaplama kuramı (theory of computation) dersinin konusudur.

3.9.2Formül ağacı ve kök sonda değerlendirme

Bir formülü programda değerlendirmenin doğal yolu onu bir ağaç olarak saklamaktır. Şekil 3.14'teki ağaçta her iç düğüm bir işleçtir. ∧ ve ∨ düğümlerinin iki çocuğu vardır. ¬ düğümünün tek işleneni vardır ve sağ çocukta durur. Yapraklar değişkenlerdir; aynı değişken birden çok yaprakta görünebilir. Ağacın C'deki tanımı ve değerlendirme fonksiyonu şöyledir:

typedef enum { DEGIL, VE, VEYA, DOGRU, YANLIS } mantik;
typedef struct agac *agac_gost;
struct agac {
  agac_gost solcocuk, sagcocuk;
  mantik veri;
  short deger;
};

void kok_sonda_degerlendir(agac_gost L) {
  if (L) {
    kok_sonda_degerlendir(L->solcocuk);
    kok_sonda_degerlendir(L->sagcocuk);
    switch (L->veri) {
      case DEGIL: L->deger = !L->sagcocuk->deger; break;
      case VE:   L->deger = L->solcocuk->deger
                         && L->sagcocuk->deger; break;
      case VEYA: L->deger = L->solcocuk->deger
                         || L->sagcocuk->deger; break;
      case DOGRU:  L->deger = 1; break;
      case YANLIS: L->deger = 0; break;
    }
  }
}

İlk satır, düğüm türlerini adlandıran bir sayım türü (enumeration) tanımlar. DEGIL, VE, VEYA işleç düğümleridir. DOGRU ve YANLIS yapraklar içindir: bir atama yapıldığında her yaprağın türü, değişkenin o atamadaki değerine göre bu ikisinden biri olur. İkinci satır agac_gost adını “struct agac'a işaretçi” anlamında tanımlar. Yapının kendisi üçüncü bildirimdedir: iki çocuk işaretçisi, düğümün türü (veri) ve düğümün hesaplanan değeri (deger).

typedef'in yapı tanımından önce gelmesi C'de geçerlidir. struct agac bu noktada henüz tamamlanmamış (incomplete) bir türdür, ama ona işaretçi tanımlamak için türün içeriğini bilmek gerekmez. Bu sayede yapı, kendi türünden düğümlere işaret eden alanlar içerebilir. Bir yapının kendi türünden bir alanı (işaretçi değil, değerin kendisi) olamaz; bu, sonsuz büyüklükte bir yapı demek olurdu.

Adların seçiminde iki ayrıntı vardır. enum { not, and, or, true, false } gibi İngilizce adlar sorun çıkarır. true ve false, C99'un <stdbool.h> başlığında makro olarak tanımlıdır ve C23'te anahtar sözcük olmuştur; not, and, or ise <iso646.h> başlığında işleç yerine geçen makrolardır. Bu başlıklardan biri eklenirse sayım türü derlenmez. İkinci ayrıntı, typedef struct agac {…}; gibi sonuna ad yazılmamış bir typedef'in hiçbir ad tanımlamamasıdır. Derleyici bu satırı kabul eder ama uyarı verir. Yukarıdaki kodda ASCII ve çakışmasız adlar kullanılmıştır.

Düğümün bellekteki görünümü de incelenmeye değer. 64 bitlik bir sistemde iki işaretçinin her biri 8 bayt tutar ve yapının ilk 16 baytını oluşturur. veri alanı (bir enum, 4 bayt) 16. bayttan, deger alanı (short, 2 bayt) 20. bayttan başlar. Derleyici yapının sonuna 2 baytlık dolgu ekler ve boyu 8'in katı olan 24 bayta tamamlar. Bu dolgu, yapılardan oluşan bir dizide her işaretçinin 8'in katı bir adreste durmasını sağlar. Bu sayılar sizeof ve offsetof ile ölçülmüştür; başka bir derleyicide ya da 32 bitlik bir sistemde farklı çıkabilir.

Ağacın düğümleri çalışma zamanında malloc ile oluşturulur. Sunumdaki kodda bu kısım gösterilmez; tam bir program için aşağıdaki iki yardımcı fonksiyon yeterlidir:

agac_gost yeni_dugum(mantik v, agac_gost sol, agac_gost sag) {
  agac_gost p = malloc(sizeof *p);
  if (p == NULL) {               /* bellek ayrilamadi */
    fprintf(stderr, "bellek yok\n");
    exit(EXIT_FAILURE);
  }
  p->veri = v;
  p->solcocuk = sol;
  p->sagcocuk = sag;
  p->deger = 0;
  return p;
}

void agac_sil(agac_gost L) {     /* kok sonda: once cocuklar */
  if (L) {
    agac_sil(L->solcocuk);
    agac_sil(L->sagcocuk);
    free(L);
  }
}

yeni_dugum, bir düğüm büyüklüğünde bellek ister. sizeof *p ifadesi, p'nin gösterdiği türün boyunu verir; tür adı yazılmadığı için p'nin türü değişse bile ifade doğru kalır. malloc bellek ayıramazsa NULL döndürür. Bu durum denetlenmeden p->veri yazılırsa program boş işaretçiye yazar ve çöker; bu yüzden dönüş değeri hemen sınanır. agac_sil, ağacın bütün düğümlerini geri verir. Önce iki çocuğu siler, sonra düğümün kendisini. Sıra önemlidir: önce düğüm serbest bırakılsaydı, L->solcocuk alanı serbest bırakılmış bellekten okunurdu ve bu tanımsız davranıştır. Ağaç silinmeden program biterse işletim sistemi belleği zaten geri alır, ama uzun çalışan bir programda her atamada yeni ağaç kurulup silinmezse bellek sızıntısı oluşur.

Formül ağacı ve atama işlemi şöyle kurulur:

agac_gost y[5];   /* yapraklar: x1, x2, x1, x3, x3 */

agac_gost formul_kur(void) {
  int k;
  for (k = 0; k < 5; k++)
    y[k] = yeni_dugum(YANLIS, NULL, NULL);
  /* (x1 VE DEGIL x2) VEYA (DEGIL x1 VE x3) VEYA DEGIL x3 */
  return yeni_dugum(VEYA,
           yeni_dugum(VEYA,
             yeni_dugum(VE, y[0], yeni_dugum(DEGIL, NULL, y[1])),
             yeni_dugum(VE, yeni_dugum(DEGIL, NULL, y[2]), y[3])),
           yeni_dugum(DEGIL, NULL, y[4]));
}

void yapraklari_yerlestir(agac_gost kok, int x1, int x2, int x3) {
  (void)kok;            /* yapraklara y[] ile dogrudan erisilir */
  y[0]->veri = x1 ? DOGRU : YANLIS;
  y[1]->veri = x2 ? DOGRU : YANLIS;
  y[2]->veri = x1 ? DOGRU : YANLIS;
  y[3]->veri = x3 ? DOGRU : YANLIS;
  y[4]->veri = x3 ? DOGRU : YANLIS;
}

Beş yaprak y dizisinde tutulur. Ağaç kurulurken bu yaprakların adresleri ilgili işleç düğümlerine çocuk olarak verilir. yapraklari_yerlestir bir atamayı ağaca yerleştirir: her yaprağın türünü, temsil ettiği değişkenin değerine göre DOGRU ya da YANLIS yapar. Ağacın yapısı değişmez; yalnız yapraklar değişir.

kok_sonda_degerlendir, ağacın değerini kök sonda (postorder) gezinmeyle hesaplar: önce sol alt ağaç, sonra sağ alt ağaç, en son düğümün kendisi. Bu sıra zorunludur, çünkü bir işleç düğümünün değeri çocuklarının değerine bağlıdır ve çocuklar ondan önce hesaplanmalıdır. Fonksiyon if (L) ile başlar; boş bir alt ağaç (NULL) için hiçbir şey yapmaz. Bu denetim hem yapraklarda hem de ¬ düğümünün boş sol çocuğunda özyinelemeyi durdurur. switch deyimi düğümün türüne göre değeri hesaplar. DEGIL düğümü sağ çocuğun değerini tersine çevirir. VE ve VEYA düğümleri iki çocuğun değerini C'nin && ve || işleçleriyle birleştirir. Yapraklar türlerine göre 1 ya da 0 değerini alır.

3.9.3Kaba kuvvetle bütün atamalar

Sekiz atamayı dolaşmak için iç içe üç döngü yazılabilir. Daha kısa bir yol, 0'dan 7'ye kadar sayan tek bir döngü kullanmak ve sayacın bitlerini değişkenlere dağıtmaktır:

int m, x1, x2, x3;
for (m = 0; m < 8; m++) {    /* 2^3 atama */
  x1 = (m >> 2) & 1;
  x2 = (m >> 1) & 1;
  x3 = m & 1;
  yapraklari_yerlestir(kok, x1, x2, x3);
  kok_sonda_degerlendir(kok);
  if (kok->deger)
    printf("%d%d%d\n", x1, x2, x3);
}

m'nin üç bitlik ikili gösterimi bir atamadır. (m >> 2) & 1 ifadesi m'yi iki bit sağa kaydırır ve en sağdaki biti alır; bu m'nin 2 numaralı bitidir ve x₁'e atanır. Aynı biçimde 1 numaralı bit x₂'ye, 0 numaralı bit x₃'e gider. m = 5 için ikili gösterim 101'dir ve x₁ = 1, x₂ = 0, x₃ = 1 çıkar. Her turda atama ağaca yerleştirilir, ağaç değerlendirilir ve kök doğruysa atama yazılır.

Tablo 3.11, sekiz atamanın yedisinin formülü sağladığını gösterir. Program 000, 001, 010, 011, 100, 101 ve 110 satırlarını yazar; yalnız x₁ = x₂ = x₃ = 1 ataması formülü sağlamaz. Bu çıktı, kod tam bir programa dönüştürülüp çalıştırılarak doğrulanmıştır.

SAT sorusu yalnız “bir atama var mı?” diye sorar. Bu soruyu cevaplamak için bütün atamaları yazmak gerekmez; doğru çıkan ilk atamada return eden bir yordam yeterlidir. Böyle bir yordam bu formülde ilk atama olan 000'da durur. Formül sağlanamaz olsaydı ise yordam sekiz atamanın hepsini denemek zorunda kalırdı. Kaba kuvvetin en kötü durumu, cevabın “hayır” olduğu durumdur.

3.9.4SAT türleri ve ön hesaplama

Sağlanabilirlik sorusu farklı biçimlerde sorulabilir:

Devre sağlanabilirliği (CIRCUIT-SAT)

Verilen bir mantık devresinin çıkışını 1 yapacak bir giriş ataması var mı? Devre, kapılardan (VE, VEYA, DEĞİL) oluşan bir ağdır.

Formül sağlanabilirliği (Formula SAT)

Bu bölümdeki gibi ∧, ∨ ve ¬ ile kurulmuş bir önerme formülünün doğru yapılıp yapılamayacağı.

3-CNF-SAT

Formül, alt cümlelerin ∧'sidir; her alt cümle üç değişkenin (ya da değillerinin) ∨'sidir. Örnek: (x₁ ∨ ¬x₁ ∨ ¬x₂) ∧ (x₃ ∨ x₂ ∨ x₄) ∧ (¬x₁ ∨ ¬x₃ ∨ ¬x₄). CNF, “birleşimli normal biçim” (conjunctive normal form) demektir.

Kaba kuvvet çözümünde dikkat çekici bir verimlilik ayrıntısı vardır. İşlem ağacı yalnız bir kez kurulur. Her atamada ağacın yapısı aynı kalır ve yalnız yapraklar değişir. Ağaç her atamada baştan kurulsaydı sekiz kez malloc ve free zinciri çalışırdı. Defalarca yapılacak bir iş için bir kez hazırlanan veri yapısına ön hesaplama (precomputing) denir. Ön hesaplama, algoritmanın mertebesini değiştirmeyebilir ama sabit çarpanını çok küçültür.

Ön hesaplama metin aramada da kullanılır. Bir metinde bir sözcük ararken, sözcüğün kendi yapısı önceden incelenip bir tabloya yazılırsa arama sırasında geri dönmek gerekmez. Knuth–Morris–Pratt algoritması bu fikrin bilinen bir örneğidir. Algoritma analizi kitaplarındaki açgözlü algoritmalar (greedy algorithms), dal ve sınır (branch and bound) ve ön hesaplama konuları, kaba kuvvetten daha iyisini aramanın yollarını anlatır.

3.10n-vezir problemi

Permütasyon ve alt küme üretiminde her seçim geçerliydi; geri izleme yalnız seçimi geri almaktan ibaretti. n-vezir probleminde seçimlerin çoğu kuralları bozar ve budama gerçek bir kazanç sağlar.

3.10.1Problem ve gösterim

İki vezir aynı satırda duramayacağına göre n vezir n satıra birer birer dağılır. Bu gözlem gösterimi sadeleştirir: çözüm, n öğeli bir q dizisidir ve q[r], r. satırdaki vezirin sütun numarasıdır. Satır kuralı bu gösterimle kendiliğinden sağlanır. Sütun kuralı, q'daki değerlerin hepsinin farklı olmasıdır. Çapraz kuralı için bir sınama gerekir.

(i, q[i]) ve (r, c) karelerindeki iki vezir aynı çaprazdaysa satır farkı ile sütun farkı eşittir. Satırlar arasındaki uzaklık kadar sütunda da ilerlemek, 45 derecelik bir çizgide yürümektir. Yeni vezir her zaman daha aşağıdaki bir satıra konduğundan r > i'dir ve satır farkı r − i'dir. Sütun farkı ise iki yönde olabilir; mutlak değer alınır:

|q[i] − c| = r − i

Kaba kuvvet çözümünde her satırın veziri n sütundan birine konur ve nⁿ aday çıkar. n = 8 için bu 8⁸ = 16.777.216, yani yaklaşık 16,7 milyon adaydır. Sütun kuralını baştan uygulayıp yalnız permütasyonları denemek sayıyı 8! = 40.320'ye indirir. Geri izleme bundan da azını dener.

3.10.2uygun() ve yerlestir()

Geri izleme çözümü iki fonksiyondan oluşur. İlki, bir karenin önceki satırlardaki vezirlerle çakışıp çakışmadığını sınar:

int q[8];  /* q[r]: r. satirdaki vezirin sutunu */

int uygun(int r, int c) {
  int i;
  for (i = 0; i < r; i++)
    if (q[i] == c || abs(q[i] - c) == r - i)
      return 0;         /* ayni sutun ya da capraz */
  return 1;
}

q dizisi küresel (global) tanımlanmıştır; böylece iki fonksiyon da ona parametre almadan erişir. Dizinin boyu 8'dir, dolayısıyla kod en çok n = 8 için çalışır. uygun(r, c), r. satırın c. sütununa vezir konup konamayacağını söyler. Döngü yalnız 0 … r − 1 satırlarına bakar, çünkü alt satırlarda henüz vezir yoktur. Her önceki vezir için iki koşul sınanır: q[i] == c aynı sütunu, abs(q[i] - c) == r - i aynı çaprazı yakalar. Çakışma varsa fonksiyon hemen 0 döndürür. Döngü çakışma bulmadan biterse kare uygundur. abs fonksiyonu <stdlib.h> başlığındadır; bu başlık eklenmezse derleyici bildirilmemiş fonksiyon için uyarı ya da hata verir.

İkinci fonksiyon veziri satır satır yerleştirir:

int yerlestir(int r, int n) {
  int c;
  if (r == n) return 1;             /* cozum */
  for (c = 0; c < n; c++)
    if (uygun(r, c)) {
      q[r] = c;
      if (yerlestir(r + 1, n)) return 1;
    }
  return 0;                  /* geri don */
}

yerlestir(r, n), r. satırdan başlayarak kalan vezirleri yerleştirmeye çalışır. Başarırsa 1, başaramazsa 0 döndürür. r == n taban durumdur: bütün satırlar doldurulmuştur ve bir çözüm bulunmuştur. Taban durumda değilse döngü sütunları soldan sağa dener. Uygun bir sütun bulununca vezir oraya konur (q[r] = c) ve bir sonraki satır için fonksiyon kendini çağırır. Alt çağrı 1 döndürürse çözüm tamamlanmıştır ve 1 hemen yukarı iletilir. Alt çağrı 0 döndürürse bu yerleşim bir çıkmaza varmıştır; döngü sıradaki sütunla devam eder. Hiçbir sütun işe yaramazsa fonksiyon 0 döndürür ve bir üst satır kendi sıradaki sütununu dener.

Kodda seçimi geri alan açık bir satır yoktur. Bunun nedeni gösterimdir: q[r] bir sonraki denemede üzerine yazılır ve uygun yalnız r'den küçük satırlara bakar. Başarısız bir denemeden kalan değerler hiçbir zaman okunmaz. Geri alma işi, r'nin yığındaki çerçevelerde saklanmasıyla örtük olarak yapılır.

3.10.3Kod izleme: 4-vezir

yerlestir(0, 4) çağrısı Tablo 3.12'deki gibi ilerler. Kareler (satır, sütun) biçiminde yazılmıştır ve satırlar ile sütunlar 0'dan başlar.

İzlemenin ilk kısmı, sol üst köşeye konan vezirin çözüme götürmediğini gösterir. Adım 2'de ikinci satırın 0. sütunu birinci vezirle aynı sütunda, 1. sütunu aynı çaprazdadır; ilk uygun sütun 2'dir. Adım 3'te üçüncü satırın her sütunu tehdit altındadır: 0 ve 2 sütun kuralına, 1 ve 3 de (1, 2)'deki vezirin çaprazlarına takılır. Fonksiyon 0 döndürür ve ikinci satır sıradaki sütunu, 3'ü dener.

Adım 4–7 ikinci denemenin de çıkmaza vardığını gösterir. Dördüncü satırda hiçbir kare kalmaz, üçüncü satırın kalan sütunları da tehdit altındadır. Adım 8'de ikinci satır, son sütunu denemiş olduğundan 0 döndürür. Artık birinci satırın veziri yer değiştirmelidir. Adım 9'da vezir (0, 1)'e konur ve bu kez her satırda uygun bir kare bulunur. Adım 13'te r = 4 = n olur ve çözüm q = [1, 3, 0, 2] bulunur. Dönen 1, dört çerçeveden geçerek ilk çağırana ulaşır.

Tablodaki q[r] = c atamaları sayılırsa sekiz yerleştirme yapıldığı görülür: (0, 0), (1, 2), (1, 3), (2, 1), (0, 1), (1, 3), (2, 0), (3, 2). Kaba kuvvet 4⁴ = 256 adayı sınardı. Bu sayılar, yerlestir'e bir sayaç eklenerek program çalıştırılıp doğrulanmıştır.

3.10.4Budamanın kazancı

Geri izlemenin en kötü durum maliyeti için bir üst sınır kolayca bulunur. Sütun kuralı yüzünden r. satırda en çok n − r sütun aday olabilir; önceki vezirlerin sütunları kapalıdır. Çağrı ağacının birinci düzeyinde en çok n, ikinci düzeyinde en çok n(n − 1) düğüm vardır ve yaprak sayısı en çok n! olur. Maliyet için verilen O(n!) üst sınırı buradan gelir; her düğümde yapılan uygun denetimleri bu sınıra yalnız bir polinom çarpanı ekler. Bu kaba bir sınırdır: çapraz kuralı ağacın büyük kısmını erkenden budar ve gerçek maliyet n!'nin çok altında kalır. Yığın maliyeti derinlik kadar, O(n)'dir.

Tablo 3.13'teki değerler programla hesaplanmıştır. Yerleştirme sütunu, ilk çözüme kadar yapılan q[r] = c atamalarını sayar. Sekiz vezir için geri izleme yalnız 113 yerleştirmeyle bir çözüm bulur; kaba kuvvetin 16,7 milyon adayıyla karşılaştırınca fark çarpıcıdır. Çözüm sayısı sütunu, algoritma ilk çözümde durmayıp bütün çözümleri sayacak biçimde değiştirilerek bulunmuştur. 4 için 2, 8 için 92 çözüm vardır. Yerleştirme sayısı n ile düzenli büyümez: 5 ve 7 için ilk denemeler hemen başarılı olur, 6 için çok sayıda çıkmaza girilir. Geri izlemenin maliyeti girdinin yapısına sıkı sıkıya bağlıdır.

3.11At gezisi ve Warnsdorff kuralı

Geri izleme her zaman çözümü bulur, ama aday sayısı büyüdükçe yavaşlar. Kimi problemlerde iyi bir seçim kuralı, geri dönmeye hiç gerek bırakmadan çözüme götürür. At gezisi bu durumun klasik örneğidir.

3.11.1Problem

Tahtanın ortasındaki bir at sekiz kareye gidebilir. Kenarlarda ve köşelerde bu sayı azalır; köşedeki at yalnız iki kareye ulaşır. Hamleler, satır değişimi Δi ve sütun değişimi Δj olarak bir tabloda tutulur:

Tablo, hamleleri saat yönünde dolaşır: 0. hamle iki satır yukarı ve bir sütun sağa, 2. hamle bir satır aşağı ve iki sütun sağa götürür. Tabloyla çalışmak, sekiz ayrı if yazmak yerine tek bir döngüyle bütün hamleleri denemeyi sağlar. (i, j) karesinden k. hamle (i + Δi[k], j + Δj[k]) karesine gider; karenin tahta içinde ve henüz gezilmemiş olması gerekir.

3.11.2Geri izleme ve sezgisel yaklaşım

Geri izleme çözümü n-vezire benzer. At bir kareye konur ve sırayla her hamle denenir. Atın gidebileceği boş kare kalmamışsa ve bütün kareler gezilmemişse bir çıkmaz vardır; son hamle geri alınır ve sıradaki hamle denenir. Bu yöntem bir çözüm varsa onu her zaman bulur. Ama kaba kuvvet niteliğindedir. Her karede sekize kadar seçenek vardır. 8 × 8 tahtanın 64 karesinde yanlış bir erken seçim, çok sonra fark edilen bir çıkmaza yol açabilir. Algoritma o noktaya kadar kurduğu milyonlarca kısmi geziyi tek tek geri almak zorunda kalır.

Sezgisel kurallar günlük hayatta da kullanılır. Mayın tarlası oyununda oyuncu, açık karelerdeki sayılara bakarak en güvenli görünen kareyi seçer. Bu seçim çoğu zaman doğrudur, ama bazen şansa kalır. Sezgisel bir algoritma da benzer biçimde çalışır: hızlıdır ve genellikle başarılıdır, ama başarısız olduğu girdiler bulunabilir.

3.11.3Warnsdorff kuralı: 5×5 tahtada izleme

At gezisi için bilinen en eski sezgisel kural H. C. von Warnsdorff'un 1823'te önerdiği kuraldır. Kural, atın bir sonraki gideceği yerin, ilerleme sayısı sıfır olmayan ama en az olan kare olmasını söyler. Bir karenin ilerleme sayısı, o kareden doğrudan gidilebilecek boş kare sayısıdır.

Kuralın mantığı, ulaşılması zor kareleri önce tüketmektir. Köşe ve kenar kareleri az sayıda kareden ulaşılabilir. At bu karelere uğramadan uzaklaşırsa, geri dönebileceği yollar zamanla dolar ve kare ulaşılamaz hâle gelir. En az ilerleme sayılı kareye gitmek bu kareleri erkenden ziyaret eder ve çıkmazı sona bırakmaz. Ortadaki kareler ise çok yoldan ulaşılabildiği için sona kalsa da sorun çıkmaz.

5×5 tahtada sol üst köşeden, yani (0, 0) karesinden başlayan bir gezi izlenebilir. Eşitlik durumunda hamle tablosundaki sıra (0'dan 7'ye) belirleyicidir. Tablo 3.15 gezinin önemli adımlarını verir. Adaylar, atın o kareden gidebileceği boş karelerdir; yanlarındaki sayı ilerleme sayısıdır.

İkinci karede kuralın etkisi açıkça görülür. Beş aday arasından sağ üst köşe (0, 4) seçilir, çünkü oradan yalnız bir boş kareye gidilebilir. Köşe şimdi ziyaret edilmezse, ona ulaşan tek yol da dolduğunda köşe sonsuza dek ulaşılamaz kalırdı. Dördüncü karede aynı mantık sağ alt köşeyi, (4, 4)'ü seçtirir. Yirmi dördüncü karede tek aday kalır ve onun ilerleme sayısı 0'dır. Kuralın “sıfır olmayan” şartı burada uygulanmaz: bu kare tahtanın son boş karesidir ve gezi onunla tamamlanır.

Tamamlanmış gezide 25 kare, hiç geri dönmeden gezilmiştir. Ziyaret sırası satır satır şöyledir: 1 14 9 20 3 / 24 19 2 15 10 / 13 8 25 4 21 / 18 23 6 11 16 / 7 12 17 22 5. Köşeler 1, 3, 5 ve 7. adımlarda, yani gezinin başında tüketilmiştir; orta kare en sona kalmıştır. Bu gezi, kural küçük bir programla uygulanarak her adımın adayları ve ilerleme sayılarıyla birlikte üretilmiş ve sunumdaki değerlerle karşılaştırılmıştır.

Warnsdorff kuralının maliyeti çok düşüktür. n × n tahtada n² hamle yapılır. Her hamlede en çok 8 aday incelenir ve her adayın ilerleme sayısı en çok 8 komşuya bakılarak hesaplanır. Hamle başına iş sabittir (en çok 8 × 8 = 64 kare denetimi); toplam iş O(n²)'dir. Bellek, tahtanın kendisi için O(n²)'dir. Geri izleme ise en kötü durumda üstel sayıda kısmi gezi dener.

Kural her zaman başarılı olmaz. Eşitliklerin nasıl bozulduğuna ve başlangıç karesine bağlı olarak at bazen çıkmaza girer. Bu durumda Warnsdorff kuralı geri izlemeyle birleştirilebilir: adaylar ilerleme sayısına göre sıralanıp bu sırayla denenir, çıkmazda geri dönülür. Kural yalnız denemelerin sırasını belirlediği için çözüm garantisi korunur. Pratikte geri dönmeye çok nadiren gerek kalır.

3.12Karmaşıklık özeti

Bu notta incelenen algoritmaların zaman ve bellek maliyetleri Tablo 3.16'da bir arada verilmiştir. Bellek sütunu, çağrı yığınının ve algoritmanın kullandığı ek yapıların toplamıdır; girdinin kendisi sayılmamıştır.

Tablo iki gruba ayrılır. İlk üç satırdaki algoritmalar polinom zamanlıdır ve büyük girdilerde rahatça çalışır. Geri kalanların çoğu üstel ya da faktöriyel zamanlıdır. Hanoi, permütasyon ve alt küme üretiminde bu maliyet kaçınılmazdır, çünkü çıktının kendisi o boydadır. SAT ve n-vezirde ise çıktı küçüktür (bir atama ya da bir yerleşim), ama onu bulmak için bilinen en iyi genel yöntemler üstel zaman alır. Warnsdorff kuralı, üstel bir aramayı sezgisel bir seçimle polinom zamana indirmenin örneğidir; karşılığında çözüm garantisinden vazgeçer.

Yığın sütununda dikkat çeken bir düzen vardır: özyinelemeli algoritmaların hepsinde yığın maliyeti, özyineleme derinliğidir. Zaman üstel bile olsa derinlik çoğu zaman n'dir. Bu yüzden Hanoi ya da permütasyon gibi algoritmalar yığın taşmasıyla değil, zaman yetmezliğiyle sınırlanır.

3.13Sık yapılan hatalar

1. Taban durumu unutmak ya da ona hiç ulaşmayan bir adım yazmak. Çağrılar durmaz ve program yığın taşmasıyla çöker. Her özyinelemeli fonksiyonda, her çağrıda azalan bir ölçü ve o ölçünün en küçük değerini yakalayan bir taban durum bulunmalıdır.
2. Özyinelemeli çağrının sonucunu döndürmemek. binsearch(...) yazılıp dönen değer atılırsa fonksiyon doğru cevabı bulduğu hâlde yanlış değer döndürür. Kuyruk çağrısı return binsearch(...) biçiminde yazılmalıdır.
3. İkili aramayı sırasız dizide ya da bağlı listede kullanmak. Sırasız dizide yarıyı atma kararı yanlıştır ve var olan değer bulunamayabilir. Bağlı listede ortaya ulaşmak doğrusal zaman alır ve logaritmik kazanç kaybolur.
4. Bulunan öğenin değerini döndürmek. Değer, hata işareti −1 ile karışabilir ve konum bilgisi kaybolur. İkili arama indis döndürmelidir.
5. Geri izlemede seçimi geri almayı unutmak. Permütasyondaki ikinci SWAP ya da alt küme üretimindeki sec[i] = 0 yazılmazsa kardeş dallar bozuk bir başlangıç durumu görür. Bazı çözümler tekrar eder, bazıları hiç çıkmaz.
6. Üstel bir algoritmayı “makine hızlı” diye büyük n ile çalıştırmak. 64 diskli Hanoi yüz milyarlarca yıl, 20 öğeli permütasyon on yıllar sürer. Algoritma seçilmeden önce büyüme mertebesi hesaplanmalıdır.
7. Derin özyinelemenin yığın maliyetini hesaba katmamak. Derinliği n olan bir özyineleme, n yüz binler mertebesindeyse birkaç megabaytlık çağrı yığınını doldurur. Kuyruk özyinelemesi C'de güvence değildir; böyle durumlarda döngü tercih edilir.
8. Taşmayı gözden kaçırmak. long Windows'ta 32 bittir ve fakt(13) taşar. İkili aramada (left + right) / 2 çok büyük dizilerde taşabilir. İşaretli taşma tanımsız davranıştır ve sessizce yanlış sonuç verebilir.

3.14Özet

• Özyineleme: bir fonksiyonun kendini daha küçük bir girdiyle çağırmasıdır. Taban durum özyinelemesiz çözülen en küçük örnektir; özyinelemeli adım problemi küçültür ve her çağrıda taban duruma yaklaşır.
• Çağrı yığını: her çağrı, parametreleri, yerel değişkenleri ve dönüş adresini tutan bir yığın çerçevesi açar. Derinliği d olan özyineleme O(d) ek bellek kullanır; aynı değişkenin her çerçevede ayrı kopyası vardır.
• Özyineleme ve döngü: her özyineleme açık bir yığınla döngüye çevrilebilir. Özyineleme tanıma yakındır; döngü O(1) bellekle ve çağrı maliyeti olmadan çalışır.
• Kuyruk özyinelemesi: özyinelemeli çağrı son iştir; birikimli parametreyle elde edilir ve derleyici bunu atlamaya çevirebilir. C standardı bu eniyilemeyi garanti etmez.
• İkili arama: sıralı dizide aralığı her turda yarıya indirir ve en çok ⌊log₂ n⌋ + 1 tur döner: O(log n). İndis döndürür, −1 “yok” demektir. Döngüsel sürüm O(1), özyinelemeli sürüm O(log n) ek bellek kullanır.
• Hanoi kuleleri: h(n) = 2h(n − 1) + 1 bağıntısının çözümü 2ⁿ − 1'dir ve bu sayı en iyisidir. Çağrı ağacı yığının tarihçesidir; hamleler kök ortada gezinmeyle sıralanır.
• Permütasyon: takas, özyineleme ve geri takasla n! diziliş üretilir. Çağrı sayısı yaklaşık e · n!, zaman Θ(n · n!)'dir.
• Geri izleme: kısmi çözüm adım adım kurulur, bir kural bozulunca dal budanır ve son seçim geri alınır. Alt küme üretimi, SAT ve n-vezir bu yöntemle çözülür.
• SAT: bir mantık formülünü doğru yapan atama aranır. Kaba kuvvet 2ⁿ atamayı dener; formül ağacı bir kez kurulur ve kök sonda gezinmeyle değerlendirilir. Problem NP-tamdır.
• Sezgisel yaklaşım: Warnsdorff kuralı atı her adımda en az ilerleme sayılı kareye götürür ve gezi çoğunlukla hiç geri dönmeden O(n²) zamanda tamamlanır. Daha iyi bir çözüm aramaktan vazgeçilmez.

3.15Kavram listesi

• özyineleme recursion
• özyinelemeli recursive
• taban durum base case
• çağrı yığını call stack
• yığın çerçevesi stack frame
• yığın taşması stack overflow
• kuyruk özyinelemesi tail recursion
• ikili arama binary search
• yineleme bağıntısı recurrence relation
• permütasyon permutation
• takas swap
• kaba kuvvet brute force
• geri izleme backtracking
• alt küme subset
• sağlanabilirlik satisfiability (SAT)
• kök sonda postorder
• n-vezir problemi n-queens problem
• sezgisel yaklaşım heuristic

3.16Kendini Dene

1. fakt_k(5, 1) çağrısı hangi çağrıları yapar ve ne döndürür? Kuyruk çağrısı eniyilemesi kapalıyken yığında en çok kaç fakt_k çerçevesi bulunur?

   Cevap

   Çağrılar fakt_k(5, 1), fakt_k(4, 5), fakt_k(3, 20), fakt_k(2, 60), fakt_k(1, 120) biçimindedir; son çağrı taban durumdur ve 120 döner. 120 hiçbir işlem görmeden yukarı iletilir. Eniyileme kapalıyken beş çerçeve aynı anda yığındadır; açıkken tek çerçeve yeter.

2. Test dizisinde ({4, 13, 18, 19, 24, 27, 33, 36, 39, 40}) döngüsel binsearch 39'u ararken hangi orta indisleri dener ve kaç tur döner?

   Cevap

   Orta indisler 4 (24 < 39, left = 5), 7 (36 < 39, left = 8) ve 8'dir (list[8] = 39). Fonksiyon üç turda 8 döndürür.

3. Özyinelemeli binsearch(list, 5, 0, 9) aynı dizide kaç çağrı yapar? Hangi aralıklarla çağrılır ve sonuç nedir?

   Cevap

   Dört çağrı yapılır: [0, 9] (orta 24), [0, 3] (orta 13), [0, 0] (orta 4) ve [1, 0]. Son aralık boştur ve −1 döner; bu değer üç çerçeveden geçerek iletilir. En derin anda yığında dört binsearch çerçevesi vardır.

4. hanoi(5, "A", "B", "C") kaç satır yazar, fonksiyon kendini toplam kaç kez çağırır (ilk çağrı dahil) ve yığın en çok kaç hanoi çerçevesi derinleşir?

   Cevap

   2⁵ − 1 = 31 satır yazılır. Her çağrı tam bir printf yaptığından çağrı sayısı da 31'dir. Derinlik disk sayısı kadardır: 5 çerçeve.

5. char s[] = "abcd"; için perm(s, 0, 4) çıktısının 7–10. satırları nelerdir? Toplam kaç çağrı yapılır?

   Cevap

   İlk altı satır a ile başlar (abcd, abdc, acbd, acdb, adcb, adbc). Sonra dizi bacd olur ve 7–10. satırlar bacd, badc, bcad, bcda'dır. Çağrı sayısı 1 + 4 + 12 + 24 + 24 = 65'tir.

6. altkume("abcd", 4, 0, sec) kaç satır yazar ve beşinci satır nedir? Fonksiyon toplam kaç kez çağrılır?

   Cevap

   2⁴ = 16 satır yazılır. Sıra {abcd}, {abc}, {abd}, {ab}, {acd}, … diye ilerler; beşinci satır {acd}'dir. Çağrı ağacı 4 düzeyli tam ikili ağaçtır: 2⁵ − 1 = 31 çağrı.

7. (x₁ ∨ ¬x₂) ∧ x₃ formülünü sağlayan atamalar (x₁x₂x₃ sırasıyla) hangileridir? Formül ağacında kaç düğüm vardır?

   Cevap

   x₃ = 1 olmalı ve x₁ = 1 ya da x₂ = 0 olmalıdır: 001, 101 ve 111. Ağaçta altı düğüm vardır: kökte ∧, onun sol çocuğu ∨, ∨'nin çocukları x₁ ve ¬, ¬'nin sağ çocuğu x₂, kökün sağ çocuğu x₃.

8. yerlestir(0, 6) çağrısının bulduğu ilk çözüm nedir? 6×6 tahtada toplam kaç çözüm vardır?

   Cevap

   İlk çözüm q = [1, 3, 5, 0, 2, 4]'tür; ona ulaşılana kadar 31 yerleştirme yapılır. 6×6 tahtada 4 çözüm vardır; 5×5'te 10 çözüm olmasına karşın 6×6'da daha azdır.

9. Windows'ta fakt(13) neden yanlış sonuç verebilir? 64 bit Linux'ta fakt hangi n'ye kadar doğru çalışır?

   Cevap

   Windows'ta long 32 bittir ve en büyük değeri 2.147.483.647'dir. 13! = 6.227.020.800 bu sınırı aşar; işaretli taşma tanımsız davranıştır. 64 bit Linux'ta long 64 bittir; 20! ≈ 2,43·10¹⁸ sığar, 21! ≈ 5,1·10¹⁹ sığmaz. Doğru sonuç n ≤ 20 için alınır.

10. Bir dizinin en büyük öğesini bulan özyinelemeli fonksiyon nasıl yazılır? Yığın derinliği ne olur?

    Cevap

    Taban durum n = 1'dir ve tek öğe döner; özyinelemeli adım ilk n − 1 öğenin en büyüğünü bulup son öğeyle karşılaştırır:

    int en_buyuk(int a[], int n) {
      int m;
      if (n == 1) return a[0];        /* taban durum */
      m = en_buyuk(a, n - 1);         /* ilk n-1 ogenin en buyugu */
      return a[n - 1] > m ? a[n - 1] : m;
    }

    Her çağrı n'yi bir azaltır; derinlik n, yığın maliyeti O(n)'dir. Test dizisinde fonksiyon 40 döndürür. Çağrı kuyruk çağrısı değildir, çünkü dönüşten sonra bir karşılaştırma yapılır.

3.17İleri okuma

• E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C (2. baskı), Kesim 1.2: bu notun ikili arama, permütasyon ve SAT örneklerinin kaynağıdır; özyinelemeli algoritmaları ve analizlerini aynı C diliyle verir.
• R. Sedgewick, Algorithms in C, Bölüm 5: özyinelemeyi, böl ve fethet yöntemini ve çağrı ağaçlarını ayrıntılı çizimlerle anlatır.
• T. H. Cormen ve diğerleri, Introduction to Algorithms (3. baskı), Bölüm 4 ve 34: yineleme bağıntılarını çözme yöntemlerini ve NP-tamlık kuramını, SAT'ın bu kuramdaki yerini verir.
• N. Wirth, Algorithms + Data Structures = Programs (1976): geri izlemenin genel kalıbını Pascal ile kuran ve sekiz vezir gibi problemlerle örnekleyen klasik bir ders kitabıdır.

3.18Kaynaklar

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3. baskı, MIT Press, 2009 (Bölüm 4: yineleme bağıntıları; Bölüm 34: NP-tamlık, SAT).
2. E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2. baskı, Silicon Press, 2008 (Bölüm 1.2: özyinelemeli algoritmalar).
3. R. Sedgewick, Algorithms in C, Addison-Wesley (Bölüm 5: özyineleme).
4. N. Wirth, Algorithms + Data Structures = Programs, Prentice-Hall, 1976.

İlgili sayfalar: Bölüm 3 sunumu · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.