Bölüm 4: Özyineleme

4.1Özyineleme nedir?

Bir metot başka metotları çağırabilir; bunu programlamaya başlarken öğreniriz. main, System.out.println'i çağırır; bir sıralama metodu, iki öğenin yerini değiştiren yardımcı bir metodu çağırır. Özyinelemede çağrılan metot, çağıranın kendisidir. Böyle bir metot neden sonsuza kadar dönüp durmaz, nasıl tasarlanır ve satır satır nasıl çalışır? Kesimin konusu bu üç sorudur.

4.1.1Günlük hayattan bir örnek

Bir sinema gişesinin önünde uzun bir kuyruk var. Kuyrukta kaçıncı sırada olduğumuzu öğrenmek istiyoruz. Yerimizi bırakıp en öne yürüyemiyoruz; yürürsek sıramızı kaybederiz. Görebildiğimiz tek kişi hemen önümüzdeki kişidir.

Bu durumda şöyle bir yol izlenebilir. Önümüzdekine “Sen kaçıncısın?” diye sorarız. O da kendi sırasını bilmiyorsa aynı soruyu kendi önündekine sorar. Soru böylece kişiden kişiye öne doğru ilerler. En öndeki kişinin önünde kimse yoktur; o hiç düşünmeden “1” der. Cevap bu kez geriye doğru yol alır. En öndekinin arkasındaki kişi “önümdeki 1. ise ben 2.'yim” der ve bunu arkasına iletir. Herkes duyduğu sayıya 1 ekleyip arkadakine söyler. Cevap bize ulaştığında sıramızı öğrenmiş oluruz.

Şekil 4.1'deki süreçte üç ayrı parça vardır:

• Aynı soru, daha kısa kuyruk. Her kişi önündekine aynı soruyu sorar. Ama soru her seferinde bir kişi daha kısa bir kuyruk için sorulur. Kimse farklı bir iş yapmaz; herkes aynı kuralı uygular.
• Durma noktası. En öndeki kişi soruyu başkasına aktarmadan cevaplar. Sorular burada durur. Böyle bir kişi olmasaydı soru sonsuza kadar öne aktarılırdı.
• Geri dönüş. Cevap geri gelirken her kişi kendi payını, yani 1'i ekler. Asıl hesap bu dönüş yolunda yapılır.

Özyinelemeli bir metot da tam böyle çalışır. Kendini daha küçük bir girdiyle çağırır. En küçük girdide cevabı doğrudan verir. Dönüşte küçük problemin cevabını kullanarak kendi cevabını kurar. Kuyruktaki her kişi, metodun bir çağrısına karşılık gelir. Her kişinin kendi aklında tuttuğu bir bilgi vardır (“arkamdakine cevap vereceğim”); metot çağrılarında da her çağrının kendi değişkenleri vardır.

4.1.2Taban durum ve özyinelemeli adım

Özyinelemenin en bilinen örneği faktöriyeldir. n!, 1'den n'ye kadar tam sayıların çarpımıdır: 4! = 4 · 3 · 2 · 1 = 24. Bu tanımda bir düzen göze çarpar. 4!'ün içinde 3 · 2 · 1 = 3! zaten vardır. Dolayısıyla 4! = 4 · 3! yazılabilir. Aynı gözlem her n > 1 için geçerlidir. Faktöriyel bu yüzden kendisi cinsinden tanımlanabilir:

n! = 1 (n ≤ 1 ise)  ·  n! = n · (n − 1)! (n > 1 ise)

Tanımın iki satırı iki farklı iş görür. İlk satır, en küçük girdiler için cevabı başka hiçbir şeye başvurmadan verir. İkinci satır, büyük bir girdinin cevabını bir küçüğünün cevabından kurar. 4!'ü bulmak için ikinci satır üç kez uygulanır, sonra birinci satır devreye girer: 4! = 4 · 3! = 4 · 3 · 2! = 4 · 3 · 2 · 1! = 4 · 3 · 2 · 1 = 24.

Faktöriyel tanımı Java'ya neredeyse kelimesi kelimesine çevrilir:

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

// main içinde:
System.out.println(faktoriyel(4));

İkinci satırdaki if (n <= 1) koşulu taban durumu yakalar ve 1 döndürür. Son return satırı özyinelemeli adımdır: faktoriyel(n - 1) çağrısı daha küçük bir girdiyle aynı metodu çalıştırır, dönen değer n ile çarpılır. main içindeki satır faktoriyel(4)'ü çağırır ve 24 yazdırır.

Taban durum neden bu kadar önemlidir? Metot her çağrıda kendini yeniden çağırıyorsa bir yerde bu zincirin kopması gerekir. Taban durum o kopma noktasıdır. Taban durum olmazsa çağrılar hiç bitmez. Her çağrı bellekte biraz yer tuttuğu için bellek bir noktada dolar ve Java programı StackOverflowError hatasıyla durdurur. Bu hatanın nereden geldiği 4.2.3'te ayrıntılı anlatılır.

Şekil 4.2 özyinelemenin iki yönlü hareketini gösterir. İniş sırasında hiçbir çarpma yapılmaz; her çağrı yalnızca kendi n'sini aklında tutup bir alttakini bekler. Çarpmalar çıkış sırasında yapılır: önce 2 · 1 = 2, sonra 3 · 2 = 6, en son 4 · 6 = 24.

Bir ayrıntıyı atlamamak gerekir. Aynı anda dört ayrı faktoriyel çağrısı bellekte durur ve her birinin kendi n değişkeni vardır: 4, 3, 2 ve 1. Bu dört n birbirine karışmaz. faktoriyel(1) çalışırken n = 1'dir; ama faktoriyel(4)'ün n'si hâlâ 4'tür ve sırası gelince 4 ile çarpma yapılır. Her çağrı bellekte kendine ait bir alan açar. Bu alana çerçeve denir; çerçeveler 4.2'nin konusudur.

4.1.3Özyinelemeli düşünmek

Özyinelemeli bir metot yazarken bütün çağrı zincirini kafada canlandırmaya çalışmak yorucudur ve çoğu zaman gereksizdir. Bunun yerine üç soru sorulur:

1. Taban durum: En küçük girdi hangisidir ve cevabı nedir? Özyineleme burada durur.
2. Küçültme: Problem, aynı türden daha küçük bir probleme nasıl indirgenir? Küçültme çoğunlukla n − 1, n / 2 ya da bir indisi i + 1 yapmak biçimindedir.
3. Birleştirme: Küçük problemin cevabından büyük problemin cevabı nasıl kurulur?

Üçüncü soru cevaplanırken işimizi kolaylaştıran bir kabul vardır: küçük problemin doğru çözüldüğü kabul edilir. faktoriyel(n)'i yazarken faktoriyel(n - 1)'in nasıl çalıştığı düşünülmez; onun (n − 1)! değerini doğru döndürdüğü varsayılır ve yalnızca son adım düşünülür: “(n − 1)! elimdeyse n!'yi nasıl bulurum? n ile çarparım.”

Bu varsayım bir hile değildir; matematikteki tümevarım ilkesinin aynısıdır. Tümevarımla bir önermenin her doğal sayı için doğru olduğunu göstermek için iki şey yeterlidir. Önerme en küçük sayı için doğrudur. Önerme n − 1 için doğruysa n için de doğrudur. Bu ikisi gösterilince önerme 1 için, dolayısıyla 2 için, dolayısıyla 3 için doğru olur ve zincir hiç kopmaz. Özyinelemeli metotta da aynıdır: taban durum doğru cevabı veriyorsa ve her adım, küçük cevap doğruysa büyük cevabı doğru kuruyorsa, metot her girdi için doğru çalışır.

Bir koşul daha vardır: her özyinelemeli çağrı girdiyi taban duruma yaklaştırmalıdır. Tümevarım zinciri ancak her adım bir öncekine bağlanıyorsa işler. Girdi küçülmüyorsa ya da taban durumu atlayıp öteye geçiyorsa zincirin başı hiç gelmez.

Bu üç soruyu basit bir örnekle cevaplayalım. geriSay(n) metodu, n'den 1'e kadar sayıları birer satıra yazsın, en sonda da “Bitti” yazsın.

Bu üç cevap doğrudan koda dönüşür:

void geriSay(int n) {
  if (n == 0) {     // taban durum
    System.out.println("Bitti");
    return;
  }
  System.out.println(n);
  geriSay(n - 1);   // özyinelemeli adım
}
geriSay(3);         // main içinde

Kodun yapısı, tasarımdaki üç parçayı tek tek yansıtır. 2–5. satırlar taban durumdur: n == 0 ise “Bitti” yazılır ve return ile metottan çıkılır. return burada önemlidir; olmasaydı akış 6. satıra geçer, 0 yazdırılır ve geriSay(-1) çağrılırdı. 6. satır n'yi yazar. 7. satır özyinelemeli adımdır ve daha küçük problemi çözer.

4.1.4Kod izleme: geriSay(3)

Özyinelemeyi anlamanın en sağlam yolu, küçük bir girdiyle kodu satır satır izlemektir. main, geriSay(3)'ü çağırıyor. İzlemede her adımda hangi çağrının çalıştığı, hangilerinin beklediği ve ekrana ne yazıldığı not edilir.

Tabloda gS, geriSay'in kısaltmasıdır. Çağrılar sütunu, özyinelemenin bellekteki izini gösterir. Sütun 2–5. adımlarda uzar, 6–9. adımlarda kısalır. En uzun hâlinde main ile birlikte 5 çağrı aynı anda bellektedir. Toplam 4 geriSay çağrısı yapılmıştır: n = 3, 2, 1, 0.

Dönüş yolunda (6–9. adımlar) ekrana hiçbir şey yazılmaz. Her çağrı 7. satırdaki özyinelemeli çağrıdan döndüğünde metodun sonuna gelmiştir; yapacak işi kalmamıştır. Bütün yazdırmalar iniş yolunda yapılır. Bu durum, yazdırma satırının çağrıdan önce gelmesinin sonucudur. Satırların yeri değişirse çıktı da değişir.

4.1.5İş çağrıdan önce mi, sonra mı?

Özyinelemeli bir metotta bir işin özyinelemeli çağrıdan önce mi, sonra mı yapıldığı sonucu doğrudan belirler. Bunu iki kısa metotla görelim. İkisi de taban durumda hiçbir şey yapmaz; tek fark yazdırma satırının yeridir.

void geriSay2(int n) {
  if (n == 0) return;
  System.out.print(n + " ");
  geriSay2(n - 1);     // sonra çağrı
}

void ileriSay(int n) {
  if (n == 0) return;
  ileriSay(n - 1);     // önce çağrı
  System.out.print(n + " ");
}

geriSay2(3) çıktısı 3 2 1'dir. Yazdırma çağrıdan önce olduğu için her çağrı önce kendi sayısını yazar, sonra daha küçük problemi çözmeye geçer. Yazdırmalar çağrılar inerken yapılır.

ileriSay(3) çıktısı ise 1 2 3'tür. Burada her çağrı önce özyinelemeli çağrıyı yapar ve onun bitmesini bekler. ileriSay(3), 3'ü yazmadan önce ileriSay(2)'nin bitmesini bekler. ileriSay(2) de 2'yi yazmadan önce ileriSay(1)'i bekler. ileriSay(1), ileriSay(0)'ı çağırır; o taban durumdur ve hemen döner. İlk yazdırmayı bu yüzden ileriSay(1) yapar: 1. Sonra ileriSay(2) kaldığı yerden devam eder ve 2'yi yazar. En son ileriSay(3) 3'ü yazar. Yazdırmalar çağrılar dönerken yapılır.

İlk biten çağrı, en son başlayan çağrıdır. Bu yüzden çağrıdan sonra yapılan işler, çağrıların başlama sırasının tersiyle yapılır. Çağrıdan sonra kalan iş kaybolmaz: çağrının bilgileri bellekte bekler ve sırası gelince bu iş yapılır. Bu gözlem bölüm boyunca birçok kez işe yarar. Tek yönlü bir bağlı listeyi sondan başa yazdırmak (4.8.3) ve Hanoi kulelerinde ikinci yarıyı taşımak (4.5.3) bu sayede mümkün olur.

4.2Çağrı yığını

Önceki kesimde aynı metodun birden çok çağrısının bellekte aynı anda durduğunu ve her birinin kendi değişkenlerini taşıdığını gördük. Java bu çağrıları nerede ve hangi düzenle tutar? Bu düzen anlaşılınca özyinelemeli bir metodun hem çıktısı hem de bellek maliyeti kolayca bulunur.

4.2.1Çerçeveler ve çağrı yığını

Bir metot çağrıldığında Java, o çağrı için bellekte küçük bir alan ayırır. Bu alanda üç bilgi bulunur: metodun parametreleri, metodun yerel değişkenleri ve metot bittiğinde programın nereden devam edeceği. Son bilgiye dönüş adresi denir. Örneğin faktoriyel(3), faktoriyel(2)'yi çağırdığında dönüş adresi “n * … çarpmasının yapılacağı yer”dir.

Çağrı yığını adını, yığın veri yapısının kuralına uymasından alır: son eklenen ilk çıkar. Bu kurala LIFO (Last-In, First-Out: son giren ilk çıkar) denir. Metot çağrılarının doğası da böyledir. main bir f metodunu, f de g'yi çağırırsa önce g biter, sonra f, en son main. En son başlayan çağrı ilk biter.

Çağrı yığınının üç özelliği özyinelemeyi anlamak için yeterlidir:

• Yalnız en üstteki çerçeve çalışır. Alttaki çerçeveler askıdadır; her biri, hemen üstündeki çağrının sonucunu bekler.
• Aynı metodun birden çok çerçevesi aynı anda yığında bulunabilir. Özyinelemede durum tam budur. Her çerçevenin n'si ayrıdır.
• Bir çağrı bitince çerçevesi silinir. Dönüş değeri, artık en üstte olan çağıran çerçeveye verilir ve o çerçeve dönüş adresinden devam eder.

Şekil 4.4, özyinelemenin bellek maliyetini de açıklar. Yığında aynı anda dört çerçeve vardır; faktoriyel(n) için bu sayı n + 1 olur (main dahil). Her çerçeve sabit büyüklükte yer kapladığından bellek kullanımı n ile doğru orantılı büyür: O(n).

Bu gözlem genel bir kurala dönüşür. Özyinelemeli bir metodun bellek maliyeti, yapılan toplam çağrı sayısıyla değil, yığında aynı anda bulunan en çok çerçeve sayısıyla belirlenir. Bu sayı, en derin çağrı zincirinin uzunluğudur. Toplam çağrı sayısı ile en derin zincir, ikili özyinelemede birbirinden çok farklıdır; bu fark 4.6.5'te ayrıntılı işlenir.

4.2.2Kod izleme: faktoriyel(4)

4.1.2'deki faktoriyel metodunu faktoriyel(4) çağrısıyla, çağrı yığınının her adımdaki durumuna bakarak izleyelim. Kod şöyledir:

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

// main içinde:
System.out.println(faktoriyel(4));

Her çağrıda yalnızca iki satır önemlidir. 2. satırdaki karşılaştırma taban durumu ayırır. 4. satır ise önce faktoriyel(n - 1)'i çağırır, dönen değeri n ile çarpar ve sonucu döndürür. Çarpma, çağrı dönmeden yapılamaz. Çağrı yapılırken çerçeve bu çarpmayı “yarım kalmış iş” olarak saklar.

Tablodaki 2–8. adımlar iniş evresidir. Her adımda yığına bir çerçeve eklenir; hiçbir çarpma yapılmaz. 9. adımda taban duruma ulaşılır ve ilk somut değer, 1, üretilir. 10–13. adımlar dönüş evresidir. Her adımda bir çerçeve yığından çıkar ve hemen altındaki çerçeve yarım kalan çarpmasını tamamlar. Yığının bu biçimde geriye doğru boşalmasına çözülme (unwinding) de denir.

Maliyeti bu izlemeden okumak kolaydır. Toplam 4 çağrı yapılmıştır. Her çağrı sabit miktarda iş yapar: bir karşılaştırma, en çok bir çarpma ve bir dönüş. Zaman bu yüzden O(n)'dir. Yığın en derin anda 4 faktoriyel çerçevesi ve main içerir; bellek de O(n)'dir. Aynı çarpımı bir döngü O(1) bellekle yapar. Özyinelemeli sürüm bu ek belleği, tanıma birebir uyan kısa bir kod için öder.

4.2.3Yığın taşması

Çağrı yığını sınırsız değildir. JVM (Java Virtual Machine, Java sanal makinesi) her iş parçacığı için yığına sabit büyüklükte bir bellek ayırır. Bu büyüklük JVM'e ve işletim sistemine göre değişir ve JVM'in -Xss seçeneğiyle ayarlanabilir. Her çerçeve bu alandan biraz yer kaplar. Varsayılan ayarlarla özyineleme derinliği genellikle birkaç bin ile birkaç on bin çağrıyla sınırlıdır.

Aşağıdaki metot 1'den n'ye kadar sayıları toplar:

long topla(int n) {        // 1 + 2 + … + n
  if (n == 0) return 0;
  return n + topla(n - 1);
}
// main içinde:
System.out.println(topla(10_000));   // 50005000
System.out.println(topla(1_000_000)); // hata

topla(10_000) sorunsuz çalışır ve 50005000 yazar. Yığında aynı anda 10.001 topla çerçevesi bulunur; bu, varsayılan yığına sığar. topla(1_000_000) ise taban duruma ulaşmadan yığını doldurur. Bir milyon çerçeve için yer yoktur. Java bu durumda programı şu hatayla durdurur:

Exception in thread "main"
  java.lang.StackOverflowError
    at Ornek.topla(Ornek.java:3)
    at Ornek.topla(Ornek.java:3)
    …

Hata mesajının altındaki satırlar, hata anındaki çağrı yığınının dökümüdür. Aynı satırın (Ornek.topla(Ornek.java:3)) binlerce kez tekrarlanması, sorunun özyinelemeden geldiğini hemen gösterir. Bu döküme yığın izi (stack trace) denir.

Bir ölçüm fikir verir. Hiçbir iş yapmadan yalnız kendini çağıran bir metot, varsayılan ayarlarla yaklaşık 21.800 derinliğe inebildi. Çerçevesi biraz daha büyük olan topla için sınır daha düşüktü. Kesin değerin önemi yoktur ve makineden makineye değişir. Önemli olan sınırın var olması ve büyüklük derecesidir: on binler mertebesinde bir derinlik çoğu zaman sorun çıkarmaz, milyonlar mertebesinde bir derinlik ise neredeyse her zaman taşar.

Aynı toplam, özyinelemeye hiç gerek kalmadan hesaplanabilir. Bir döngü O(n) zaman ve O(1) bellek kullanır. Daha da iyisi, 1 + 2 + … + n = n(n + 1)/2 formülü sonucu O(1) zamanda verir. n = 1.000.000 için bu 500.000.500.000'dir; sonuç int'e sığmadığı için metodun long döndürmesi doğru bir seçimdir.

4.2.4Taban durumu unutmak

Yığın taşmasının en sık nedeni çok büyük bir girdi değil, hatalı yazılmış bir taban durumdur. Üç tipik hata vardır. Üçünün de sonucu aynıdır, ama nedenleri farklıdır.

1. Taban durum yok.

int f(int n) {
  return n * f(n - 1);
}

Metot her çağrıda kendini yeniden çağırır. f(3) için girdiler 3, 2, 1, 0, −1, −2, … diye sürer. Hiçbir çağrı geri dönmez; yığın dolar.

2. Taban duruma ulaşılamıyor.

if (n == 1) return 1;
return n * f(n - 1);

Burada taban durum vardır, ama yalnız n = 1'i yakalar. Metot f(0) ile çağrılırsa girdiler 0, −1, −2, … diye azalır ve n hiçbir zaman 1 olmaz. Koşulu n <= 1 yapmak bu girdiyi de yakalar: f(0) hemen 1 döndürür. Benzer bir durum, girdinin her çağrıda 2 azaldığı metotlarda da görülür. n * f(n - 2) biçimindeki bir metot n == 1 taban durumuyla tek sayılarda durur, çift sayılarda 2, 0, −2, … diye sürer ve taşar.

3. Problem küçülmüyor.

if (n <= 1) return 1;
return n * f(n);

Bu kez taban durum doğrudur, ama özyinelemeli adım girdiyi küçültmez: f(n), yine f(n)'yi çağırır. f(1) doğru cevap verir; f(2) ise sonsuza kadar f(2)'yi çağırır. Taban durum vardır ama ona hiç yaklaşılmaz.

Bu üç hatadan çıkan kural şudur: her olası girdi, 0 ve negatif değerler dahil, sonlu sayıda adımda bir taban duruma ulaşmalıdır. Bir özyinelemeli metot yazıldıktan sonra iki soru sorulur. Hangi girdiler doğrudan taban durumda biter? Öteki her girdi, her çağrıda bunlardan birine yaklaşıyor mu? İki sorunun cevabı da “evet” değilse metot bazı girdilerde taşar.

4.3Doğrusal özyineleme

Şimdiye kadarki örneklerin hepsinde her çağrı en çok bir özyinelemeli çağrı yaptı. Bu, özyinelemenin en sade türüdür. Adını çağrıların oluşturduğu biçimden alır: çağrılar dallanmayan, düz bir zincir oluşturur. Kesimin konusu aynı türden üç problemdir: dizinin toplamı, dizinin tersine çevrilmesi ve üs alma. Son örnek, zincirin uzunluğunu kısaltmanın maliyeti nasıl değiştirdiğini gösterir.

4.3.1Tanım ve dizinin toplamı

faktoriyel, geriSay ve topla doğrusal özyinelemenin örnekleridir. Dizinin toplamı, diziyi tersine çevirme, üs alma ve bağlı listenin uzunluğu da bu türdendir.

Bir tamsayı dizisindeki öğelerin toplamını özyinelemeyle bulalım. Özyinelemeli düşünmenin üç sorusu (4.1.3) burada da yol gösterir. Ama önce problemi küçültülebilir bir biçimde yazmak gerekir. “Dizinin toplamı” yerine “dizinin ilk n öğesinin toplamı” diye düşünülürse n küçültülebilecek bir parametre olur.

• Taban durum: n = 0 ise parça boştur; boş parçanın toplamı 0'dır.
• Küçültme: İlk n öğenin toplamı, ilk n − 1 öğenin toplamına dayandırılır.
• Birleştirme: İlk n − 1 öğenin toplamına son öğe a[n - 1] eklenir.

Dizi indisleri 0'dan başladığı için ilk n öğe a[0], …, a[n - 1]'dir; sondaki öğe a[n] değil a[n - 1]'dir. Kod şöyledir:

int toplam(int[] a, int n) {   // ilk n öğenin toplamı
  if (n == 0)
    return 0;                   // taban durum
  return toplam(a, n - 1) + a[n - 1];
}

Metodun ikinci parametresi, dizinin hangi parçasıyla ilgilenildiğini söyler. Dizinin kendisi hiçbir çağrıda değişmez ve kopyalanmaz. Java'da diziler referansla geçirilir: her çerçevede a, aynı dizinin adresini tutar. Böylece her çağrı yalnız bir referans ve bir tamsayı taşır. Bütün dizinin toplamı için ilk çağrı toplam(a, a.length) biçiminde yapılır.

Şekil 4.6 özyinelemeli düşünmenin özünü gösterir. toplam(a, 4)'ü yazan kişinin toplam(a, 3)'ün 13'ü nasıl bulduğunu bilmesi gerekmez. 13'ün doğru olduğunu kabul eder ve yalnızca son öğeyi ekler.

4.3.2Kod izleme: toplam(a, 4)

int toplam(int[] a, int n) {   // ilk n öğenin toplamı
  if (n == 0)
    return 0;                   // taban durum
  return toplam(a, n - 1) + a[n - 1];
}
// main içinde:
int[] a = {4, 3, 6, 2};
System.out.println(toplam(a, 4));

main, a = {4, 3, 6, 2} dizisi için toplam(a, 4)'ü çağırıyor. Her çağrı önce bir küçük parçanın toplamını ister; kendi öğesini toplamaya eklemeyi dönüşe bırakır.

5. adımda yığın en derindedir: main ve 5 toplam çerçevesi. Toplamalar dönüş yolunda, dizinin başından sonuna doğru yapılır: önce a[0], en son a[3]. Bunun nedeni, toplama işleminin özyinelemeli çağrıdan sonra yapılmasıdır; 4.1.5'teki ileriSay ile aynı durumdur.

Maliyet: n öğeli parça için n + 1 çağrı yapılır (n, n − 1, …, 0). Her çağrı bir karşılaştırma, bir toplama ve bir dizi erişimi yapar; zaman O(n)'dir. Yığın en derin anda n + 1 çerçeve (ve main) içerir; bellek de O(n)'dir.

Aynı kalıp dizinin başka özelliklerine de uygulanır. Örneğin dizinin en büyük öğesi de ilk n öğe üzerinden düşünülebilir. Taban durum n = 1'dir: tek öğeli parçanın en büyüğü a[0]'dır (boş parçanın en büyüğü tanımsızdır). Özyinelemeli adım, ilk n − 1 öğenin en büyüğünü son öğeyle karşılaştırır: Math.max(enBuyuk(a, n - 1), a[n - 1]). Maliyet yine O(n) zaman ve O(n) yığındır.

4.3.3Diziyi tersine çevirme

Bir diziyi yerinde, yani ikinci bir dizi kullanmadan, tersine çevirmek isteyelim. Fikir şudur: dizinin iki ucundaki öğelerin yeri değiştirilir, sonra aradaki parça aynı yöntemle tersine çevrilir. Aradaki parça, iki öğe kısa bir dizidir; problem böylece küçülür.

Bu kez parça, başlangıç ve bitiş indisleriyle verilir: a[i..j], i'den j'ye kadar (ikisi dahil) öğeleri gösterir. İlk çağrı bütün dizi için yapılır: ters(a, 0, n - 1).

• Taban durum: i >= j ise parçada 0 ya da 1 öğe kalmıştır. Tek öğeli ya da boş bir parça zaten kendi tersidir; yapılacak iş yoktur.
• Küçültme ve birleştirme: a[i] ile a[j] yer değiştirir; ardından iç parça a[i+1..j-1] tersine çevrilir.

void ters(int[] a, int i, int j) {
  if (i >= j)
    return;                    // taban: 0 ya da 1 öğe
  int t = a[i]; a[i] = a[j]; a[j] = t;  // uçlar
  ters(a, i + 1, j - 1);       // içteki parça
}
// main içinde:
int[] a = {2, 7, 4, 9, 1, 6};
ters(a, 0, a.length - 1);

Bu metodun öncekilerden iki farkı vardır. Birincisi, bir değer döndürmez (void). İş, dizinin kendisi değiştirilerek yapılır. Bütün çağrılar aynı diziyi gördüğü için bir çağrının yaptığı değiştirme ötekilere de yansır. İkincisi, iş özyinelemeli çağrıdan önce yapılır; dönüş yolunda yapılacak bir şey kalmaz.

Kaç değiştirme ve kaç çağrı yapılır? Her çağrı parçayı 2 öğe kısaltır. n öğeli dizide ⌊n/2⌋ değiştirme yapılır; buradaki ⌊ ⌋ işareti aşağı yuvarlamayı gösterir. Değiştirme yapan her çağrıya ek olarak, en sonda taban duruma düşen bir çağrı daha vardır. Toplam çağrı sayısı ⌊n/2⌋ + 1'dir. 6 öğeli dizi için 3 değiştirme ve 4 çağrı; 7 öğeli dizi için de 3 değiştirme ve 4 çağrı (ortadaki öğe yerinde kalır). Zaman O(n), yığın belleği O(n)'dir.

4.3.4Kod izleme: ters(a, 0, 5)

a = {2, 7, 4, 9, 1, 6} için ters(a, 0, 5) çağrısını izleyelim. Tabloda her çağrının i ve j değerleri ve çağrının sonunda dizinin durumu verilmiştir.

4. çağrıda yığında main ve 4 ters çerçevesi vardır. Bu çağrı döner; ardından 3., 2. ve 1. çağrılar sırayla döner. Dönüşte hiçbirinin yapacak işi yoktur, çünkü ters(a, i + 1, j - 1) satırı metodun son satırıdır. Sonuç: 6 1 9 4 7 2; 3 değiştirme, 4 çağrı.

4.3.5Üs alma: yavaş ve hızlı

xⁿ, x'in kendisiyle n kez çarpımıdır. Bu tanım hemen bir özyineleme verir: xⁿ = x · xⁿ⁻¹ ve x⁰ = 1.

long us(long x, int n) {
  if (n == 0) return 1;
  return x * us(x, n - 1);
}

Bu metot doğrudur, ama yavaştır. n her çağrıda yalnızca 1 azalır; us(x, n) n + 1 çağrı yapar (n, n − 1, …, 0). Zaman O(n), yığın belleği O(n)'dir. n = 1.000.000 için bir milyon çerçeve gerekir ve yığın taşar.

Daha hızlı bir yol için üslerin bir özelliğinden yararlanılır: x¹⁰ = x⁵ · x⁵ = (x⁵)². x⁵ bir kez hesaplanıp karesi alınırsa x¹⁰ bulunur. Böylece üs her adımda yarıya iner. Üs tek sayıysa yarıya tam bölünmez; o zaman bir x dışarıda bırakılır: x⁵ = x · x⁴ = x · (x²)². Genel kural şudur:

xⁿ = (x^n/2)² (n çift)  ·  xⁿ = x · (x^(n−1)/2)² (n tek)

Java'da tamsayı bölmesi aşağı yuvarladığı için tek n için n / 2, (n − 1)/2'ye eşittir. İki durumu da n / 2 ile yazmak mümkündür. Örneğin 2¹⁰ şöyle açılır:

2¹⁰ = (2⁵)²,   2⁵ = 2 · (2²)²,   2² = (2¹)²,   2¹ = 2 · (2⁰)²

long hizliUs(long x, int n) {
  if (n == 0) return 1;           // taban durum
  long y = hizliUs(x, n / 2);     // x^(n/2)
  if (n % 2 == 0) return y * y;   // n çift
  return x * y * y;               // n tek
}
// main içinde:
System.out.println(hizliUs(2, 10));

3. satırdaki y değişkeni bu metodun püf noktasıdır. x^n/2 bir kez hesaplanır ve y'de saklanır; kare almak için y * y yazılır. hizliUs(x, n / 2) * hizliUs(x, n / 2) yazılsaydı aynı değer iki kez hesaplanır ve kazanç kaybolurdu (bu tuzak 4.4.3'te yeniden ele alınır). 4. satır çift üs için kareyi döndürür. 5. satıra yalnız tek üste gelinir; burada kareye bir x çarpanı daha eklenir.

Hızlı sürüm kaç çağrı yapar? Her çağrıda n yarıya iner. n'yi 1'e indirmek için gereken yarılama sayısı ⌊log₂ n⌋'dir. Buna 1'in kendi çağrısı ve n = 0 taban durum çağrısı eklenir: toplam ⌊log₂ n⌋ + 2 çağrı (n ≥ 1 için). Zaman ve yığın belleği O(log n)'dir.

Tablo 4.5 iki büyüme hızı arasındaki farkı somutlaştırır. n bin kat büyüyünce us'un çağrı sayısı da bin kat büyür; hizliUs'unki yalnız yaklaşık 10 artar. Bir milyonluk üs için us yığını taşırır, hizliUs ise 21 çerçeveyle işini bitirir. Bu fark, problemi her adımda sabit miktarda değil, sabit oranda küçültmenin sonucudur.

4.3.6Kod izleme: hizliUs(2, 10)

main, hizliUs(2, 10)'u çağırıyor. İniş yolunda yalnız üs yarıya indirilir; çarpmaların hepsi dönüş yolunda yapılır.

Sonuç 1024'tür ve yalnız 5 çağrıyla bulunmuştur; yavaş us(2, 10) 11 çağrı yapardı. Dönen değerler dikkatle incelenirse 1, 2, 4, 32, 1024 dizisi görülür. Bunlar sırasıyla 2⁰, 2¹, 2², 2⁵, 2¹⁰'dur. Üsler 0, 1, 2, 5, 10'dur; bu sayılar 10'un ikili gösterimi olan 1010'un soldan büyüyen önekleridir (1, 10, 101, 1010). Tek üslü adımlar, ikili gösterimdeki 1 basamaklarına karşılık gelir.

4.4İkili özyineleme

Bazı problemlerde bir çağrı, kendini iki kez çağırır. Çağrılar artık düz bir zincir oluşturmaz; her çağrıdan iki dal çıkar ve bir ağaç oluşur. Böyle yapıların en bilinen örneği Fibonacci sayılarıdır. Fibonacci ağacının maliyeti ve bu maliyetten kurtulma yolları burada işlenir. Kesimin sonundaki ikili aramanın kodunda da iki çağrı yazılıdır, ama çağrılar ağaç değil zincir oluşturur.

4.4.1Fibonacci sayıları

Fibonacci dizisi 0 ve 1 ile başlar. Sonraki her sayı, kendinden önceki iki sayının toplamıdır: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … Dizi doğada (ayçiçeğindeki tohum dizilişi, bazı bitkilerde yaprakların dizilişi) ve bilgisayar biliminde (bazı veri yapılarının analizi) sık karşımıza çıkar.

Dizinin tanımı kendiliğinden özyinelemelidir:

F(0) = 0,   F(1) = 1,   F(n) = F(n − 1) + F(n − 2) (n ≥ 2)

Bu tanımda iki taban durum vardır: n = 0 ve n = 1. İki taban durum gereklidir, çünkü özyinelemeli adım iki önceki terime başvurur. Yalnız F(0) verilseydi F(1) = F(0) + F(−1) tanımsız kalırdı. Tanım koda doğrudan dökülür:

int fib(int n) {
  if (n <= 1) return n;    // taban durum
  return fib(n - 1) + fib(n - 2);
}

2. satır iki taban durumu tek koşulla yakalar: n ≤ 1 iken F(n) = n'dir (F(0) = 0, F(1) = 1). 3. satır iki özyinelemeli çağrı yapar ve sonuçlarını toplar.

Çağrı ağacı, ikili özyinelemeyi çözümlemenin temel aracıdır. Ağaçtaki düğüm sayısı toplam çağrı sayısını, ağacın derinliği ise yığında aynı anda bulunan en çok çerçeve sayısını verir. Fibonacci ağacının dikkat çekici bir özelliği, aynı değerin ağaçta birden çok kez hesaplanmasıdır. fib'in maliyetini bu tekrar belirler.

4.4.2Kod izleme: fib(4) çağrı ağacı

int fib(int n) {
  if (n <= 1) return n;    // taban durum
  return fib(n - 1) + fib(n - 2);
}
// main içinde:
System.out.println(fib(4));

fib(4)'ü izlerken önemli kural şudur: Java bir ifadeyi soldan sağa değerlendirir. fib(n - 1) + fib(n - 2) ifadesinde önce fib(n - 1) çağrılır ve tamamen biter. Ancak ondan sonra fib(n - 2) çağrılır. Sol dal bütünüyle bitmeden sağ dala geçilmez.

Sonuç F(4) = 3'tür ve 9 çağrıyla bulunmuştur. Bu 9 çağrının dağılımı şöyledir: fib(4) ve fib(3) birer kez, fib(2) iki kez, fib(1) üç kez, fib(0) iki kez. fib(2)'nin ikinci hesabı (7. çağrı) tamamen gereksizdir: aynı değer 3. çağrıda zaten bulunmuştu, ama hiçbir yerde saklanmadığı için yeniden hesaplanır.

Şekil 4.12'deki ağaçtan bellek maliyeti de okunur. Yığında aynı anda bulunan çerçeveler, kökten o an çalışan düğüme giden yoldur. En uzun yol fib(4) → fib(3) → fib(2) → fib(1)'dir: 4 çerçeve, main ile 5. Toplam çağrı 9 olduğu hâlde yığın hiçbir zaman 4 fib çerçevesini aşmaz.

4.4.3Özyinelemenin maliyeti

Özyinelemeli bir metodun zaman maliyeti, yaptığı toplam iştir. Her çağrı sabit miktarda iş yapıyorsa (bir karşılaştırma, bir toplama, bir dönüş), toplam iş çağrı sayısıyla orantılıdır. Maliyeti bulmak, çağrı sayısını bulmaya indirgenir.

faktoriyel için bu kolaydır. faktoriyel(n) bir kez faktoriyel(n - 1)'i çağırır. T(n), faktoriyel(n)'in yaptığı toplam iş olsun ve c bir çağrının kendi içindeki sabit işi göstersin. O zaman T(n) = T(n − 1) + c yazılır. Her çağrı bir sonrakini yapar ve zincir n çağrı uzunluğundadır. Zaman O(n), yığın belleği O(n)'dir. Bu tür denklemlere yineleme bağıntısı denir; 4.6 bu konuya ayrılmıştır.

fib için durum çok farklıdır. Her çağrı iki çağrı yapar ve aynı alt problemler tekrar tekrar çözülür.

int fib(int n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

Çağrı sayısı n büyüdükçe çok hızlı artar. fib(n)'in toplam çağrı sayısına C(n) diyelim. n ≤ 1 için tek çağrı yapılır: C(0) = C(1) = 1. Daha büyük n için çağrının kendisi, sol alt ağaç ve sağ alt ağaç toplanır: C(n) = C(n − 1) + C(n − 2) + 1. Bu bağıntı Fibonacci bağıntısına çok benzer ve çözümü de Fibonacci sayılarıyla yazılır.

Teorem, fib(4) için 2 · F(5) − 1 = 2 · 5 − 1 = 9 verir; izlemeyle aynı. Fibonacci sayıları her adımda yaklaşık 1,6 katına çıktığı için (oran, altın oran denen φ ≈ 1,618 sayısına yaklaşır) çağrı sayısı da yaklaşık 1,6ⁿ gibi büyür. Bu üstel bir büyümedir: n her 1 arttığında iş yaklaşık 1,6 katına çıkar.

Bellek ise hâlâ O(n)'dir. Ağaç ne kadar büyük olursa olsun, yığında aynı anda yalnız kökten bir düğüme giden tek bir yol bulunur ve en uzun yol n düğümlüdür. fib'in sorunu bellek değil, zamandır.

4.4.4Tekrarlanan hesaptan kaçınmak

Üstel büyümenin ne demek olduğu sayılara bakınca daha iyi anlaşılır. Tablo 4.8, fib(n)'in değerini ve yaptığı çağrı sayısını birkaç n için verir.

fib(40) 331 milyondan fazla çağrı yapar. Oysa farklı alt problem sayısı yalnızca 41'dir: fib(0)'dan fib(40)'a kadar. Çağrıların neredeyse hepsi daha önce çözülmüş bir problemi yeniden çözer. Bu israfı önlemenin iki yolu vardır.

1. Sonuçları saklamak. Bir değer ilk kez hesaplandığında bir dizide saklanır. Aynı değer yeniden istendiğinde hesaplanmaz, diziden okunur. Bu tekniğe sonuçları saklama ya da yaygın İngilizce adıyla memoization denir.

long[] bellek = new long[91];   // 0: hesaplanmadı
long fibBellek(int n) {
  if (n <= 1) return n;
  if (bellek[n] != 0) return bellek[n];
  bellek[n] = fibBellek(n - 1) + fibBellek(n - 2);
  return bellek[n];
}

bellek dizisi 91 öğelidir ve F(0)–F(90) değerlerini tutar. Bu değerlerin hepsi long'a sığar; long ancak F(92)'ye kadar yeter. Dizinin her hücresi başlangıçta 0'dır ve 0 “henüz hesaplanmadı” anlamına gelir. Bu seçim güvenlidir, çünkü n ≥ 2 için F(n) hiçbir zaman 0 değildir. Metot önce taban duruma bakar. Ardından değerin daha önce hesaplanıp hesaplanmadığını denetler; hesaplanmışsa hemen döndürür. Hesaplanmamışsa iki çağrıyı yapar, sonucu bellek[n]'e yazar ve döndürür.

fibBellek(40) 79 çağrı yapar. Bunun nedeni şudur. fibBellek(n)'in sol çağrısı fibBellek(n - 1), n − 1'e kadar her değeri hesaplar ve saklar. Sağ çağrı fibBellek(n - 2) geldiğinde değer zaten bellektedir; çağrı hemen döner. Her k ≥ 2 için bir “hesaplayan” çağrı ve onun sağ dalında değeri hazır bulan (ya da fibBellek(0) gibi taban duruma düşen) bir çağrı vardır; buna en alttaki fibBellek(1) eklenir. Toplam 2n − 1 çağrı yapılır: n = 40 için 79. Zaman O(n)'dir; yığın derinliği n ve bellek dizisi de O(n) yer kaplar.

2. Döngüyle hesaplamak. Fibonacci dizisi baştan sona doğru hesaplanırsa her adımda yalnız son iki terim gerekir.

long fibDongu(int n) {
  long a = 0, b = 1;              // F(0), F(1)
  for (int i = 0; i < n; i++) {
    long t = a + b;  a = b;  b = t;
  }
  return a;
}

a ve b her an ardışık iki terimi tutar. Döngünün başında a = F(0), b = F(1)'dir. Her turda t = a + b bir sonraki terimi hesaplar; sonra pencere bir adım kayar. n tur sonunda a = F(n) olur.

Altı turdan sonra a = 8 = F(6) döndürülür. Döngülü sürüm O(n) zaman ve O(1) bellek kullanır; çerçeve açmaz, yığın taşması riski yoktur. Fibonacci için en iyi seçim budur.

4.4.5Özyinelemeli ikili arama

Sıralı bir dizide bir x değerini aramak için ortadaki öğeye bakılır. x ortadaki öğeye eşitse aranan bulunmuştur. x daha küçükse, dizi sıralı olduğu için ancak sol yarıda olabilir; daha büyükse ancak sağ yarıda. Her iki durumda da aynı arama, yarı boyutlu bir parça üzerinde tekrarlanır. Bu, doğası gereği özyinelemeli bir algoritmadır.

Aranan parça lo ve hi indisleriyle verilir: a[lo..hi]. İki taban durum vardır:

• Aralık boş (lo > hi): aranacak öğe kalmamıştır; x dizide yoktur. Metot −1 döndürür.
• Ortadaki öğe x: aranan bulunmuştur; metot ortanın indisini döndürür.

int ikiliAra(int[] a, int x, int lo, int hi) {
  if (lo > hi) return -1;       // taban: boş aralık
  int mid = (lo + hi) / 2;
  if (a[mid] == x) return mid;  // taban: bulundu
  if (x < a[mid])
    return ikiliAra(a, x, lo, mid - 1); // sol yarı
  return ikiliAra(a, x, mid + 1, hi);   // sağ yarı
}
System.out.println(ikiliAra(a, 23, 0, 9));

Kodda iki özyinelemeli çağrı yazılıdır (6. ve 7. satırlar). Ama bir çağrı bunlardan yalnız birini yapar: if koşulu doğruysa sol yarıya, değilse sağ yarıya gidilir. Fibonacci'deki gibi bir ağaç oluşmaz; çağrılar yine bir zincirdir. İkili arama bu yüzden ikili değil, doğrusal özyinelemedir. Örnek, ağaç ile zincir arasındaki farkı göstermek için bu kesimde ele alınır.

Her çağrıda aralık yarıya iner. Yineleme bağıntısı T(n) = T(n/2) + c'dir; çözümü O(log n) zaman ve O(log n) yığın belleğidir (4.6.3). n = 10 öğeli dizide en çok 5, n = 10⁶ öğeli dizide en çok 21 çağrı yapılır; bu sayılar boş aralıkla biten son çağrıyı da içerir.

4.4.6Kod izleme: ikiliAra(a, 23, 0, 9)

Dizi a = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}, aranan x = 23'tür. main, ikiliAra(a, 23, 0, 9)'u çağırır.

3. çağrı taban durumda 5 döndürür. 2. çağrı aldığı 5'i return ile olduğu gibi iletir; 1. çağrı da aynısını yapar. Dönüş yolunda yeni bir hesap yapılmaz. Sonuç 5'tir ve 3 çağrıyla bulunmuştur; aralık 10 → 5 → 2 öğeye inmiştir.

4.5Hanoi kuleleri ve geri izleme

Önceki kesimdeki Fibonacci ağacı, özyinelemenin kötü kullanımına bir örnekti: aynı iş tekrar tekrar yapılıyordu. Bu kesimdeki problemlerde de çağrı ağacı üstel büyür, ama bu kez ağacın her düğümü farklı ve gerekli bir iş yapar. Hanoi kulelerinde her düğüm bir disk hamlesidir. Geri izlemede her yaprak, üretilmesi istenen bir alt küme ya da permütasyondur. Bu problemlerde üstel maliyetten kaçış yoktur, çünkü çıktının kendisi üstel büyüklüktedir. Özyineleme ise bu çıktıyı üretmenin en açık yoludur.

4.5.1Hanoi kuleleri

Hanoi kuleleri (Towers of Hanoi), bilgisayar biliminde ve matematikte klasik bir problemdir. Üç çubuk vardır: A, B ve C. A çubuğunda, büyükten küçüğe doğru üst üste dizilmiş n disk bulunur; en büyük disk en alttadır. Amaç, bütün diskleri A'dan C'ye taşımaktır. B çubuğu yardımcı olarak kullanılabilir. Taşıma iki kurala uyar:

• Her hamlede tek disk taşınır; bu, bir çubuğun en üstündeki disktir.
• Disk yalnız kendinden büyük bir diskin üstüne ya da boş çubuğa konabilir.

Problemi doğrudan, hamle hamle düşünmek zordur. Özyinelemeli düşünmek ise çözümü neredeyse kendiliğinden verir. En büyük diske odaklanalım. Bu disk bir noktada A'dan C'ye taşınmak zorundadır. O hamle yapılırken A'da başka disk olamaz (en büyük disk en üstte olmalıdır) ve C boş olmalıdır (en büyük disk hiçbir diskin üstüne konamaz). Öyleyse geri kalan n − 1 diskin hepsi o anda B'de olmalıdır. Bu gözlem üç adımlı bir plan verir:

1. Üstteki n − 1 diski A'dan B'ye taşı (C'yi yardımcı kullanarak).
2. En büyük diski A'dan C'ye taşı.
3. n − 1 diski B'den C'ye taşı (A'yı yardımcı kullanarak).

1. ve 3. adımlar, n − 1 diskli aynı problemdir; yalnız çubukların rolleri değişmiştir. Bu iki adım sırasında en büyük disk hiç rahatsız edilmez ve her disk ondan küçük olduğu için onun üstüne serbestçe konabilir. En büyük disk, küçük problem için yok sayılabilir. Taban durum tek disktir: tek disk doğrudan kaynaktan hedefe taşınır.

4.5.2Üç diskle yedi hamle

Üç diskli problemde plan şöyle işler. Üstteki 2 disk A'dan B'ye taşınır; bu, 3 hamle tutar. Disk 3, A'dan C'ye gider. Sonra 2 disk B'den C'ye taşınır; bu da 3 hamledir. Toplam 7 hamle eder.

Şekil 4.17, planın üç adımını açıkça gösterir. İlk üç hamle küçük iki diski B'de toplar (hamle 3'ten sonraki durum). Hamle 4 en büyük diski taşır. Son üç hamle küçük iki diski C'de en büyük diskin üstüne yerleştirir. İlk üç hamle ile son üç hamle aynı “2 diski taşı” işinin iki örneğidir; yalnız çubuklar farklıdır.

Hamle sayısı bu plandan hesaplanır. T(n), n diski taşımak için gereken hamle sayısı olsun. Tek disk için T(1) = 1'dir. Daha fazla disk için planın üç adımı toplanır: T(n) = T(n − 1) + 1 + T(n − 1) = 2T(n − 1) + 1. Birkaç değer hesaplayalım: T(2) = 3, T(3) = 7, T(4) = 15. Her değer bir ikinin kuvvetinin bir eksiğidir.

2ⁿ − 1 çok hızlı büyür. 20 disk için 1.048.575 hamle gerekir. Bir efsaneye göre tapınaktaki rahipler 64 diskli kuleyi taşıyor; iş bitince dünyanın sonu gelecektir. 2⁶⁴ − 1, yaklaşık 1,8 · 10¹⁹ hamledir; saniyede bir hamleyle yaklaşık 585 milyar yıl sürer.

4.5.3Kod izleme: hanoi(3, 'A', 'B', 'C')

Plan Java'ya doğrudan çevrilir. Metot dört parametre alır: disk sayısı n, kaynak çubuk k, yardımcı çubuk y ve hedef çubuk h.

void hanoi(int n, char k, char y, char h) {
  if (n == 1) {
    System.out.println("1: " + k + "→" + h);
    return;
  }
  hanoi(n - 1, k, h, y);
  System.out.println(n + ": " + k + "→" + h);
  hanoi(n - 1, y, k, h);
}
// main içinde:
hanoi(3, 'A', 'B', 'C');

2–5. satırlar taban durumdur: tek disk kaynaktan hedefe taşınır ve hamle “1: A→C” biçiminde yazdırılır. Baştaki sayı, taşınan diskin numarasıdır. 6. satır planın 1. adımıdır: n − 1 disk kaynaktan yardımcıya taşınır. Bu çağrıda hedefin (h) yardımcı, yardımcının (y) hedef rolüne geçtiğine dikkat edilmelidir: hanoi(n - 1, k, h, y). 7. satır en büyük diski, yani n numaralı diski taşır. 8. satır 3. adımdır: n − 1 disk yardımcıdan hedefe taşınır; bu kez kaynak yardımcı kullanılır: hanoi(n - 1, y, k, h).

Yazılan yedi satır, Şekil 4.17'deki yedi hamlenin aynısıdır. Çağrı ağacında 7 düğüm vardır: bir H(3,…), iki H(2,…) ve dört H(1,…). Her düğüm tam bir satır yazar; çağrı sayısı ile hamle sayısı eşittir: 2³ − 1 = 7.

Maliyet: zaman O(2ⁿ)'dir, çünkü 2ⁿ − 1 çağrının her biri sabit iş yapar. Bellek ise O(n)'dir. Yığında aynı anda en çok n hanoi çerçevesi bulunur (n, n − 1, …, 1 disklik çağrılar) ve main ile n + 1 çerçeve olur.

Çıktıda bir düzen daha göze çarpar. Disk 1 her ikinci hamlede, yani tek numaralı hamlelerde oynar; n diskte toplam 2ⁿ⁻¹ kez taşınır. Disk k ise 2^n−k kez taşınır; en büyük disk yalnız bir kez. Bu, ağaçta her seviyedeki düğüm sayısıyla aynıdır: en alt seviyede (tek disklik çağrılar) 2ⁿ⁻¹ düğüm vardır. Hanoi kuleleri simülatöründe bulmaca 1–6 diskle elle çözülebilir ya da en kısa çözüm adım adım izlenebilir. Simülatör yapılan hamle sayısını en az hamle sayısıyla (2ⁿ − 1; 6 disk için 63) karşılaştırır. Her kule bir yığın gibi davranır: yalnız en üstteki disk alınabilir.

4.5.4Geri izleme

Bazı problemlerde cevap tek bir değer değil, bir dizi seçimin sonucudur. Labirentte her kavşakta hangi yöne gidileceği, sudoku tablosunda her boş kareye hangi rakamın yazılacağı, kümeden hangi öğelerin seçileceği böyledir. Bu problemlerin genel çözüm yöntemine geri izleme denir.

Seçimi geri almak neden gereklidir? Geri izlemede kurulmakta olan çözüm (örneğin bir liste) genellikle bütün çağrılar arasında paylaşılan tek bir nesnedir. Bir dalda yapılan değişiklik geri alınmazsa sonraki dal bu değişikliği hazır bulur ve yanlış bir durumdan başlar. Seçim geri alınınca her dal, aynı başlangıç durumunu görür.

Hanoi'de olduğu gibi geri izlemede de her çağrı birden çok özyinelemeli çağrı yapar. Çağrı ağacı, denenen bütün seçimlerin ağacıdır; buna karar ağacı da denir. Kökten bir yaprağa giden her yol, bir seçimler dizisidir. Geri izlemenin bilinen örnekleri şunlardır: alt kümeleri ya da permütasyonları listelemek, labirentte yol bulmak, sudoku çözmek ve n vezir problemi. Son problemde bir satranç tahtasına birbirini tehdit etmeyen n vezir yerleştirilir.

4.5.5Alt kümeleri listeleme

Bir kümenin bütün alt kümelerini yazdırmak isteyelim. {1, 2, 3} kümesinin 8 alt kümesi vardır: {1, 2, 3}, {1, 2}, {1, 3}, {1}, {2, 3}, {2}, {3} ve boş küme. Bunları sistemli üretmenin yolu, her öğe için tek tek karar vermektir: bu öğe alt kümeye alınacak mı, alınmayacak mı? Her öğe için iki seçenek vardır ve n öğe için kararlar birbirinden bağımsızdır. Toplam 2 · 2 · … · 2 = 2ⁿ farklı karar dizisi, yani 2ⁿ alt küme vardır.

Karar ağacı doğrudan bir özyinelemeli metoda dönüşür. Metot üç parametre alır: dizi a, karar verilecek öğenin indisi i ve o ana kadar seçilen öğeleri tutan liste s.

void altKumeler(int[] a, int i, List<Integer> s) {
  if (i == a.length) {              // taban durum
    System.out.print(s + " "); return;
  }
  s.add(a[i]);                      // a[i]'yi al
  altKumeler(a, i + 1, s);
  s.remove(s.size() - 1);           // geri al
  altKumeler(a, i + 1, s);          // a[i]'siz dene
}
// main içinde:
altKumeler(new int[]{1, 2, 3}, 0, new ArrayList<>());

Metodun her parçası karar ağacındaki bir öğeye karşılık gelir:

• Taban durum (2–4. satırlar): i == a.length ise bütün öğeler için karar verilmiştir; ağacın bir yaprağındayız. s bir alt kümedir ve yazdırılır.
• Sol dal (5–6. satırlar): a[i] listeye eklenir ve bir sonraki öğe için karar verilir.
• Geri alma (7. satır): sol daldan dönülünce a[i] listeden çıkarılır. Liste, bu çağrının başındaki hâline döner.
• Sağ dal (8. satır): a[i] alınmadan bir sonraki öğeye geçilir.

s.remove(s.size() - 1) listenin son öğesini indisle siler. Son öğe her zaman bu çağrının eklediği a[i]'dir, çünkü alt çağrılar ekledikleri her şeyi kendileri geri almıştır. List<Integer> için s.remove(a[i]) yazmak tehlikelidir: a[i] bir int olduğundan Java bunu indis olarak yorumlar ve yanlış öğeyi siler.

Çağrı sayısı: karar ağacı tam bir ikili ağaçtır. Seviye k'de 2^k düğüm vardır (k = 0, 1, …, n). Toplam 1 + 2 + … + 2ⁿ = 2ⁿ⁺¹ − 1 çağrı yapılır. n = 3 için 8 alt küme ve 15 çağrı. Her yaprakta alt küme yazdırılırken O(n) iş yapıldığı için toplam zaman O(n · 2ⁿ)'dir. Yığın derinliği n + 1 çerçevedir; bellek O(n)'dir.

4.5.6Kod izleme: altKumeler ile {1, 2, 3}

main, altKumeler(new int[]{1, 2, 3}, 0, new ArrayList<>()) çağrısını yapıyor. Tablo 4.12, 15 çağrıyı başlama sırasıyla verir. Her satırda çağrının i değeri, çağrı başladığı andaki s ve çağrının ilk yaptığı iş yazılıdır.

Çıktı sırası şöyledir: [1, 2, 3] [1, 2] [1, 3] [1] [2, 3] [2] [3] []. Sıra, karar ağacının yapraklarının soldan sağa sırasıdır; çünkü her çağrı önce sol dalı (“al”), sonra sağ dalı (“alma”) bütünüyle gezer. “Al” ve “alma” dallarının sırası değiştirilirse yapraklar ters sırayla gelir; alt kümeler aynı kalır.

Yığında aynı anda en çok main ve 4 altKumeler çerçevesi vardır (kökten bir yaprağa giden yol: i = 0, 1, 2, 3).

4.5.7Permütasyonları listeleme

Bir dizi harfin bütün sıralanışlarını, yani permütasyonlarını yazdırmak isteyelim. A, B, C harflerinin 6 permütasyonu vardır: ABC, ACB, BAC, BCA, CAB, CBA. Geri izlemeyle çözüm şöyle kurulur: kelimenin ilk harfi için 3 seçenek vardır; ilk harf seçildikten sonra ikinci harf için kalan 2 harften biri seçilir; üçüncü harf için tek seçenek kalır. Toplam 3 · 2 · 1 = 3! = 6 permütasyon çıkar.

void perm(char[] h, boolean[] kul, StringBuilder s) {
  if (s.length() == h.length) {  // taban durum
    System.out.print(s + " "); return;
  }
  for (int k = 0; k < h.length; k++) {
    if (kul[k]) continue;        // harf kullanıldı
    kul[k] = true; s.append(h[k]);   // seç
    perm(h, kul, s);
    kul[k] = false;              // geri al
    s.deleteCharAt(s.length() - 1);
  }
}

Metodun üç parametresi vardır. h harfleri tutar. kul dizisi hangi harflerin o ana kadar kullanıldığını gösterir: kul[k] doğruysa h[k] kelimede vardır. s, kurulmakta olan kelimedir. Kelime harf sayısı uzunluğuna ulaşınca (2. satır) bir permütasyon tamamlanmıştır ve yazdırılır. Öteki durumda her kullanılmamış harf sırayla denenir: harf kullanıldı olarak işaretlenir ve kelimenin sonuna eklenir (7. satır); kalan harfler için özyinelemeli çağrı yapılır (8. satır); çağrı dönünce işaret kaldırılır ve harf kelimeden silinir (9–10. satırlar).

Bu metotta bir çağrı, kalan harf sayısı kadar özyinelemeli çağrı yapar: kökteki çağrı 3, ikinci seviyedekiler 2'şer, üçüncü seviyedekiler 1'er. Çağrı sayısı sabit değil, değişkendir; bu tür özyinelemeye çoklu özyineleme denir. n harf için yaprak sayısı n!'dir. Ağaçtaki toplam düğüm sayısı n!'in en çok yaklaşık 2,72 katıdır (n = 3 için 16 düğüm, 6 yaprak). Her düğüm O(n) adımlık bir for döngüsü çalıştırır ve her yaprakta n harflik bir kelime yazdırılır. Zaman bu yüzden O(n · n!)'dir. Yığın derinliği n + 1'dir; bellek O(n).

4.6Yineleme bağıntıları

Önceki kesimlerde her özyinelemeli metodun maliyetini çağrıları tek tek sayarak bulduk. Bu yöntem küçük girdilerde işe yarar, ama genel bir kural vermez. Daha genel bir yol, maliyeti bir denklemle yazıp bu denklemi çağrı ağacıyla çözmektir. Bölümde geçen bütün metotlar dört ya da beş denklem tipinden birine uyar.

4.6.1Yineleme bağıntısı nedir?

T(n), bir metodun n boyutlu girdide yaptığı toplam iş olsun. Özyinelemeli bir metotta bu iş iki parçadan oluşur: metodun kendi içinde yaptığı iş ve özyinelemeli çağrıların yaptığı iş. İkinci parça, aynı metodun daha küçük girdilerdeki maliyetidir. Böylece T(n), T'nin daha küçük değerleri cinsinden yazılır.

Bağıntıyı yazmak için metoda bakıp üç soru cevaplanır:

1. Taban durumun maliyeti nedir? Çoğunlukla bir sabittir; c ile gösterilir.
2. Kaç özyinelemeli çağrı yapılıyor ve girdileri ne kadar küçük?
3. Çağrılar dışında metodun kendisi ne kadar iş yapıyor?

Örneğin hizliUs bir çağrı yapar, girdisi n / 2'dir ve çağrı dışında bir karşılaştırma ile en çok iki çarpma yapar (sabit iş). Bağıntısı T(n) = T(n/2) + c'dir. Bölümdeki metotların bağıntıları Tablo 4.13'te toplanmıştır.

Bağıntıyı çözmenin en kolay yolu çağrı ağacını çizmektir. Her düğüm bir çağrıdır ve kendi içinde c kadar iş yapar. Toplam iş, düğüm sayısı ile c'nin çarpımıdır: T(n) ≈ c · (çağrı sayısı). Bağıntıyı çözmek, çağrı ağacındaki düğümleri saymaya indirgenir.

4.6.2T(n) = T(n − 1) + c

Bu bağıntı, girdiyi her adımda 1 azaltan doğrusal özyinelemeye aittir. Çözmek için bağıntı kendi içine tekrar tekrar yerleştirilir; buna bağıntıyı açmak denir:

T(n) = T(n − 1) + c
     = T(n − 2) + 2c
     = T(n − 3) + 3c
     …
     = T(0) + n · c
     = c + n · c   →  O(n)

Her açılışta bir c daha eklenir ve n 1 azalır. k açılıştan sonra T(n) = T(n − k) + k · c olur. k = n olunca taban duruma inilir: T(n) = T(0) + n · c = c + n · c. Bu O(n)'dir.

Çağrı ağacı burada düz bir zincirdir (Şekil 4.23). Zincirde n + 1 çağrı vardır ve zincirin tamamı aynı anda yığındadır: ilk çağrı, son çağrı dönmeden bitemez. Bellek de bu yüzden O(n)'dir. faktoriyel, toplam, geriSay, yavaş üs alma ve bağlı listenin uzunluğu bu bağıntıya uyar.

ters için girdi, yani parçanın uzunluğu, her adımda 2 azalır: T(n) = T(n − 2) + c. Açılınca T(n) = T(n − 2k) + k · c çıkar ve taban duruma yaklaşık k = n/2 adımda inilir. Çağrı sayısı yarıya iner, ama n/2 de n ile doğru orantılı olduğundan sonuç yine O(n)'dir. Girdiyi sabit bir miktar azaltmak, bu miktar ne olursa olsun, doğrusal bir zincir verir.

4.6.3T(n) = T(n/2) + c

Bu bağıntı, girdiyi her adımda yarıya indiren özyinelemeye aittir. Açalım:

T(n) = T(n/2) + c
     = T(n/4) + 2c
     = T(n/8) + 3c
     …
     = T(n/2ᵏ) + k · c

k açılıştan sonra girdi n/2^k'dir. Taban duruma girdi 1 olunca ulaşılır: n/2^k = 1, yani 2^k = n, yani k = log₂ n. Bu değer yerine konunca T(n) = T(1) + c · log₂ n bulunur. Bu O(log n)'dir.

Logaritma burada tek bir soruya cevaptır: n'yi kaç kez yarıya bölersek 1'e ulaşırız? 16 → 8 → 4 → 2 → 1 dizisinde 4 bölme vardır ve log₂ 16 = 4'tür. n ikinin kuvveti değilse tamsayı bölmesi aşağı yuvarlar ve bölme sayısı ⌊log₂ n⌋ olur.

Girdi bin kat büyüyünce (1.024'ten yaklaşık bir milyona) zincir yalnızca yaklaşık 10 çağrı uzar. Logaritmik büyüme bu kadar yavaştır. Zincirin derinliği de log n olduğu için bellek O(log n)'dir. İkili arama ve hızlı üs alma bu bağıntıya uyar. (Gerçek metotlarda taban durum 0 ya da boş aralık olabilir; o zaman zincire bir çağrı daha eklenir. hizliUs'un ⌊log₂ n⌋ + 2 çağrısı bu yüzdendir.)

4.6.4T(n) = 2T(n − 1) + c

Bu bağıntıda her çağrı, n − 1 boyutlu iki çağrı yapar. Çağrı ağacının her seviyesinde çağrı sayısı ikiye katlanır. Kökte (seviye 0) 1 çağrı, seviye 1'de 2 çağrı, seviye 2'de 4 çağrı vardır; seviye k'de 2^k çağrı. Taban durum n = 1 ise seviyeler 0'dan n − 1'e kadar gider.

1 + 2 + 4 + … + 2ⁿ⁻¹ = 2ⁿ − 1 çağrı → O(2ⁿ)

Bu toplamın değeri, ikinin kuvvetlerinin bilinen bir özelliğinden gelir: ikinin ardışık kuvvetlerinin toplamı, bir sonraki kuvvetin bir eksiğidir. Örneğin 1 + 2 + 4 + 8 = 15 = 16 − 1. İkili sayılarla düşünülünce bu açıktır: 1111 ikili sayısı 15'tir ve 1 eklenince 10000, yani 16 olur.

Hanoi kuleleri bu bağıntıya tam uyar: 2ⁿ − 1 hamle. n = 20 için 1.048.575, n = 64 için yaklaşık 1,8 · 10¹⁹ hamle.

fib'in bağıntısı T(n) = T(n − 1) + T(n − 2) + c'dir. T(n − 2) ≤ T(n − 1) olduğu için T(n) ≤ 2T(n − 1) + c yazılabilir. Buradan fib için üst sınır olarak O(2ⁿ) çıkar. Gerçek büyüme bundan biraz yavaştır: 4.4.3'te gösterildiği gibi yaklaşık 1,6ⁿ. Ama 1,6 tabanı da üsteldir; n = 40 için 331 milyon çağrı bunun sonucudur.

Bu ağaç ne kadar büyük olursa olsun derinliği yalnız n'dir. Yığında aynı anda en çok n çerçeve bulunur. Zaman üstel, bellek doğrusaldır.

4.6.5Alan maliyeti: en derin çağrı zinciri

Zaman maliyeti çağrı ağacındaki bütün düğümlerden gelir. Alan maliyeti ise başka bir ölçüye bağlıdır. Bir çağrı, kardeşi başlamadan önce tamamen biter. Örneğin fib(4)'te fib(3)'ün bütün alt ağacı bitmeden fib(2) başlamaz. Bu yüzden yığında aynı anda yalnız kökten bir düğüme giden tek bir yol bulunur. Bitmiş çağrıların çerçeveleri silinmiştir, henüz başlamamış çağrıların çerçeveleri ise yoktur.

Bellek = en derin çağrı zinciri × çerçeve boyutu

Toplam çağrı sayısı değil, ağacın derinliği belirleyicidir. fib(4) 9 çağrı yapar, ama yığında aynı anda en çok 4 fib çerçevesi (ve main) bulunur.

Tablo 4.15 çarpıcı bir farkı gösterir. fib(40) üç yüz milyondan fazla çağrı yapar ve sonucu beklemek fark edilir bir süre alır, ama belleği hiç zorlamaz: yığın en çok 40 çerçeve derinliğe iner. Tersine, topla(1_000_000) yalnız bir milyon çağrı yapar ve bu zaman açısından hiç sorun değildir; ama bir milyon çerçevelik zincir yığını taşırır (4.2.3). Özyinelemede zaman sorunu ile bellek sorunu birbirinden bağımsızdır ve ayrı ayrı denetlenmelidir.

altKumeler satırındaki zaman, yalnız çağrı sayısından gelmez. Çağrı sayısı 2ⁿ⁺¹ − 1'dir, ama 2ⁿ yaprağın her birinde n'ye kadar öğeli bir liste yazdırılır. Yazdırmanın maliyeti eklenince toplam O(n · 2ⁿ) olur.

4.7Kuyruk özyinelemesi

Özyinelemeli metotların büyük bir kısmı dönüş yolunda iş yapar: faktoriyel çarpmayı, toplam toplamayı, ileriSay yazdırmayı dönüşte yapar. Bu yüzden çerçeveler, alt çağrılar bitene kadar bellekte beklemek zorundadır. Bazı metotlarda ise dönüşte yapılacak hiçbir iş yoktur. Böyle metotlar özeldir: döngüye kolayca çevrilir.

4.7.1Kuyruk özyinelemesi nedir?

faktoriyel kuyruk özyinelemeli değildir:

int faktoriyel(int n) {
  if (n <= 1) return 1;
  return n * faktoriyel(n - 1);
  // çarpma, çağrı dönünce yapılır
}

return n * faktoriyel(n - 1); satırında çağrı son iş gibi görünür, ama değildir. Çağrı döndükten sonra sonucun n ile çarpılması gerekir. Son iş çarpmadır.

Faktöriyeli kuyruk özyinelemeli yazmak için çarpmayı çağrıdan önceye almak gerekir. Bunun yolu, ara sonucu bir parametreyle aşağı taşımaktır. Bu parametreye biriktirici (accumulator) denir ve geleneksel olarak acc diye adlandırılır.

int faktKuyruk(int n, int acc) {
  if (n <= 1) return acc;
  return faktKuyruk(n - 1, n * acc);
  // son iş: çağrı (çarpma önce)
}

acc, o ana kadar yapılmış çarpmaların sonucunu tutar. Her çağrı kendi n'sini acc ile çarpar ve sonucu bir sonraki çağrıya verir. Taban durumda bütün çarpmalar yapılmıştır; acc sonucun kendisidir ve döndürülür. İlk çağrı faktKuyruk(n, 1) biçiminde yapılır, çünkü henüz hiçbir çarpma yapılmamıştır ve 1 çarpmanın etkisiz öğesidir.

Bölümdeki metotlar bu açıdan ikiye ayrılır:

• Kuyruk özyinelemeli: geriSay (yazdırma çağrıdan önce), ters (değiştirme çağrıdan önce), ikiliAra (dönen değer olduğu gibi iletilir), faktKuyruk.
• Kuyruk özyinelemeli değil: faktoriyel ve toplam (çağrıdan sonra çarpma ya da toplama), fib (iki çağrının sonucu toplanır), ileriSay (çağrıdan sonra yazdırma).

4.7.2Kod izleme: faktKuyruk(4, 1)

int faktKuyruk(int n, int acc) {
  if (n <= 1) return acc;   // taban durum
  return faktKuyruk(n - 1, n * acc);  // son iş
}
// main içinde:
System.out.println(faktKuyruk(4, 1));

Tablo 4.2'deki faktoriyel(4) izlemesiyle karşılaştırınca fark açıkça görülür. Orada çarpmalar dönüş yolunda yapılıyordu: 2 · 1, 3 · 2, 4 · 6. Burada çarpmalar iniş yolunda yapılır: 4 · 1, 3 · 4, 2 · 12. Çarpma sırası farklıdır ama çarpma değişmeli olduğu için sonuç aynıdır. Asıl fark dönüş yolundadır. 5–7. adımlarda hiçbir çerçeve yeni bir hesap yapmaz; hepsi aldığı 24'ü olduğu gibi iletir.

Dönüşte yapılacak iş yoksa bekleyen çerçevelere de gerek yoktur. Bir derleyici bunu fark edip kuyruk çağrısında yeni çerçeve açmak yerine mevcut çerçeveyi yeniden kullanabilir. Bu eniyilemeye kuyruk çağrısı eniyilemesi denir. Ama Java bunu yapmaz: faktKuyruk için de her çağrıda yeni bir çerçeve açılır. Yukarıdaki izlemede 4 çerçeve açılmıştır; dönüşte bu çerçevelere ihtiyaç yoktu, ama yine de yığında yer tuttular.

4.7.3Döngüye çevirme

Kuyruk özyinelemeli bir metot her zaman bir döngüye çevrilebilir ve bu çevirme tamamen mekaniktir. Bir kuyruk çağrısı, parametrelere yeni değerler verip metodun başına dönmek demektir. Döngü de tam olarak bunu yapar.

int faktDongu(int n) {
  int acc = 1;
  while (n > 1) {   // taban durum değilken
    acc = n * acc;  // çağrının yeni
    n = n - 1;      //   parametreleri
  }
  return acc;       // taban: return acc
}

Çevirmenin kuralları şunlardır:

• Parametreler değişken olur. n zaten bir parametredir; acc, ilk çağrıdaki değeri olan 1 ile başlatılan yerel bir değişkene dönüşür.
• Taban durumun tersi döngü koşulu olur. Özyineleme n <= 1 iken durur; döngü n > 1 iken sürer.
• Kuyruk çağrısı, parametrelerin güncellenmesi olur. faktKuyruk(n - 1, n * acc) çağrısı, acc = n * acc; ve n = n - 1; atamalarına dönüşür. Atamaların sırası önemlidir: acc eski n ile hesaplanmalıdır. Önce n azaltılsaydı yanlış sayıyla çarpılırdı.
• Taban durumdaki dönüş, döngüden sonraki dönüş olur: return acc;.

Döngü sabit bellekle çalışır: yalnız iki değişken vardır, çerçeve açılmaz. Bellek O(1), zaman O(n)'dir. Aynı çevirme ikiliAra'ya da uygulanabilir: lo ve hi değişken olur, döngü lo <= hi iken sürer, her turda lo ya da hi güncellenir. Bilinen döngülü ikili arama, özyinelemeli sürümün tam olarak bu biçimde çevrilmiş hâlidir.

Dil desteği konusunda bir not: Java derleyicisi ve JVM kuyruk çağrısını eniyilemez; çok derin bir kuyruk özyinelemesi de StackOverflowError verir. Scheme gibi bazı diller bu eniyilemeyi dilin kuralı olarak garanti eder. Scala ve Kotlin derleyicileri, bir metodun kendini çağıran kuyruk özyinelemesini döngüye çevirebilir. Java'da derinliği büyük olabilecek kuyruk özyinelemesi, bu yüzden elle döngüye çevrilir.

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

Her döngü özyinelemeyle, her özyineleme de döngüyle yazılabilir. Seçim, problemin yapısına ve girdinin büyüklüğüne bağlıdır. Tablo 4.18 iki yaklaşımı dört ölçüte göre karşılaştırır.

Şu durumlarda özyineleme doğal seçimdir: veri iç içe bir yapıdaysa (ağaçlar, iç içe klasörler, iç içe ifadeler); problem geri izleme gerektiriyorsa (alt kümeler, permütasyonlar); problem her adımda yarıya bölünüyorsa; Hanoi gibi tanımı özyinelemeli olan problemlerde. Bu durumların ortak noktası, derinliğin küçük olmasıdır: log n kadar ya da n'nin kendisi küçük.

Şu durumlarda döngü daha iyidir: basit sayma ve toplama işlerinde; derinliği n'ye ulaşan doğrusal özyinelemede, özellikle n büyükse (uzun bir bağlı liste, büyük bir sayı); tekrarlanan alt problemli ikili özyinelemede (fib).

Daha genel bir sonuç da vardır: kuyruk özyinelemeli olmayanlar dahil, her özyinelemeli metot döngüye çevrilebilir. Bunun yolu, çağrı yığınının yaptığı işi açık bir yığın veri yapısıyla yapmaktır. Bekleyen işler (yarım kalmış çarpmalar, henüz çözülmemiş alt problemler) bir yığına konur ve döngü yığın boşalana kadar sürer. Hanoi kuleleri böyle bir “görev yığınıyla” özyinelemesiz çözülebilir. Bu çevirme kuyruk özyinelemesindeki kadar kısa değildir, ama yığın taşması riskini ortadan kaldırır: açık yığın, çağrı yığınının aksine, programın genel belleğinde büyür.

4.8Bağlı listede özyineleme

Özyineleme yalnızca sayılar ve diziler üzerinde değil, veri yapılarının kendisi üzerinde de doğal bir araçtır. En basit bağlantılı veri yapısı tek yönlü bağlı listedir ve özyinelemeli bir gözle bakılınca işlemleri çok kısa yazılır. Aynı bakış ağaçlar gibi daha karmaşık yapılarda da işe yarar.

4.8.1Liste özyinelemeli bir yapıdır

Bağlı liste (linked list), öğeleri düğümlerde (node) tutan bir veri yapısıdır. Her düğüm bir veri ve bir sonraki düğümün referansını taşır. Son düğümün “sonraki” referansı null'dır. Listenin ilk düğümünü gösteren referansa genellikle bas denir. Liste boşsa bas da null'dır.

Bu yapıya özyinelemeli bir tanım verilebilir: bağlı liste ya boştur (null) ya da bir düğüm ile onu izleyen daha kısa bir listedir. bas → 7 → 3 → 9 → null listesi, 7'yi taşıyan bir düğüm ile 3 → 9 → null listesinden oluşur. O liste de 3'ü taşıyan düğüm ile 9 → null listesinden oluşur. En sonda boş liste vardır.

Tanım özyinelemeli olduğu için liste üzerindeki işlemler de doğal olarak özyinelemeli yazılır. Kalıp hep aynıdır: düğüm işlenir, kalan liste (d.sonraki) aynı metoda verilir. Taban durum boş listedir: d == null. Listenin uzunluğu bu kalıbın en sade örneğidir:

class Dugum { int veri; Dugum sonraki; }

int uzunluk(Dugum d) {
  if (d == null) return 0;        // boş liste
  return 1 + uzunluk(d.sonraki);  // 1 + kalan
}

Boş listenin uzunluğu 0'dır. Boş olmayan listenin uzunluğu, ilk düğüm için 1 artı kalan listenin uzunluğudur. Özyinelemeli düşünmenin üç sorusu burada şöyle cevaplanır: taban durum d == null, küçültme d.sonraki'ye geçmek, birleştirme 1 eklemek. Listeyi baştan sona yazdıran metot da aynı kalıba uyar:

void yazdir(Dugum d) {
  if (d == null) return;
  System.out.print(d.veri + " ");
  yazdir(d.sonraki);
}

4.8.2Kod izleme: uzunluk(bas)

int uzunluk(Dugum d) {
  if (d == null) return 0;        // boş liste
  return 1 + uzunluk(d.sonraki);  // 1 + kalan
}
// main içinde (bas → 7 → 3 → 9 → null):
System.out.println(uzunluk(bas));

Sonuç 3'tür. 4 çağrı yapılmıştır: 3 düğüm ve sondaki null. n düğümlü listede n + 1 çağrı yapılır ve yığın en derin anda n + 1 çerçeve içerir. Zaman O(n), yığın belleği O(n)'dir.

Bu bellek maliyeti, listeler için ciddi bir sorundur. Bağlı listeler milyonlarca düğüm içerebilir ve uzunluk, bir milyon düğümlü listede bir milyon çerçeve açmaya çalışır. 4.2.3'te görüldüğü gibi bu kadar çerçeve varsayılan yığına sığmaz. Döngülü sürüm aynı işi sabit bellekle yapar: int s = 0; for (Dugum d = bas; d != null; d = d.sonraki) s++;.

4.8.3Listeyi tersten yazdırma

Tek yönlü bağlı listede her düğüm yalnız bir sonrakini bilir; bir öncekine giden referans yoktur. Listeyi sondan başa yazdırmak bu yüzden döngüyle kolay değildir. Önce son düğüme gidilir, ama ondan sonra bir öncekine dönülemez. Özyineleme bu sorunu kendiliğinden çözer.

void tersYazdir(Dugum d) {
  if (d == null) return;
  tersYazdir(d.sonraki);  // önce kalan
  System.out.print(d.veri + " ");
}

4.8.1'deki yazdir ile bu metot arasındaki tek fark, yazdırma satırının özyinelemeli çağrıdan önce mi sonra mı geldiğidir. Bu, 4.1.5'teki geriSay2 ile ileriSay farkının aynısıdır. yazdir(bas) çıktısı 7 3 9'dur: yazdırma çağrıdan önce yapılır ve düğümler gidiş sırasıyla yazılır. tersYazdir(bas) çıktısı ise 9 3 7'dir.

Tek yönlü listede geriye giden bağlantı yoktur; geri dönüşü çağrı yığını sağlar. Her çerçeve kendi düğümünü “aklında tutar” ve sırası gelince yazar. Bunun bedeli O(n) yığın belleğidir. Çok uzun listelerde aynı iş bir döngü ve açık bir yığın veri yapısıyla daha güvenli yapılır. Döngü düğümleri baştan sona dolaşır ve her birini yığına ekler. Sonra yığın boşaltılır; düğümler ters sırayla çıkar ve yazdırılır.

4.9Sık yapılan hatalar

Özyinelemedeki hataların çoğu birkaç tipe ayrılır. Not boyunca her konunun yanında verilen hatalar burada bir arada toplanmıştır; özyinelemeli bir metodu gözden geçirirken kontrol listesi olarak kullanılabilir.

Bu hataların hepsi aynı iki soruya bağlanır. Birincisi doğrulukla ilgilidir: taban durum her girdiyi yakalıyor mu ve her adım ona yaklaşıyor mu? İlk iki hata bu sorunun cevabının “hayır” olduğu durumlardır. Üçüncü ve dördüncü hata da doğrulukla ilgilidir, ama tümevarım varsayımının bozulmasıyla: küçük problemin cevabı ya kaybolur ya da küçük problem yanlış bir durumdan başlar. İkinci soru maliyetle ilgilidir: çağrı ağacı kaç düğümlü ve ne kadar derin? Son iki hata bu sorunun cevabı göz ardı edildiğinde ortaya çıkar. Düğüm sayısı üstelse zaman, derinlik çok büyükse bellek sorun olur.

4.10Özet

• Özyineleme, bir metodun kendini daha küçük bir girdiyle çağırmasıdır. Her özyinelemeli metot bir taban durum (doğrudan çözülen girdiler) ve taban duruma yaklaşan bir özyinelemeli adım içerir. Özyinelemeli düşünmede küçük problemin doğru çözüldüğü kabul edilir ve yalnız son adım düşünülür; bu, tümevarımın mantığıdır.
• Bir iş özyinelemeli çağrıdan önce yapılırsa çağrılar inerken, sonra yapılırsa çağrılar dönerken ve ters sırayla yapılır (geriSay2 → 3 2 1, ileriSay → 1 2 3).
• Her çağrı çağrı yığınında bir çerçeve açar: parametreler, yerel değişkenler, dönüş adresi. Çerçeveler LIFO düzeniyle eklenip çıkarılır; yalnız en üstteki çalışır. Yığın sınırlıdır: çok derin ya da sonsuz özyineleme StackOverflowError verir. Her girdi, 0 ve negatifler dahil, sonlu adımda bir taban duruma ulaşmalıdır.
• Doğrusal özyinelemede her çağrı en çok bir çağrı yapar ve çağrılar bir zincir oluşturur: faktoriyel, toplam, ters, uzunluk. Girdi her adımda yarıya inerse zincir O(log n) uzunluğundadır: hizliUs ⌊log₂ n⌋ + 2 çağrı yapar, ikiliAra O(log n)'dir.
• İkili özyinelemede bir çağrı iki çağrı yapar ve bir çağrı ağacı oluşur. fib(n) 2F(n + 1) − 1 çağrı yapar ve yaklaşık 1,6ⁿ hızında büyür, çünkü aynı alt problemler tekrar tekrar çözülür. Sonuçları saklamak ya da döngü O(n) verir; döngülü sürüm O(1) bellek kullanır.
• Hanoi kuleleri üç adımla çözülür: n − 1 disk yardımcıya, en büyük disk hedefe, n − 1 disk hedefe. Hamle sayısı 2ⁿ − 1'dir ve bu en azdır.
• Geri izleme, çözümü adım adım kurar: bir seçenek seçilir, özyinelemeli çağrıyla ilerlenir, dönüşte seçim geri alınır. altKumeler 2ⁿ alt küme ve 2ⁿ⁺¹ − 1 çağrı, perm n! permütasyon üretir.
• Yineleme bağıntısı, maliyeti küçük girdilerin maliyetiyle yazar ve çağrı ağacıyla çözülür: T(n − 1) + c → O(n), T(n/2) + c → O(log n), 2T(n − 1) + c → O(2ⁿ). Zaman çağrı sayısından, alan en derin çağrı zincirinden gelir.
• Kuyruk özyinelemesinde özyinelemeli çağrı metodun son işidir; ara sonuç bir biriktiriciyle taşınır. Böyle bir metot mekanik olarak döngüye çevrilir: parametreler değişken, taban durumun tersi döngü koşulu olur. Java kuyruk çağrısını eniyilemez; faktKuyruk da O(n) yığın kullanır.
• Bağlı liste özyinelemeli bir yapıdır: ya boştur ya da bir düğüm ve daha kısa bir listedir. Taban durum d == null'dır. tersYazdir, çağrı yığınını kullanarak tek yönlü listeyi sondan başa yazar; bedeli O(n) yığın belleğidir.

Bölümün tamamı tek bir cümleye sığar: özyineleme, taban durum ile taban duruma yaklaşan özyinelemeli adımdan oluşur; zaman maliyeti çağrı sayısından, alan maliyeti en derin çağrı zincirinden gelir.

4.11Kavram listesi

Terimlerin İngilizce karşılıkları ve öteki bölümlerdeki kullanımları terim sözlüğünde bulunur.

• özyineleme recursion
• taban durum base case
• özyinelemeli adım recursive step
• çerçeve stack frame
• çağrı yığını call stack
• LIFO last-in, first-out
• doğrusal özyineleme linear recursion
• ikili özyineleme binary recursion
• çoklu özyineleme multiple recursion
• ikili arama binary search
• Hanoi kuleleri Towers of Hanoi
• geri izleme backtracking
• yineleme bağıntısı recurrence relation
• kuyruk özyinelemesi tail recursion
• biriktirici accumulator
• bağlı liste linked list
• düğüm node
• zaman karmaşıklığı time complexity
• alan karmaşıklığı space complexity

4.12Kendini Dene

1. void yaz(int n) { if (n == 0) return; yaz(n / 10); System.out.print(n % 10 + " "); } için yaz(472) ne yazar? Kaç çağrı yapılır ve yığında (main dahil) en çok kaç çerçeve bulunur?

   Cevap

   Çağrılar 472, 47, 4, 0 girdileriyle yapılır: 4 çağrı. yaz(0) taban durumdur ve hiçbir şey yazmaz. Yazdırma çağrıdan sonra olduğu için dönüşte, ters sırayla yapılır: önce yaz(4) 4'ü, sonra yaz(47) 7'yi, en son yaz(472) 2'yi yazar. Çıktı 4 7 2'dir; basamaklar soldan sağa yazılmıştır. En derin anda 4 yaz çerçevesi ve main vardır: 5 çerçeve.

2. hizliUs(3, 9) kaç çağrı yapar? Her çağrı ne döndürür?

   Cevap

   n değerleri 9, 4, 2, 1, 0'dır: 5 çağrı (⌊log₂ 9⌋ + 2 = 3 + 2). Dönüşte: hizliUs(3, 0) = 1; n = 1 tek, 3 · 1 · 1 = 3; n = 2 çift, 3 · 3 = 9; n = 4 çift, 9 · 9 = 81; n = 9 tek, 3 · 81 · 81 = 19.683. Sonuç 3⁹ = 19.683.

3. Özyinelemeli fib(7) kaç çağrı yapar? Yığında aynı anda en çok kaç fib çerçevesi bulunur?

   Cevap

   F(8) = 21 olduğundan çağrı sayısı 2 · 21 − 1 = 41'dir; fib(7) = 13. En derin zincir fib(7) → fib(6) → … → fib(1)'dir: 7 çerçeve (main ile 8). Zaman üstel, bellek O(n).

4. a = {1, 4, 7, 10, 13, 16, 19} dizisinde ikiliAra(a, 19, 0, 6) ve ikiliAra(a, 5, 0, 6) kaçar çağrı yapar, ne döndürür?

   Cevap

   19 için: (0, 6) mid = 3, 19 > 10; (4, 6) mid = 5, 19 > 16; (6, 6) mid = 6, bulundu. 3 çağrı, 6 döner. 5 için: (0, 6) 5 < 10; (0, 2) mid = 1, 5 > 4; (2, 2) mid = 2, 5 < 7; (2, 1) aralık boş. 4 çağrı, −1 döner.

5. 5 diskli Hanoi kulelerinde toplam kaç hamle yapılır? 2 numaralı disk kaç kez taşınır?

   Cevap

   2⁵ − 1 = 31 hamle. Disk k, 2^n−k kez taşınır: disk 2 için 2³ = 8. Denetim: disk 1'den 5'e taşınma sayıları 16, 8, 4, 2, 1'dir ve toplamı 31'dir.

6. altKumeler(new int[]{5, 6}, 0, new ArrayList<>()) ne yazar ve kaç çağrı yapar?

   Cevap

   Çıktı [5, 6] [5] [6] []'dir. Karar ağacında 1 + 2 + 4 = 7 düğüm vardır: 2²⁺¹ − 1 = 7 çağrı. Yığın en çok 3 altKumeler çerçevesi içerir.

7. Bir metot n <= 0 iken sabit iş yapıp duruyor, öteki durumda sabit iş yapıp kendini n − 3 ile bir kez çağırıyor. Yineleme bağıntısı nedir? n = 12 için kaç çağrı yapılır?

   Cevap

   T(n) = T(n − 3) + c. Zincir 12, 9, 6, 3, 0'dır: 5 çağrı. Genel olarak yaklaşık n/3 + 1 çağrı yapılır; bu O(n)'dir, çünkü girdi her adımda sabit bir miktar azalır.

8. int ik(int n, int acc) { if (n == 0) return acc; return ik(n - 1, acc * 2); } kuyruk özyinelemeli midir? ik(5, 1) hangi çağrı zinciriyle ne döndürür? Döngülü karşılığı nedir?

   Cevap

   Evet: çarpma parametre hesaplanırken, çağrıdan önce yapılır; dönen değer değiştirilmeden iletilir. Zincir (5, 1) → (4, 2) → (3, 4) → (2, 8) → (1, 16) → (0, 32); 6 çağrı, 32 döner (2⁵). Döngülü karşılığı: int acc = 1; while (n != 0) { acc = acc * 2; n = n - 1; } return acc;. Java'da özyinelemeli sürüm O(n), döngü O(1) bellek kullanır.

9. int say(Dugum d, int x) { if (d == null) return 0; return (d.veri == x ? 1 : 0) + say(d.sonraki, x); }. Liste 2 → 7 → 2 → 2 → null ise say(bas, 2) ne döndürür, kaç çağrı yapar? Metot kuyruk özyinelemeli midir?

   Cevap

   3 döndürür (2 değerli üç düğüm). Çağrı sayısı düğüm sayısı artı 1'dir: 5 (dört düğüm ve null). Kuyruk özyinelemeli değildir: çağrı döndükten sonra sonuca 0 ya da 1 eklenir. Biriktiricili bir sürüm (say(d.sonraki, x, acc + …)) kuyruk özyinelemeli olur.

10. int t(int n) { if (n <= 1) return 1; return t(n - 1) + t(n - 1) + t(n - 1); } için t(3) ne döndürür, kaç çağrı yapar? Metot nasıl doğrusal yapılır?

    Cevap

    Çağrı ağacında seviyeler 1, 3, 9 düğümlüdür: 1 + 3 + 9 = 13 çağrı. 9 yaprağın her biri 1 döndürür: t(3) = 9 = 32. Genel olarak t(n) = 3ⁿ⁻¹ ve çağrı sayısı (3ⁿ − 1)/2'dir: O(3ⁿ). Üç çağrı aynı değeri hesaplar; return 3 * t(n - 1); yazılırsa tek çağrı kalır ve maliyet O(n) olur.

4.13İleri okuma

• M. T. Goodrich, R. Tamassia ve M. H. Goldwasser, Data Structures and Algorithms in Java (6. baskı, 2014), Bölüm 5: özyinelemeyi doğrusal, ikili ve çoklu özyineleme diye ayırarak anlatır ve bu nottakine yakın Java örnekleri (ikili arama, diziyi tersine çevirme, üs alma) verir.
• R. Sedgewick ve K. Wayne, Computer Science: An Interdisciplinary Approach (2016), Kesim 2.3: Hanoi kuleleri, Fibonacci'deki tekrarlanan hesap ve sonuçları saklama konularını kısa programlar ve deneylerle işler.
• E. Roberts, Thinking Recursively with Java (2006): kitabın tamamı özyinelemeli düşünmeye ayrılmıştır; tümevarımla bağlantıyı ve geri izleme örneklerini başlangıç düzeyindeki okura göre açıklar.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein, Introduction to Algorithms (4. baskı, 2022), Bölüm 4: yineleme bağıntılarını özyineleme ağacı ve yerine koyma yöntemleriyle daha biçimsel bir dille çözer.

4.14Kaynaklar

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022.
2. M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6. baskı, Wiley, 2014.
3. E. Roberts, Thinking Recursively with Java, Wiley, 2006.
4. R. Sedgewick, K. Wayne, Computer Science: An Interdisciplinary Approach, Addison-Wesley, 2016.

İlgili sayfalar: Bölüm 4 sunumu · Çalışma soruları · Hanoi kuleleri simülatörü · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.