Özyineleme

12.1Özyineleme nedir?

12.1.1Kendini çağıran metot

Metotlar birbirini çağırabilir. main bir metodu çağırır, o metot da başka bir metodu çağırabilir. Çağrılan metot işini bitirince denetim çağırana döner ve program kaldığı yerden devam eder. Java'da bir metodun çağırabileceği metotlar arasında kendisi de vardır. Bir metot kendi gövdesinde kendi adını kullanabilir.

Bu ilk bakışta tuhaf görünür: kendini çağıran metot hiç bitmeyecekmiş gibi gelir. Oysa her çağrı problemin biraz daha küçük bir hâliyle yapılırsa durum değişir. Problem küçüldükçe bir gün cevabı doğrudan bilinen kadar küçük hâle gelir. O noktada metot kendini çağırmaz, cevabı hemen döndürür. Bekleyen çağrılar da bu cevabı sırayla kullanarak kendi işlerini tamamlar.

Faktöriyel bu fikri iyi gösterir. Matematikte 4! = 4 × 3 × 2 × 1 = 24'tür. Aynı çarpım 4! = 4 × 3! biçiminde de yazılabilir. Yani 4!'i bulmak için önce 3!'i bulmak yeter. 3! için 2!, 2! için de 1! gerekir. 1! ise doğrudan bilinir: 1'dir. Şekil 12.1 bu iç içe yapıyı gösterir. Her kutunun içinde bir öncekinin daha küçük bir kopyası vardır. En içteki kutu kendi içinde yeni bir kutu açmaz.

Her çağrı kendi parametreleri ve kendi yerel değişkenleriyle çalışır. faktoriyel(4) çağrısındaki n ile faktoriyel(3) çağrısındaki n aynı adı taşır ama ayrı değişkenlerdir. Biri 4, öteki 3 değerini tutar. Java her çağrı için bellekte ayrı bir alan açar. Bu alana yığın çerçevesi denir. Çerçeveler, açılış sırasıyla üst üste dizilir. Çerçevelerin oluşturduğu bu yapı da çağrı yığınıdır. Çağrı yığını özyinelemeyi anlamanın anahtarıdır ve notun büyük bölümünde kullanılır.

12.1.2İki zorunlu parça

Doğru çalışan her özyinelemeli metotta iki parça bulunur. Biri, cevabın doğrudan bilindiği durumdur. Öteki, problemi küçültüp metodun kendisini yeniden çağırdığı durumdur.

Şekil 12.2 bu iki parçanın bir çağrıdaki sırasını gösterir. Çağrı başlayınca önce taban durum sorulur. Cevap “evet” ise sonuç hemen döndürülür. Cevap “hayır” ise problem küçültülür ve yeni bir çağrı yapılır. Yeni çağrı da aynı soruyla başlar.

İki parçadan biri eksik olursa metot doğru çalışmaz. Taban durum yoksa çağrılar hiç durmaz. Her çağrı yeni bir çerçeve açar ve bir süre sonra bellek dolar. Taban durum varsa ama problem her çağrıda ona yaklaşmıyorsa sonuç yine aynıdır. Örneğin return n * faktoriyel(n); satırında n hiç küçülmez. Taban duruma hiç ulaşılmaz.

Bu yüzden bir özyinelemeli metot yazılırken üç soru sorulur:

1. Taban durum nedir? Cevabı hesaplamadan bilinen en küçük girdi hangisidir? Faktöriyelde n ≤ 1'dir.
2. Problem nasıl küçülür? Hangi ölçü her çağrıda azalır? Faktöriyelde n her çağrıda 1 azalır.
3. Küçük cevap büyük cevaba nasıl dönüşür? Alt çağrının sonucuyla ne yapılır? Faktöriyelde alt sonuç n ile çarpılır.

İkinci sorunun cevabı aynı zamanda metodun biteceğinin gerekçesidir. n bir tam sayıdır ve her çağrıda 1 azalır. 4'ten başlayan bir n en çok üç adımda 1'e iner. Azalan bir tam sayı, alttan sınırlı bir değere sonlu sayıda adımda ulaşır. Taban durumun ulaşılabilir olduğu böyle gösterilir.

12.1.3Özyinelemeli düşünme

Özyinelemeli bir metodu yazarken bütün çağrıları akılda canlandırmak gerekmez. Bunun yerine şöyle düşünülür: “Metot, kendisinden daha küçük her girdi için zaten doğru çalışıyor. Bu varsayımla, verilen girdinin cevabını nasıl kurarım?” Faktöriyel için cevap kısadır. faktoriyel(n − 1) doğru sonucu veriyorsa n! bu sonucun n katıdır.

Bu düşünme biçimi matematikteki tümevarıma benzer. Tümevarımda önce en küçük durum için iddia gösterilir. Sonra iddia k için doğruysa k + 1 için de doğru olduğu gösterilir. Taban durum, tümevarımın başlangıç adımına; özyinelemeli durum da tümevarım adımına karşılık gelir. İki adım birlikte doğruysa metot her geçerli girdi için doğru sonuç verir.

Yine de yeni başlayan biri için en güvenli yol, küçük bir girdiyle metodu elle izlemektir. Hangi çağrının ne zaman açıldığı, neyi beklediği ve ne döndürdüğü bir tabloya yazılır. Notun geri kalanında hemen her örnek böyle bir tabloyla izlenir. Tabloların hepsi, metotlara çağrı ve dönüş anlarını kaydeden satırlar eklenerek JDK 21'de üretilmiştir.

12.2Faktöriyel ve çağrı yığını

12.2.1Özyinelemeli faktöriyel

Faktöriyelin matematiksel tanımı iki satırdır: 0! = 1! = 1 ve n! = n × (n − 1)!. Negatif sayıların faktöriyeli tanımlı değildir. Java metodu bu tanımı neredeyse aynen izler:

static long faktoriyel(int n) {
    if (n < 0)
        throw new IllegalArgumentException();
    if (n <= 1) return 1;
    return n * faktoriyel(n - 1);
}

Metot satır satır şöyle çalışır:

1. static long faktoriyel(int n): metot bir int alır ve long döndürür. Faktöriyel çok hızlı büyüdüğü için sonuç türü long seçilmiştir. int en çok 12!'i tutabilir; long 20!'e kadar yeter.
2. if (n < 0) throw new IllegalArgumentException();: negatif girdi geçersizdir. Metot bu durumda bir hata nesnesi fırlatır ve çalışmayı keser. Fırlatma (throw), metodun “bu girdiyle iş yapamam” demesinin Java'daki yoludur.
3. if (n <= 1) return 1;: taban durum. 0 ve 1 için sonuç 1'dir; yeni çağrı yapılmaz.
4. return n * faktoriyel(n - 1);: özyinelemeli durum. Önce faktoriyel(n − 1) çağrılır. Bu çağrı bitip bir değer döndürünce o değer n ile çarpılır ve sonuç döndürülür.

Son satırdaki sıra önemlidir. Çarpma, alt çağrının sonucu gelmeden yapılamaz. Bu yüzden faktoriyel(4) çarpmayı yarıda bırakıp bekler. faktoriyel(3) çağrısı da aynı biçimde bekler. Çarpmaların hepsi dönüş yolunda yapılır.

Şekil 12.3 girdinin hangi bölgeye düştüğüne göre metodun ne yaptığını sayı doğrusu üzerinde gösterir. Negatif sayılar hata bölgesindedir. 0 ve 1 taban durumdur. 2 ve üstü özyinelemeli bölgededir; her çağrı bir adım sola kayar ve sonunda taban duruma girer.

Metot birkaç girdiyle çalıştırıldığında beklenen sonuçlar alınır. Aşağıdaki çıktının ilk satırı faktoriyel(4), faktoriyel(0), faktoriyel(1) ve faktoriyel(20) değerleridir. İkinci satır, faktoriyel(−3) çağrısının fırlattığı hatanın yakalanıp yazdırılmasıdır:

24 1 1 2432902008176640000
faktoriyel(-3): java.lang.IllegalArgumentException

12.2.2faktoriyel(4)'ü adım adım izlemek

Sunumdaki izleme slaydı aşağıdaki programı kullanır. main metodu faktoriyel(4)'ü çağırır ve sonucu yazdırır:

static long faktoriyel(int n) {
    if (n < 0)
        throw new IllegalArgumentException();
    if (n <= 1) return 1;
    return n * faktoriyel(n - 1);
}
System.out.println(faktoriyel(4));

24

Çalışma sırasında çağrı yığınında neler olduğu Tablo 12.1'de adım adım verilmiştir. “Çerçeve sayısı” sütunu, o anda yığında bulunan çerçevelerin sayısıdır; main'in çerçevesi de bu sayıya dahildir.

Tablonun ilk dört satırı açılış evresidir. faktoriyel(4) çağrılır ve bir çerçeve açılır. Bu çerçevede n = 4'tür. 4 < 0 ve 4 ≤ 1 yanlış olduğundan son satıra gelinir. Çarpma için faktoriyel(3)'ün sonucu gerekir; bu çerçeve bekleyişe geçer ve yeni bir çağrı yapılır. Aynı şey n = 3 ve n = 2 için tekrarlanır. 4. adımda faktoriyel(1) çağrılır. Bu çerçevede 1 ≤ 1 doğrudur: taban duruma ulaşılmıştır.

Yığın bu anda en derin hâlindedir. main ve dört faktoriyel çerçevesiyle toplam 5 çerçeve vardır. Hiçbir çarpma henüz yapılmamıştır. Her çerçeve kendi n değerini saklayarak üstündeki çağrının sonucunu bekler. Şekil 12.4'ün üst kısmı bu anı gösterir.

5. adımdan sonra dönüş evresi başlar. faktoriyel(1) 1 döndürür ve çerçevesi silinir. Denetim faktoriyel(2)'nin çerçevesine geçer. Bu çerçeve beklediği değeri almıştır: 2 × 1 = 2 hesaplanır ve döndürülür. faktoriyel(3) bu değerle 3 × 2 = 6, faktoriyel(4) de 4 × 6 = 24 hesaplar. En sonunda main 24'ü yazdırır.

Bu izlemeden iki sonuç çıkar. Birincisi, çerçeveler açıldıkları sıranın tersine kapanır. En son açılan faktoriyel(1) ilk kapanır; ilk açılan faktoriyel(4) en son kapanır. Bu davranış “son giren ilk çıkar” (last in, first out, LIFO) kuralıdır. Yığın veri yapısının adı da buradan gelir. İkincisi, faktoriyel(n) çağrısında yığında aynı anda n tane faktoriyel çerçevesi bulunur. Ek bellek n ile doğru orantılı büyür; yani O(n)'dir. faktoriyel(20) için sayaçlı bir sürüm 20 çağrı ve 20 çerçevelik en büyük derinlik ölçmüştür.

12.2.3Açılım ve dönüş

Özyinelemeli bir hesap iki evrede düşünülebilir. Şekil 12.5'te sol sütun açılım evresidir: çağrılar aşağı doğru açılır ve yığın büyür. Sağ sütun dönüş evresidir: değerler yukarı doğru taşınır ve yığın küçülür.

Açılım evresinde her çağrı yalnızca bir soru sorar ve bir sonraki çağrıyı başlatır. Asıl hesap dönüş evresinde yapılır. Bu ayrım, özyinelemeli bir metodun çıktısını tahmin ederken çok işe yarar. Bir yazdırma deyimi özyinelemeli çağrıdan önceyse açılım sırasında çalışır. Çağrıdan sonraysa dönüş sırasında, yani ters sırada çalışır. Aynı metot, yazdırma satırının yeri değiştirilerek bir sayının rakamlarını düz ya da ters sırada yazdırabilir.

static void g(int n) {
    if (n <= 0) return;
    System.out.print(n + " ");
    g(n - 2);
    System.out.print(n + " ");
}

12.3Tek çağrılı örnekler

Faktöriyelde her çağrı en çok bir yeni çağrı yapar. Böyle metotların çağrıları tek bir zincir oluşturur: f(4) → f(3) → f(2) → f(1). Bu biçime doğrusal özyineleme denir. Bu kesimdeki beş örnek de doğrusaldır. Her birinde aynı üç soru sorulur: taban durum nedir, problem nasıl küçülür, alt sonuç nasıl kullanılır?

12.3.11'den n'ye toplam

1'den n'ye kadar sayıların toplamı da faktöriyel gibi tanımlanabilir. toplam(n), n ile toplam(n − 1)'in toplamıdır. Hiç sayı yoksa toplam 0'dır: toplam(0) = 0. Böylece toplam(3) = 3 + toplam(2) = 3 + 2 + toplam(1) = 3 + 2 + 1 + toplam(0) = 6 olur.

static int toplam(int n) {
    if (n <= 0) return 0;
    return n + toplam(n - 1);
}
System.out.println(toplam(3));

6

Taban durum n <= 0 biçiminde yazılmıştır. Bu seçim negatif girdilerde de metodu güvenli kılar. toplam(−5) çağrısı ilk denetimde taban duruma girer ve 0 döndürür. Koşul n == 0 olsaydı toplam(−5) çağrısında n −6, −7 … diye iner ve hiç durmazdı.

Tablo 12.2 faktöriyel izlemesine çok benzer. Açılımda dört toplam çerçevesi açılır: toplam(3), toplam(2), toplam(1) ve toplam(0). En derin anda main ile birlikte 5 çerçeve vardır. toplam(0) 0 döndürür. Dönüşte sırasıyla 1 + 0 = 1, 2 + 1 = 3 ve 3 + 3 = 6 hesaplanır. Sonuç 6 = 3 + 2 + 1 + 0'dır.

toplam(n) metodu n + 1 çağrı yapar ve yığın n + 1 çerçeve derinleşir. Zaman da ek bellek de O(n)'dir. Aynı toplam n(n + 1)/2 formülüyle tek adımda bulunabilir. Bu örnek özyinelemenin mekanizmasını göstermek için seçilmiştir; toplamı hesaplamanın en iyi yolu değildir.

12.3.2Rakamlar toplamı ve yardımcı metot

Bir sayının rakamları toplamı da özyinelemeyle yazılabilir. Fikir rakam kalıbına dayanır: n % 10 son rakamı verir, n / 10 son rakamı atar. 472'nin rakamları toplamı, son rakam 2 ile 47'nin rakamları toplamının toplamıdır. Tek basamaklı bir sayının rakamları toplamı kendisidir. Bu cümleler metodun taban durumunu ve özyinelemeli durumunu birlikte verir.

static int rakamToplami(int n) {
    long m = Math.abs((long) n);
    return rakamToplamiPozitif(m);
}
static int rakamToplamiPozitif(long n) {
    if (n < 10) return (int) n;
    return (int) (n % 10)
        + rakamToplamiPozitif(n / 10);
}
System.out.println(rakamToplami(472));

Program 13 yazar. Kodda iki metot vardır. İşi asıl yapan rakamToplamiPozitif'tir ve yalnızca negatif olmayan sayılarla doğru çalışır. rakamToplami ise dışarıdan çağrılan metottur. Girdiyi hazırlar ve asıl işi yardımcı metoda bırakır. Böyle metotlara yardımcı metot (helper method) denir.

Hazırlık adımı neden gereklidir? Negatif bir sayıda n % 10 negatif çıkar. Örneğin Java'da −472 % 10 = −2'dir. Ayrıca −472 < 10 doğru olduğu için metot hemen taban duruma girer ve −472 döndürür. Bunu önlemek için önce mutlak değer alınır. Mutlak değer neden long'a çevrildikten sonra alınır? int'in en küçük değeri −2 147 483 648'dir; int'in en büyük değeri ise 2 147 483 647'dir. Math.abs(Integer.MIN_VALUE) bu yüzden int'e sığmaz ve yine −2 147 483 648 döner. Math.abs((long) n) ise 2 147 483 648 değerini doğru verir. Yardımcı metot bu nedenle long parametre alır.

Program birkaç uç girdiyle de çalıştırılmıştır. Çıktının ikinci satırı rakamToplami(−472), rakamToplami(0) ve rakamToplami(Integer.MIN_VALUE) sonuçlarıdır:

13
13 0 47

Son değer 47'dir: 2 + 1 + 4 + 7 + 4 + 8 + 3 + 6 + 4 + 8 = 47. Mutlak değer int ile alınsaydı metot negatif bir sayıyla taban duruma girer ve yanlış sonuç döndürürdü.

Tablo 12.3 her çerçevenin hangi rakamı beklettiğini gösterir. 472'nin çerçevesi 2'yi, 47'nin çerçevesi 7'yi bekletir. 4 tek basamaklıdır ve taban durumdur. Dönüşte 7 + 4 = 11, ardından 2 + 11 = 13 hesaplanır. Yardımcı metot 13 döndürür ve rakamToplami bu değeri aynen iletir.

Yığın derinliği sayının basamak sayısı kadardır. Basamak sayısı, sayının büyüklüğüyle logaritmik büyür: 10 basamaklı bir int en çok 10 yardımcı çerçeve açar. Bu yüzden rakam problemlerinde yığın taşması kaygısı yoktur.

12.3.3Palindrom kontrolü

Palindrom, tersten okunuşu düz okunuşuyla aynı olan dizgidir: “kayak”, “ana”, “abba” gibi. Bir dizginin palindrom olup olmadığı iki uçtan içe doğru ilerlenerek anlaşılır. İlk ve son karakter farklıysa dizgi palindrom değildir. Aynıysa bu iki karakter atılır ve kalan iç dizgi aynı soruyla denetlenir. Ortada tek karakter ya da hiç karakter kalmadıysa dizgi palindromdur.

static boolean palindrom(String s,
                         int sol, int sag) {
    if (sol >= sag) return true;
    if (s.charAt(sol) != s.charAt(sag))
        return false;
    return palindrom(s, sol + 1, sag - 1);
}
System.out.println(palindrom("kayak", 0, 4));

Metot dizginin kopyasını oluşturmaz. Bunun yerine bakılacak bölgeyi iki indisle tanımlar: sol ve sag. Her çağrıda sol 1 artar, sag 1 azalır. Problemin ölçüsü bölgenin uzunluğudur: sag − sol + 1. Bu uzunluk her çağrıda 2 azalır ve sonunda 1 ya da 0 olur. Taban durum sol >= sag bu iki durumu birlikte kapsar.

Metodun iki ayrı çıkışı vardır. Uçlar farklıysa false döner; bu da bir taban durum sayılır, çünkü yeni çağrı yapılmaz. Uçlar eşitse son satırdaki çağrının sonucu aynen döndürülür. Dönüş yolunda yapılan bir hesap yoktur.

Tablo 12.4'e göre “kayak” için üç çağrı yapılır. 0. ve 4. karakterler 'k', 1. ve 3. karakterler 'a'dır. Üçüncü çağrıda 2 ≥ 2 doğrudur: ortada yalnız 'y' kalmıştır ve true döner. Bu değer iki çerçeveden geçerek main'e ulaşır. “kitap” için tek bir çağrı yeter. İlk karakter 'k', son karakter 'p'dir; metot hemen false döndürür. Program ek girdilerle de çalıştırılmıştır. Aşağıdaki ikinci satır sırasıyla "kitap", "abba" ve "a" sonuçlarıdır:

true
false true true

Çift uzunluklu "abba" dizgisinde iç bölge sonunda boşalır: palindrom(s, 2, 1) çağrısında 2 ≥ 1 doğrudur. Taban durumun eşitlik yerine >= ile yazılması bu durumu da yakalar. n karakterlik bir dizgi için en çok ⌊n/2⌋ + 1 çağrı yapılır; zaman ve yığın derinliği O(n)'dir.

12.3.4Öklid algoritmasıyla EBOB

İki sayının en büyük ortak böleni (EBOB), ikisini de kalansız bölen en büyük sayıdır. EBOB(48, 18) = 6'dır. Öklid algoritması bu sayıyı bölme kalanlarıyla bulur. Dayandığı kural şudur: b sıfırdan farklıysa EBOB(a, b) = EBOB(b, a mod b)'dir. b = 0 ise EBOB(a, 0) = |a|'dır. Bu iki satır özyinelemeli bir metodu doğrudan tarif eder.

static int ebob(int a, int b) {
    if (b == 0) return Math.abs(a);
    return ebob(b, a % b);
}
System.out.println(ebob(48, 18));

Kural neden doğrudur? a ile b'yi bölen her sayı a − k·b farkını da böler. a mod b de böyle bir farktır. Tersine, b ile a mod b'yi bölen her sayı a'yı da böler. Yani (a, b) ve (b, a mod b) çiftlerinin ortak bölenleri aynıdır. Ortak bölenleri aynı olan iki çiftin en büyük ortak böleni de aynıdır.

Tablo 12.5 dört çağrıyı gösterir. 48 % 18 = 12, 18 % 12 = 6 ve 12 % 6 = 0'dır. ebob(6, 0) taban durumdur ve 6 döndürür. Bu değer üç çerçeveden geçerek aynen geri gelir. Son sıfırdan farklı kalan, yani 6, aranan EBOB'dur.

Metot farklı girdilerle de denenmiştir. Aşağıdaki ikinci satır ebob(18, 48), ebob(17, 5), ebob(−12, 8) ve ebob(7, 0) sonuçlarıdır:

6
6 1 4 7

ebob(18, 48) çağrısında ilk adım sayıların yerini değiştirir: 18 % 48 = 18 olduğundan sonraki çağrı ebob(48, 18)'dir. Bu yüzden sayaçlı sürüm bu girdide 5 çağrı sayar, ebob(48, 18)'de ise 4. Taban durumdaki Math.abs negatif girdilerde sonucu pozitif yapar: ebob(−12, 8) = 4'tür.

Öklid algoritması çok hızlıdır. Kalanlar her iki adımda en az yarıya iner. Bu yüzden çağrı sayısı sayıların basamak sayısıyla orantılıdır. En kötü durum ardışık iki Fibonacci sayısıyla ortaya çıkar. int'e sığan en büyük ardışık Fibonacci çifti olan 1 134 903 170 ve 701 408 733 için bile sayaçlı sürüm yalnızca 44 çağrı saymıştır.

12.3.5Dizgiyi ters çevirme

Bir dizginin tersi de özyinelemeyle tanımlanabilir. “abc” dizgisinin tersi, “bc”nin tersinin sonuna 'a' eklenerek bulunur. Uzunluğu 0 ya da 1 olan dizginin tersi kendisidir.

static String ters(String s) {
  if (s.length() <= 1) return s;
  return ters(s.substring(1)) + s.charAt(0);
}
System.out.println(ters("abc"));

s.substring(1) ilk karakter hariç kalan dizgiyi verir. s.charAt(0) ilk karakterdir. Alt çağrı kalanın tersini döndürür; ilk karakter bu sonucun sonuna eklenir. Toplama bir String ile bir char arasında yapıldığı için sonuç yine String'dir.

Program boş dizgi, “kayak” ve “Java” ile de çalıştırılmıştır:

cba
[] kayak avaJ

Boş dizginin tersi boş dizgidir; köşeli ayraçlar bunu görünür kılmak için yazdırılmıştır. “kayak” palindrom olduğu için tersi kendisiyle aynıdır.

Bu metot kısa ve okunaklıdır ama verimli değildir. Her çağrı substring ile yeni bir alt dizgi üretir. n karakterlik bir dizgi için üretilen alt dizgilerin toplam uzunluğu yaklaşık n(n + 1)/2'dir. Sayaçlı sürüm 1000 karakterlik bir dizgi için 1000 çağrı ve toplam 500 500 karakterlik alt dizgi saymıştır. Zaman O(n²)'dir. Döngüyle ve StringBuilder ile ters çevirme O(n)'de yapılır. Bir çözümün kısa olması, ucuz olduğu anlamına gelmez.

12.4Üs alma

12.4.1Düz özyinelemeli üs

Bir tabanın n'inci kuvveti, tabanın n kez kendisiyle çarpımıdır. Bu tanım da özyinelemeli yazılabilir: tabanⁿ = taban × tabanⁿ⁻¹ ve taban⁰ = 1. Örneğin 2⁴ = 2 × 2³'tür.

static long us(long taban, int n) {
  if (n == 0) return 1;
  return taban * us(taban, n - 1);
}
System.out.println(us(2, 4));

16

Yapı faktöriyelle aynıdır. Taban durum n == 0'dır. Özyinelemeli durumda n 1 azalır ve alt sonuç taban ile çarpılır. Taban her çağrıda aynı kalır; yalnızca üs küçülür.

us(2, 4) çağrısında us(2, 3), us(2, 2), us(2, 1) ve us(2, 0) çağrıları açılır. us(2, 0) taban durumdur ve 1 döndürür. Tablo 12.7 dönüş yolundaki çarpmaları verir: 2, 4, 8 ve 16. Toplam n + 1 = 5 çağrı yapılır. us(2, 10) için bu sayı 11'dir. Zaman ve yığın derinliği O(n)'dir.

Metot negatif üsle çağrılırsa ne olur? us(2, −1) çağrısında n −1'dir ve −1 == 0 yanlıştır. Sonraki çağrıda n −2, sonra −3 olur. n sıfırdan uzaklaşır ve taban duruma hiç ulaşılmaz. Çağrılar yığın dolana kadar sürer. Bu durum 12.11.2'de ölçülerek ele alınır.

12.4.2Hızlı üs

Düz yöntem 2¹⁰ için 10 çarpma yapar. Oysa 2¹⁰ = (2⁵)²'dir. 2⁵ bir kez hesaplanıp kendisiyle çarpılırsa iş yarıya iner. Aynı fikir 2⁵ için de kullanılabilir. Üs tek olduğundan bir taban fazladan çarpılır: 2⁵ = (2²)² × 2. Her adımda üs yarıya indiği için çağrı sayısı çok azalır. Bu yönteme hızlı üs ya da karesini alarak üs alma denir.

static long hizliUs(long taban, int us) {
  if (us == 0) return 1;
  long yarim = hizliUs(taban, us / 2);
  if (us % 2 == 0) return yarim * yarim;
  return yarim * yarim * taban;
}
System.out.println(hizliUs(2, 10));

Metot önce us / 2 ile kendini çağırır ve sonucu yarim değişkenine koyar. Java'da iki int'in bölümü tam sayıdır; 5 / 2 = 2'dir. Üs çiftse sonuç yarim × yarim'dır. Üs tekse bölmede 1 kaybolmuştur ve sonuç bir kez daha tabanla çarpılır.

yarim değişkeni bu metodun en önemli ayrıntısıdır. Kod return hizliUs(taban, us / 2) * hizliUs(taban, us / 2); biçiminde yazılsaydı aynı alt problem iki kez hesaplanırdı. Her çağrı iki çağrı yapar ve kazanç tamamen kaybolurdu. Alt sonucu bir kez hesaplayıp yerel değişkende saklamak, yöntemi hızlı yapan şeydir.

Açılımda üs 10, 5, 2, 1 ve 0 olur. hizliUs(2, 0) 1 döndürür. Tablo 12.8 dönüş yolunu gösterir. Üs 1 tektir: 1 × 1 × 2 = 2. Üs 2 çifttir: 2 × 2 = 4. Üs 5 tektir: 4 × 4 × 2 = 32. Üs 10 çifttir: 32 × 32 = 1024. Toplam 5 çağrı yapılmıştır; düz yöntem 11 çağrı yapardı.

Çağrı sayısı üssün ikili gösterimindeki basamak sayısına bağlıdır. 1 ve üstü bir üs için çağrı sayısı ⌊log₂ us⌋ + 2'dir. Sayaçlı sürümün ölçümleri bu formülle uyuşur:

Milyonuncu kuvvet için düz yöntem bir milyon çağrı yapar; varsayılan yığın boyutunda bu, yığın taşmasına yol açar. Hızlı üs yalnızca 21 çağrı yapar. Zaman ve yığın derinliği O(log n)'dir. Program hizliUs(3, 16) = 43 046 721 ve hizliUs(2, 62) = 4 611 686 018 427 387 904 değerlerini de doğru hesaplamıştır:

1024
43046721 4611686018427387904

Sonuçların long'a sığması gerekir. 2⁶³ long'un sınırını aşar; hizliUs(2, 63) çağrısı hata vermeden −9 223 372 036 854 775 808 döndürür. Taşma, metodun hızından bağımsız bir sorundur.

12.5Böl ve fethet

Hızlı üs bir problemi yarı büyüklükte bir probleme indirir. Bu fikrin genel adı böl ve fethettir (divide and conquer). Problem iki ya da daha çok küçük parçaya bölünür. Parçalar aynı yöntemle, yani özyinelemeyle çözülür. Sonra parça çözümleri birleştirilerek asıl çözüm elde edilir. Parçalar yeterince küçülünce doğrudan çözülür; bu da taban durumdur.

12.5.1Özyinelemeli ikili arama

İkili arama sıralı bir dizide bir değeri arar. Aralığın ortasındaki öğeye bakılır. Aranan değer ortadakine eşitse arama biter. Ortadaki değer daha küçükse aranan değer sağ yarıdadır; daha büyükse sol yarıdadır. Bakılmayan yarı bir daha hiç incelenmez. Döngüyle yazılan ikili arama, özyinelemeyle de aynı adımlarla yazılabilir. Her çağrı aralığın yarısıyla kendini çağırır.

static int ara(int[] a, int x,
               int lo, int hi) {
  if (lo > hi) return -1;
  int mid = (lo + hi) / 2;
  if (a[mid] == x) return mid;
  if (a[mid] < x) return ara(a, x, mid + 1, hi);
  return ara(a, x, lo, mid - 1);
}
// a = {2, 5, 8, 12, 16, 23, 38, 56}
System.out.println(ara(a, 38, 0, 7));

Aralık iki indisle tanımlanır: lo alt sınır, hi üst sınırdır. İki taban durum vardır. lo > hi ise aralık boştur ve aranan değer dizide yoktur; metot −1 döndürür. a[mid] == x ise değer bulunmuştur ve indisi döner. Öteki iki satır aralığı yarıya indirir. Dizinin kendisi kopyalanmaz; bütün çağrılar aynı diziye bakar.

Programda dizi bir yorum satırıyla verilmiştir. Çalıştırılan sürümde dizi int[] a = {2, 5, 8, 12, 16, 23, 38, 56}; satırıyla tanımlanmıştır. Çıktının ikinci satırı 2, 56 ve 20 değerlerinin aranmasıdır:

6
0 7 -1

Tablo 12.10'a göre 38 üç çağrıda bulunur. İlk çağrıda mid = (0 + 7) / 2 = 3 ve a[3] = 12'dir. 12 < 38 olduğundan arama sağ yarıda sürer. İkinci çağrıda mid = 5 ve a[5] = 23'tür; arama yine sağa kayar. Üçüncü çağrıda mid = 6 ve a[6] = 38'dir: değer bulunmuştur. 6 iki çerçeveden geçerek main'e ulaşır.

Dizide olmayan bir değer arandığında aralık sonunda boşalır. Tablo 12.11 20'nin aranmasını gösterir. Dördüncü çağrıda lo = 5, hi = 4 olur; 5 > 4 doğrudur ve −1 döner.

Her çağrıda aralık yarıya indiği için n öğeli bir dizide en çok yaklaşık log₂ n + 1 çağrı yapılır. 8 öğeli dizide en kötü durum 4 çağrıdır: 56 ve 20 aramaları 4 çağrı sürmüştür. Zaman O(log n)'dir. Özyinelemeli sürümün ek yığın belleği de O(log n)'dir; döngülü sürüm aynı işi O(1) ek bellekle yapar.

12.5.2Birleştirme sıralaması

Birleştirme sıralaması (merge sort) böl ve fethet yönteminin tipik bir örneğidir. Dizi ortadan ikiye bölünür. Her yarı özyinelemeyle sıralanır. Sonra sıralı iki yarı tek bir sıralı dizide birleştirilir. Tek öğeli bir dizi zaten sıralıdır; bu da taban durumdur.

static void sirala(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int mid = (lo + hi) / 2;
    sirala(a, lo, mid);
    sirala(a, mid + 1, hi);
    int[] t = new int[hi - lo + 1];
    int i = lo, j = mid + 1, k = 0;
    while (i <= mid && j <= hi)
        t[k++] = a[i] <= a[j] ? a[i++] : a[j++];
    while (i <= mid) t[k++] = a[i++];
    while (j <= hi) t[k++] = a[j++];
    System.arraycopy(t, 0, a, lo, t.length);
}

Metot üç bölümden oluşur:

1. Taban durum: lo >= hi ise aralıkta en çok bir öğe vardır ve metot hemen döner.
2. Bölme: mid hesaplanır; sirala(a, lo, mid) sol yarıyı, sirala(a, mid + 1, hi) sağ yarıyı sıralar.
3. Birleştirme: t adlı geçici bir dizi açılır. i sol yarıda, j sağ yarıda ilerler. Her adımda iki yarının baştaki öğelerinden küçüğü t'ye yazılır. Yarılardan biri bitince ötekinin kalanı olduğu gibi eklenir. En sonda System.arraycopy t'yi dizinin ilgili bölgesine geri kopyalar.

a[i] <= a[j] karşılaştırmasındaki “küçük ya da eşit” bilinçli bir seçimdir. Eşit öğelerde soldaki önce yazılır. Böylece eşit değerlerin özgün sırası korunur. Bu özelliğe kararlılık denir. Birleştirme sıralaması kararlı bir sıralama yöntemidir.

Tablo 12.12 çağrıların gerçek sırasını verir. 1 numaralı çağrı diziyi [0..1] ve [2..3] diye böler. Sol yarı tamamen bitmeden sağ yarıya geçilmez. 2 numaralı çağrı [5, 2]'yi iki tek öğeye böler, ikisi de hemen döner, sonra birleştirme [2, 5] üretir. Dizi bu anda [2, 5, 4, 1] olur. Sağ yarı aynı biçimde [1, 4]'e dönüşür. En sonda 1 numaralı çağrı [2, 5] ile [1, 4]'ü birleştirir. Karşılaştırmalar 2 ile 1, 2 ile 4, 5 ile 4 arasındadır; sağ yarı bitince 5 eklenir. Sonuç [1, 2, 4, 5]'tir.

Program ayrıca 7 öğeli bir diziyi de sıralamıştır:

[1, 2, 4, 5]
[3, 9, 10, 27, 38, 43, 82]

Maliyet şöyle hesaplanır. Bölme sırasında dizinin boyu her düzeyde yarıya iner. n öğeli bir dizi yaklaşık log₂ n düzeyde tek öğelere ayrılır. Her düzeyde bütün parçaların birleştirilmesi toplam n öğe yazmayı gerektirir. Toplam iş düzey sayısı ile düzey başına işin çarpımıdır: O(n log n). Birleştirme için geçici dizi kullanıldığı için ek bellek O(n)'dir. Yığın derinliği ise yalnızca O(log n)'dir. Sayaçlı sürüm ters sıralı 1024 öğelik dizi için 2047 çağrı, en çok 11 çerçeve derinlik ve 5120 karşılaştırma saymıştır. 5120 = 512 × 10, yani (n/2) · log₂ n'dir.

Karşılaştırma için: seçme ya da kabarcık sıralaması gibi iç içe iki döngüyle çalışan yöntemler yaklaşık n²/2 karşılaştırma yapar. 1024 öğe için bu yaklaşık 520 bin karşılaştırma demektir. Birleştirme sıralaması aynı diziyi yüz kat daha az karşılaştırmayla sıralar.

12.6İki çağrılı özyineleme

Şimdiye kadarki örneklerin çoğunda her çağrı en çok bir yeni çağrı yaptı. Birleştirme sıralaması ise iki çağrı yapar: biri sol yarı, biri sağ yarı için. Her çağrının iki çağrı yaptığı metotlarda çağrılar bir zincir değil, bir ağaç oluşturur. Bu ağaca özyineleme ağacı (recursion tree) denir. Ağacın kökü ilk çağrıdır; her düğümün çocukları o çağrının yaptığı alt çağrılardır. Hanoi kuleleri ve alt küme üretimi bu yapının iki klasik örneğidir.

12.6.1Hanoi kuleleri

Hanoi kuleleri bir bulmacadır. Üç çubuk vardır: A, B ve C. A çubuğunda büyükten küçüğe dizilmiş n disk bulunur. Amaç bütün diskleri C çubuğuna taşımaktır. İki kural vardır: bir hamlede yalnızca bir disk, o da bir çubuğun en üstündeki disk taşınabilir. Büyük bir disk küçük bir diskin üstüne konamaz.

Bulmaca ilk bakışta zordur ama özyinelemeli çözümü üç satırdır. n diski A'dan C'ye taşımak için önce üstteki n − 1 disk B'ye taşınır. Bu sırada C yardımcı çubuk olarak kullanılır. Sonra A'da yalnız kalan en büyük disk C'ye taşınır. En son B'deki n − 1 disk, A yardımcı olarak kullanılarak C'ye taşınır. n − 1 diski taşımak aynı problemin küçük bir örneğidir. Hiç disk yoksa yapılacak bir şey yoktur.

static void hanoi(int n, char kaynak,
                  char hedef, char ara) {
  if (n == 0) return;
  hanoi(n - 1, kaynak, ara, hedef);
  System.out.print(kaynak + "->" + hedef + " ");
  hanoi(n - 1, ara, hedef, kaynak);
}
hanoi(3, 'A', 'C', 'B');

A->C A->B C->B A->C B->A B->C A->C 

Metodun dört parametresi vardır: disk sayısı, kaynak çubuk, hedef çubuk ve yardımcı (ara) çubuk. Birinci özyinelemeli çağrıda hedef ile ara yer değiştirir: n − 1 disk ara çubuğa gider. İkinci çağrıda kaynak ile ara yer değiştirir: n − 1 disk ara çubuktan hedefe gider. Yazdırma deyimi iki çağrının arasındadır. Bu yüzden bir hamle, sol alt ağaç bütünüyle bittikten sonra yazılır.

Tablo 12.13 yedi hamleyi ve her hamleyi hangi çağrının yaptığını gösterir. Disk 1 en küçük, disk 3 en büyük disktir. İlk üç hamle üstteki iki diski B'ye taşır. 4. hamle en büyük diski C'ye götürür; bu hamleyi en dıştaki hanoi(3, A, C, B) çağrısı yapar. Son üç hamle B'deki iki diski C'ye taşır. Disk 1 her iki hamlede bir hareket eder: 1., 3., 5. ve 7. hamleler onundur. Şekil 12.15 dört anı gösterir.

Hamle sayısı da özyinelemeyle bulunur. h(n), n diski taşımak için gereken hamle sayısı olsun. Çözüm iki kez n − 1 disk taşır ve bir kez de en büyük diski taşır: h(n) = 2·h(n − 1) + 1, h(0) = 0. Buradan h(1) = 1, h(2) = 3, h(3) = 7, h(4) = 15 ve h(5) = 31 bulunur. Genel formül h(n) = 2ⁿ − 1'dir. Formül tümevarımla doğrulanır: 2·(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 1.

Tablo 12.14 iki farklı büyüme gösterir. Hamle ve çağrı sayısı üsteldir: her disk eklendiğinde yaklaşık iki katına çıkar. Yığın derinliği ise doğrusaldır: n + 1. Hanoi'nin bu çözümü en iyisidir. n diski 2ⁿ − 1'den az hamleyle taşımak mümkün değildir. Çünkü en büyük disk bir kez hareket edecekse üstündeki n − 1 disk iki kez bütünüyle taşınmak zorundadır. Üstel büyüme algoritmanın değil, problemin kendisinin özelliğidir. 64 disk için gereken hamle sayısı 2⁶⁴ − 1 ≈ 1,8 × 10¹⁹'dur.

12.6.2Alt küme üretimi ve geri izleme

{1, 2} kümesinin dört alt kümesi vardır: {1, 2}, {1}, {2} ve boş küme. n öğeli bir kümenin 2ⁿ alt kümesi vardır. Bunun nedeni basittir: her öğe için iki seçenek vardır, ya alt kümeye dahil edilir ya da edilmez. n öğe için seçenekler çarpılır: 2 × 2 × … × 2 = 2ⁿ.

Bu “her öğe için iki seçenek” fikri özyinelemeli bir metoda dönüşür. Metot i'nci öğe için karar verir. Önce öğeyi listeye ekler ve kalan öğeler için kendini çağırır. Sonra öğeyi listeden çıkarır ve kalan öğeler için kendini yeniden çağırır. Bütün öğeler için karar verildiyse liste bir alt kümedir ve yazdırılır.

static void altKume(int[] a, int i,
                    List<Integer> sec) {
    if (i == a.length) {
        System.out.println(sec);
        return;
    }
    sec.add(a[i]);
    altKume(a, i + 1, sec);
    sec.remove(sec.size() - 1);
    altKume(a, i + 1, sec);
}
altKume(new int[]{1, 2}, 0, new ArrayList<>());

sec, o ana kadar seçilen öğeleri tutan bir listedir (List<Integer>). Bütün çerçeveler aynı liste nesnesini paylaşır; her çağrıya listenin kopyası değil, kendisi gider. sec.add(a[i]) öğeyi sona ekler. sec.remove(sec.size() - 1) son öğeyi çıkarır ve listeyi eklemeden önceki hâline döndürür. Bu çıkarma adımı olmasaydı ikinci çağrı, birinci çağrının eklediği öğeyi listede bulurdu.

Tablo 12.15 on adımda dört alt kümenin nasıl üretildiğini gösterir. 1. ve 2. adımlarda iki öğe de eklenir ve liste [1, 2] olur. 3. adımda i = 2'dir, yani dizinin sonuna gelinmiştir: [1, 2] yazdırılır. 4. adımda geri dönülür ve 2 çıkarılır. Liste [1] olur ve “2 hariç” dalı [1]'i yazdırır. 6. adımda i = 0 çerçevesine dönülür ve 1 de çıkarılır. Bundan sonra “1 hariç” dalları [2] ve [] alt kümelerini üretir.

Programın çıktısında önce iki öğeli kümenin, “--” satırından sonra da {1, 2, 3} kümesinin alt kümeleri vardır:

[1, 2]
[1]
[2]
[]
--
[1, 2, 3]
[1, 2]
[1, 3]
[1]
[2, 3]
[2]
[3]
[]

Çıktı sırası özyineleme ağacının soldan sağa gezilme sırasıdır. Her düzeyde önce “dahil” dalı, sonra “hariç” dalı çalışır. Bu yüzden ilk satır bütün öğeleri içeren küme, son satır boş kümedir.

Özyineleme ağacının her düzeyi bir öğeye karşılık gelir. n öğeli bir dizide ağacın 2ⁿ yaprağı ve toplam 2ⁿ⁺¹ − 1 düğümü vardır. Sayaçlı sürüm n = 2 için 7, n = 3 için 15, n = 10 için 2047 çağrı saymıştır. Yığın derinliği ise yalnızca n + 1'dir. Zaman O(2ⁿ)'dir; ama bu, 2ⁿ alt kümenin hepsini üretmek isteyen her yöntemin ödemek zorunda olduğu bedeldir.

12.7Çağrı yığını ve yığın taşması

12.7.1Yığın çerçevesinde neler saklanır?

Önceki örneklerin hepsinde çağrı yığını kullanıldı. Bu kesim, yığında tam olarak neyin saklandığını ve yığının neden sınırlı olduğunu açıklar. Bir metot başka bir metodu çağırdığında çağıran metodun işi yarıda kalır. İş daha sonra kaldığı yerden sürecektir. Bunun için üç bilgi saklanmalıdır:

1. Parametreler: çağrıya verilen değerler. faktoriyel(3) çerçevesinde n = 3'tür.
2. Yerel değişkenler: metodun içinde tanımlanan değişkenler. hizliUs'taki yarim ya da sirala'daki mid, i, j böyle değişkenlerdir.
3. Dönüş noktası: çağrılan metot bitince çağıran metotta hangi komuttan devam edileceği. faktoriyel(3) bittiğinde faktoriyel(4)'ün çerçevesinde çarpma işlemine dönülür.

Java sanal makinesi (Java Virtual Machine, JVM) bu bilgileri her çağrı için ayrı bir yığın çerçevesinde tutar. Çerçeveler, iş parçacığına ayrılmış yığın belleğinde üst üste durur. Yeni bir çağrı yapıldığında en üste bir çerçeve eklenir. Metot return ile bitince en üstteki çerçeve silinir ve denetim bir alttaki çerçeveye geçer. Çerçeveler bu yüzden ters sırada kapanır: son açılan ilk kapanır.

Yığın belleği sınırlıdır. Java'da her iş parçacığının yığını, program başlarken belirlenen sabit bir boyuttadır. 64 bitlik sistemlerde bu varsayılan boyut genellikle 1 MB'tır. Çerçeveler sınırı aşacak kadar çoğalırsa JVM yeni çerçeveye yer bulamaz ve bir hata fırlatır. Bu duruma yığın taşması denir.

Yığın taşmasının iki nedeni vardır. Birincisi sonsuz özyinelemedir: taban durum yoktur, yanlış yazılmıştır ya da problem küçülmez. İkincisi, doğru yazılmış ama çok derine inen özyinelemedir. Taban duruma ulaşılacaktır ama o ana kadar biriken çerçeveler yığına sığmaz. Doğrusal bir özyineleme, girdinin boyu kadar çerçeve açar. Bu yüzden büyük girdilerde doğru bir metot bile taşabilir.

12.7.2StackOverflowError

Sunumdaki en kısa örnek, hiçbir koşul içermeyen bir metottur:

static void sonsuz(int n) {
    sonsuz(n + 1);
}
sonsuz(0);

sonsuz(0) çağrısı hemen sonsuz(1)'i çağırır, o da sonsuz(2)'yi. Hiçbir çağrı dönmediği için hiçbir çerçeve silinmez. Şekil 12.18 bu birikmeyi gösterir. Yığın dolunca JVM bir StackOverflowError fırlatır. Hata yakalanmadığı için program biter ve hata metni standart hata akışına (stderr) yazılır. JDK 21'de çalıştırılan programın hata metninin ilk satırları şöyledir:

Exception in thread "main" java.lang.StackOverflowError
    at S19.sonsuz(S19.java:5)
    at S19.sonsuz(S19.java:5)
    at S19.sonsuz(S19.java:5)
    ...

Her “at” satırı yığındaki bir çerçeveyi gösterir: hangi sınıfın hangi metodunda ve kaynak dosyanın hangi satırında olduğu yazar. Satır numarası 5'tir, çünkü programda sonsuz metodu sınıfın 5. satırındaki çağrıyı yapar. Bu satırlar binlerce kez tekrarlanır. JVM hata metnine varsayılan olarak en çok 1024 çerçeve yazar; çalıştırılan programın hata metni de 1 başlık satırı ve 1024 “at” satırından oluşmuştur. Böyle bir hata metninde aynı satırın art arda tekrarlanması, sonsuz ya da çok derin özyinelemenin açık işaretidir.

Taşmanın kaç çağrıdan sonra olduğu sabit değildir. Çerçevenin boyu metodun parametre ve yerel değişken sayısına bağlıdır. JVM'in kodu yorumlayarak mı yoksa makine koduna derleyerek mi çalıştırdığı da çerçeve boyunu değiştirir. Aşağıdaki program taşma anına kadar yapılan çağrıları sayar. Hata catch ile yakalandığı için program bitmez ve sayıyı yazdırabilir:

// Varsayılan yığın boyutunda kaç çağrıda StackOverflowError oluştuğunu sayar (JVM'e ve koşullara göre değişir).
public class Derinlik {
    static int sayac;

    static void sonsuz(int n) {
        sayac++;
        sonsuz(n + 1);
    }

    static long us(long taban, int n) {
        sayac++;
        if (n == 0) return 1;
        return taban * us(taban, n - 1);
    }

    static int toplam(int n) {
        if (n <= 0) return 0;
        return n + toplam(n - 1);
    }

    public static void main(String[] args) {
        for (int k = 0; k < 3; k++) {
            sayac = 0;
            try {
                sonsuz(0);
            } catch (StackOverflowError e) {
                System.out.println("sonsuz: " + sayac + " cagri sonra " + e.getClass().getName());
            }
        }
        sayac = 0;
        try {
            us(2, -1);
        } catch (StackOverflowError e) {
            System.out.println("us(2, -1): " + sayac + " cagri sonra " + e.getClass().getSimpleName());
        }
        for (int n : new int[]{1000, 5000, 10000, 100000, 1000000}) {
            try {
                System.out.println("toplam(" + n + ") = " + toplam(n));
            } catch (StackOverflowError e) {
                System.out.println("toplam(" + n + "): StackOverflowError");
            }
        }
    }
}

Programın bir çalıştırmasındaki çıktı şöyledir:

sonsuz: 23539 cagri sonra java.lang.StackOverflowError
sonsuz: 62252 cagri sonra java.lang.StackOverflowError
sonsuz: 62252 cagri sonra java.lang.StackOverflowError
us(2, -1): 8079 cagri sonra StackOverflowError
toplam(1000) = 500500
toplam(5000) = 12502500
toplam(10000) = 50005000
toplam(100000): StackOverflowError
toplam(1000000): StackOverflowError

Aynı metot aynı programda üç kez denendiğinde ilk denemede yaklaşık 23 bin, sonrakilerde yaklaşık 62 bin çağrıdan sonra taşmıştır. Program birkaç kez daha çalıştırıldığında ilk denemenin sayısı 22 bin ile 27 bin arasında değişmiştir. Sayılar her çalıştırmada biraz farklı çıkabilir. Ama büyüklük sırası bellidir: varsayılan yığın boyutunda birkaç on bin çağrı. toplam(10 000) çalışır, toplam(100 000) taşar. Yığın boyutu java -Xss4m Program gibi bir seçenekle büyütülebilir. Bu sınırı yalnızca uzaklaştırır; derin özyineleme sorununu çözmez.

12.8Özyineleme mi döngü mü?

12.8.1Seçim ölçütleri

Özyinelemeyle yazılan her metot bir döngüyle de yazılabilir. Döngüyle yazılan her metot da özyinelemeyle yazılabilir. İkisi arasındaki seçim, hangisinin daha “güçlü” olduğuna değil, problemin yapısına ve maliyete bağlıdır.

Özyineleme, kendine benzeyen problemlerde doğal bir seçimdir. Ağaç biçimindeki veriler, dizin ve klasör yapıları, böl ve fethet algoritmaları ve geri izleme bu türdendir. Bu problemlerde özyinelemeli kod matematiksel tanıma çok yakındır ve kolay okunur. Hanoi ve alt küme üretimini döngüyle yazmak mümkündür. Ancak bunun için çağrı yığınının işini yapan bir yığın veri yapısını elle yönetmek gerekir.

Basit doğrusal tekrarlarda ise döngü üstündür. Faktöriyel, 1'den n'ye toplam ve rakamlar toplamı bir döngüyle aynı açıklıkta yazılır. Döngü tek bir çerçevede çalışır; her tur için yeni çerçeve açmaz. Ek yığın belleği O(1)'dir ve girdi ne kadar büyük olursa olsun yığın taşmaz. Çağrı yapmanın da küçük bir zaman maliyeti vardır: çerçeve açmak ve kapatmak döngünün bir turundan pahalıdır.

Seçim yalnızca kodun kısalığına bakılarak yapılmamalıdır. Üç ölçüt birlikte düşünülür: doğruluk, okunabilirlik ve kaynak kullanımı. Taban durumu ve küçülmesi açık bir özyinelemeli çözüm hata yapma olasılığını azaltabilir. Ama girdinin boyu on binleri aşabiliyorsa doğrusal özyineleme yığını tehlikeye sokar. Aynı alt problemi defalarca çözen bir özyineleme ise zamanı tehlikeye sokar; bu durum Fibonacci örneğinde ayrıntılı görülür.

12.8.2Döngülü faktöriyel

Faktöriyelin döngülü sürümü bir biriktiriciyle çalışır. sonuc 1'den başlar ve her turda sayaç i ile çarpılır:

static long faktoriyelDongu(int n) {
    long sonuc = 1;
    for (int i = 2; i <= n; i++)
        sonuc *= i;
    return sonuc;
}
System.out.println(faktoriyelDongu(4));

24

Tablo 12.17 üç turu gösterir. i = 2'de sonuc 2, i = 3'te 6, i = 4'te 24 olur. i = 5'te 5 ≤ 4 yanlıştır ve döngü biter. Döngünün i = 2'den başlaması bilinçlidir: 1 ile çarpmak sonucu değiştirmez. n = 0 ve n = 1 için döngü hiç dönmez ve 1 döndürülür; bu da 0! = 1! = 1 tanımıyla uyuşur.

Özyinelemeli sürümle karşılaştırıldığında hesap aynıdır: 2 × 3 × 4 = 24. Fark, çarpmaların sırası ve yığın kullanımındadır. Döngülü sürümde çarpmalar küçükten büyüğe, gidiş yolunda yapılır. Özyinelemeli sürümde büyükten küçüğe çağrılar açılır ve çarpmalar dönüş yolunda yapılır. Döngülü sürümde yığın hiçbir anda 2 çerçeveyi aşmaz. Çalışma sorularındaki while sürümü de aynı işi aynı maliyetle yapar; n = 0'dan 5'e kadar sonuçları 1, 1, 2, 6, 24 ve 120'dir.

12.9Fibonacci ve bellekleme

12.9.1Doğrudan Fibonacci

Fibonacci dizisi 0 ve 1 ile başlar. Sonraki her terim, kendinden önceki iki terimin toplamıdır: 0, 1, 1, 2, 3, 5, 8, 13, 21 … Tanım özyinelemelidir: fib(0) = 0, fib(1) = 1 ve fib(n) = fib(n − 1) + fib(n − 2). Java'ya doğrudan çevrilen metot şöyledir:

static long fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}
System.out.println(fib(4));

3

Metot tanımın kelimesi kelimesine karşılığıdır ve doğru sonuç verir. Ama faktöriyelden önemli bir farkı vardır: özyinelemeli durumda iki çağrı yapılır. Önce fib(n − 1) bütünüyle hesaplanır, sonra fib(n − 2). Çağrılar bir zincir değil, bir ağaç oluşturur.

Tablo 12.18 dokuz çağrının sırasını verir. fib(4), fib(3)'ü çağırır; fib(3), fib(2)'yi; fib(2) de fib(1)'i. fib(1) ve fib(0) taban durumdur. fib(2) = 1 + 0 = 1 hesaplanır. fib(3) sağ terimi için fib(1)'i çağırır ve 1 + 1 = 2 bulur. Sonra fib(4) sağ terimi için fib(2)'yi çağırır. 7 numaralı bu çağrı, 3 numaralı çağrının yaptığı işin aynısını baştan yapar. fib(2) iki kez, fib(1) üç kez, fib(0) iki kez hesaplanır. Sonuç 3 olsa da 9 çağrı yapılmıştır. Yığın derinliği ise en çok 4'tür: aynı anda yalnızca kökten yaprağa giden bir yolun çerçeveleri açıktır.

n büyüdükçe tekrar hızla artar. Şekil 12.22 fib(5) ağacını gösterir. 15 çağrı yapılır: f(3) 2 kez, f(2) 3 kez, f(1) 5 kez, f(0) 3 kez hesaplanır. Ağacın sağ yarısındaki f(3) alt ağacı, sol yarıdaki f(4) alt ağacının içinde zaten vardır. fib(n − 1) ve fib(n − 2) alt ağaçları büyük ölçüde örtüşür.

12.9.2Çağrı sayısının büyümesi

Çağrı sayısı en güvenilir biçimde sayılarak bulunur. Aşağıdaki programda metoda bir sayaç eklenmiştir. Her çağrı sayacı 1 artırır:

public class FibSayac {
    static long cagri = 0;

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

    public static void main(String[] args) {
        for (int n : new int[]{5, 10, 20, 30}) {
            cagri = 0;
            long sonuc = fib(n);
            System.out.println("fib(" + n + ") = " + sonuc + ", çağrı sayısı = " + cagri);
        }
    }
}

fib(5) = 5, çağrı sayısı = 15
fib(10) = 55, çağrı sayısı = 177
fib(20) = 6765, çağrı sayısı = 21891
fib(30) = 832040, çağrı sayısı = 2692537

Sayılar bir formülle de bulunabilir. ç(n), fib(n) için yapılan çağrı sayısı olsun. İlk çağrı 1 sayılır; ona iki alt ağacın çağrıları eklenir: ç(n) = 1 + ç(n − 1) + ç(n − 2), ç(0) = ç(1) = 1. Buradan ç(2) = 3, ç(3) = 5, ç(4) = 9, ç(5) = 15 ve ç(6) = 25 bulunur. Bu yineleme bağıntısının çözümü ç(n) = 2·fib(n + 1) − 1'dir. Örneğin fib(11) = 89 olduğundan ç(10) = 177'dir.

Tablo 12.19 iki büyüme biçimini yan yana koyar. Döngülü sürüm n tur döner; iş n ile doğru orantılıdır. Özyinelemeli sürümün çağrı sayısı ise n her 10 arttığında yaklaşık 123 katına çıkar. Bunun nedeni Fibonacci sayılarının kendisidir. Ardışık iki Fibonacci sayısının oranı yaklaşık 1,618'e yaklaşır. Bu sayıya altın oran denir ve φ ile gösterilir. φ¹⁰ ≈ 123'tür. Çağrı sayısı fib(n + 1) ile orantılı olduğu için o da her adımda yaklaşık 1,618 katına çıkar. Zaman O(φⁿ)'dir. Sunumdaki O(2ⁿ) yazımı bunun kaba bir üst sınırıdır: her çağrı en çok iki çağrı yapar ve ağacın derinliği n'dir. Hangisiyle ifade edilirse edilsin büyüme üsteldir.

Üstel büyümenin pratikteki anlamı şudur: fib(40) için 331 milyon çağrı yapılır. fib(50) için bu sayı 40 milyarı aşar. Döngülü sürüm ise fib(50)'yi 50 turda bulur. Yığın derinliği iki sürümde de sorun değildir: özyinelemeli sürüm en çok n çerçeve açar. Sorun zamandadır.

12.9.3Bellekleme

Tekrarın çaresi basittir: bir alt problemin sonucu ilk kez hesaplandığında bir yere yazılır. Aynı alt problem yeniden istendiğinde hesap yapılmaz; kayıtlı değer döndürülür. Bu yönteme bellekleme denir.

Fibonacci için kayıt yeri bir long dizisidir. bellek[k], fib(k)'nin sonucunu tutar. Java'da yeni bir sayı dizisinin bütün hücreleri 0 ile başlar. fib(k) ≥ 1 olduğu için (k ≥ 1) 0 değeri “henüz hesaplanmadı” anlamında kullanılabilir.

static long fib(int n, long[] bellek) {
    if (n <= 1) return n;
    if (bellek[n] != 0) return bellek[n];
    bellek[n] = fib(n - 1, bellek)
              + fib(n - 2, bellek);
    return bellek[n];
}
long[] bellek = new long[6];
System.out.println(fib(5, bellek));

5

Metot düz sürümden yalnızca üç noktada ayrılır:

1. Diziyi bir parametre olarak alır. Bütün çağrılar aynı dizi nesnesini paylaşır; bir çağrının yazdığı değeri öteki çağrılar görür.
2. Taban durumdan sonra kayda bakar: bellek[n] != 0 ise sonuç zaten bilinir ve hemen döndürülür.
3. Sonucu döndürmeden önce kaydeder: bellek[n] = fib(n - 1, bellek) + fib(n - 2, bellek);.

Bellekli sürümün çağrı sayısı da sayaçla ölçülmüştür:

public class BellekSayac {
    static long cagri = 0;

    static long fib(int n, long[] bellek) {
        cagri++;
        if (n <= 1) return n;
        if (bellek[n] != 0) return bellek[n];
        bellek[n] = fib(n - 1, bellek)
                  + fib(n - 2, bellek);
        return bellek[n];
    }

    public static void main(String[] args) {
        for (int n : new int[]{5, 10, 20, 30, 50}) {
            cagri = 0;
            long sonuc = fib(n, new long[n + 1]);
            System.out.println("fib(" + n + ") = " + sonuc + ", çağrı sayısı = " + cagri);
        }
    }
}

fib(5) = 5, çağrı sayısı = 9
fib(10) = 55, çağrı sayısı = 19
fib(20) = 6765, çağrı sayısı = 39
fib(30) = 832040, çağrı sayısı = 59
fib(50) = 12586269025, çağrı sayısı = 99

1 ve üstü n için çağrı sayısı 2n − 1'dir. Nedeni şudur: fib(n), fib(n − 1), …, fib(2) çağrılarının her biri bir kez hesaplanır ve iki çağrı yapar. Bunlardan n − 1 tane vardır; ilk çağrı da eklenince 1 + 2(n − 1) = 2n − 1 çıkar. fib(30) için çağrı sayısı 2 692 537'den 59'a iner. Zaman O(n) olur. Bunun karşılığında n + 1 hücrelik bir dizi kullanılır: ek bellek O(n)'dir. Zamandan kazanmak için bellek harcanmıştır.

12.9.4Belleklemeli fib(5)'i izlemek

Tablo 12.20 dokuz çağrıyı ve belleğin dolmasını gösterir. İlk dört çağrı fib(5), fib(4), fib(3) ve fib(2)'dir. Bunların hiçbiri bellekte yoktur ve hepsi hesaplanmak üzere sol terimlerini çağırır. fib(1) ve fib(0) taban durumdur. fib(2) = 1 + 0 = 1 hesaplanır ve bellek[2]'ye yazılır. fib(3) sağ terimi için fib(1)'i çağırır ve 2 bulur; bellek[3] = 2 olur.

Belleklemenin etkisi 8. çağrıda görülür. fib(4) sağ terimi için fib(2)'yi çağırır. Düz sürümde bu çağrı yeni bir alt ağaç açardı. Burada bellek[2] = 1'dir ve değer hemen döner. 9. çağrıda fib(5)'in istediği fib(3) de bellekten gelir. Sonunda bellek dizisi [0, 0, 1, 2, 3, 5] olur ve 5 yazdırılır. bellek[0] ve bellek[1] hiç kullanılmaz, çünkü 0 ve 1 taban durumdur.

Çalışma sorularındaki sürüm diziyi parametre yerine bir static alan olarak tutar: static long[] bellek = new long[50];. Bu biçimde dizi bütün programda bir kez oluşturulur ve sonraki fib çağrıları önceki hesapları da kullanır. 50 hücreli dizi fib(49)'a kadar yeter; fib(49) = 7 778 742 049 int'e sığmaz ama long'a sığar.

12.9.5Belleklemeyle kombinasyon

Bellekleme yalnızca Fibonacci'ye özgü değildir. Alt problemleri örtüşen her özyinelemede işe yarar. Sunumun alıştırmalarından biri kombinasyon sayısıdır. n öğeden k tanesini seçmenin yollarının sayısı C(n, k) ile gösterilir ve Pascal üçgeni kuralını sağlar: C(n, k) = C(n − 1, k − 1) + C(n − 1, k). Kural şöyle açıklanır: belirli bir öğe ya seçilir (kalan n − 1 öğeden k − 1 seçilir) ya da seçilmez (kalan n − 1 öğeden k seçilir). Taban durumlar C(n, 0) = 1 ve C(n, n) = 1'dir: hiç öğe seçmenin ve bütün öğeleri seçmenin birer yolu vardır.

// Sunumdaki alıştırma: kombinasyon(n, k) = kombinasyon(n - 1, k - 1) + kombinasyon(n - 1, k)
public class Kombinasyon {
    static long cagri;

    static long kombinasyon(int n, int k) {
        cagri++;
        if (k == 0 || k == n) return 1;
        return kombinasyon(n - 1, k - 1) + kombinasyon(n - 1, k);
    }

    static long kombinasyonB(int n, int k, long[][] bellek) {
        cagri++;
        if (k == 0 || k == n) return 1;
        if (bellek[n][k] != 0) return bellek[n][k];
        bellek[n][k] = kombinasyonB(n - 1, k - 1, bellek) + kombinasyonB(n - 1, k, bellek);
        return bellek[n][k];
    }

    public static void main(String[] args) {
        int[][] g = {{4, 2}, {5, 2}, {10, 5}, {20, 10}, {30, 15}};
        for (int[] x : g) {
            cagri = 0;
            long v = kombinasyon(x[0], x[1]);
            long c1 = cagri;
            cagri = 0;
            long w = kombinasyonB(x[0], x[1], new long[x[0] + 1][x[1] + 1]);
            System.out.println("C(" + x[0] + ", " + x[1] + ") = " + v + " / " + w + ": belleksiz " + c1 + " cagri, bellekli " + cagri + " cagri");
        }
    }
}

C(4, 2) = 6 / 6: belleksiz 11 cagri, bellekli 9 cagri
C(5, 2) = 10 / 10: belleksiz 19 cagri, bellekli 13 cagri
C(10, 5) = 252 / 252: belleksiz 503 cagri, bellekli 51 cagri
C(20, 10) = 184756 / 184756: belleksiz 369511 cagri, bellekli 201 cagri
C(30, 15) = 155117520 / 155117520: belleksiz 310235039 cagri, bellekli 451 cagri

12.10Kuyruk özyinelemesi

12.10.1Birikim parametresi

Özyinelemeli faktöriyelde her çerçeve bir işi dönüş yoluna bırakır: alt sonucu n ile çarpmak. Çerçevenin bekleyişi bu yüzdendir. Aynı hesap, çarpma çağrıdan önce yapılacak biçimde de yazılabilir. Bunun için ara sonuç ikinci bir parametrede taşınır. Bu parametreye birikim denir.

static long fakt(int n, long birikim) {
    if (n <= 1) return birikim;
    return fakt(n - 1, n * birikim);
}
// fakt(4, 1) → fakt(3, 4)
//   → fakt(2, 12) → fakt(1, 24) → 24

fakt(n, birikim), n! × birikim değerini hesaplar. İlk çağrıda birikim 1 verilir: fakt(4, 1) = 4!. Özyinelemeli durumda çarpma çağrının içinde, argüman hesaplanırken yapılır: n * birikim. Çağrı döndüğünde yapılacak iş kalmaz; alt çağrının sonucu olduğu gibi döndürülür. Taban durumda birikim, aranan sonucun tamamını taşır.

Dönüşte iş kalmadığına göre eski çerçeveyi saklamaya gerek yoktur. Bazı diller ve derleyiciler bu durumu tanır. Yeni çerçeve açmak yerine eski çerçeveyi yeni argümanlarla yeniden kullanırlar. Bu dönüşüme kuyruk çağrısı eniyilemesi (tail call optimization) denir. Eniyileme yapılırsa kuyruk özyinelemesi bir döngü kadar az bellek kullanır: O(1). Scheme gibi dillerin standardı bunu zorunlu tutar.

Java ise bu eniyilemeyi garanti etmez. Java derleyicisi ve JDK 21'in sanal makinesi kuyruk çağrılarını döngüye çevirmez. Her çağrı yine yeni bir çerçeve açar. Bu yüzden Java'da kuyruk özyinelemesi yığın güvenliği sağlamaz: fakt(100 000, 1) da derin bir doğrusal özyineleme gibi taşar. Java'da derin bir kuyruk özyinelemesi gerekiyorsa onu döngüye çevirmek programcının işidir. Çeviri de kolaydır: parametreler döngü değişkeni olur, özyinelemeli çağrı da bu değişkenlerin güncellenmesine dönüşür.

12.10.2fakt(4, 1)'i izlemek

static long fakt(int n, long birikim) {
    if (n <= 1) return birikim;
    return fakt(n - 1, n * birikim);
}
System.out.println(fakt(4, 1)); // 24

Program 24 yazar. Çalıştırılan sürüm fakt(20, 1), fakt(1, 1) ve fakt(0, 1) sonuçlarını da yazdırmıştır:

24
2432902008176640000 1 1

Tablo 12.21 zinciri verir: fakt(4, 1) → fakt(3, 4) → fakt(2, 12) → fakt(1, 24) → 24. Çarpmalar 4 × 1 = 4, 3 × 4 = 12 ve 2 × 12 = 24'tür ve hepsi gidiş yolunda yapılır. Normal faktöriyelde çarpmalar 2, 6, 24 sırasıyla dönüşte yapılıyordu. Burada çarpma sırası 4, 12, 24'tür ve dönüşte yalnızca 24 taşınır.

Şekil 12.26 Java'daki asıl durumu gösterir. Eski çerçevelerin bekleyecek bir işi yoktur ama yığında durmaya devam ederler. En derin anda main ile birlikte 5 çerçeve vardır; bu, normal faktoriyel(4) ile aynıdır. Kuyruk özyinelemesi Java'da belleği azaltmaz; ek bellek yine O(n)'dir. Yöntemin yararı başka dillerde ortaya çıkar. Java'da ise bir döngüye çevirmenin ara adımı olarak düşünülebilir.

12.11Taşma, uç durumlar ve hata ayıklama

12.11.1long taşması

Yığın taşması ile tamsayı taşması farklı şeylerdir. Yığın taşmasında çağrılar belleğe sığmaz. Tamsayı taşmasında ise hesaplanan sayı, türün tutabileceği en büyük değeri aşar. Faktöriyel bu ikinci türe çok çabuk ulaşır. long en çok 9 223 372 036 854 775 807 tutar. 20! = 2 432 902 008 176 640 000 bu sınırın altındadır. 21! = 51 090 942 171 709 440 000 ise sınırın yaklaşık beş buçuk katıdır.

Java tamsayı taşmasında hata fırlatmaz. Sonuç sessizce sarar: sınırı aşan kısım atılır ve sayı negatif bölgeden geri gelir. Aşağıdaki program faktoriyel metodunu 19'dan 22'ye kadar çalıştırmıştır:

public class Tasma {
    static long faktoriyel(int n) {
        if (n < 0)
            throw new IllegalArgumentException();
        if (n <= 1) return 1;
        return n * faktoriyel(n - 1);
    }

    public static void main(String[] args) {
        for (int n = 19; n <= 22; n++)
            System.out.println("faktoriyel(" + n + ") = " + faktoriyel(n));
        System.out.println("Long.MAX_VALUE = " + Long.MAX_VALUE);
        System.out.println("21! (BigInteger) = " + java.math.BigInteger.valueOf(21).multiply(new java.math.BigInteger("2432902008176640000")));
        System.out.println("fib(92), fib(93) long: " + fib(92) + " " + fib(93));
        System.out.println("hizliUs(2, 63) = " + hizliUs(2, 63) + ", hizliUs(2, 64) = " + hizliUs(2, 64));
        System.out.println("Integer.MIN_VALUE: Math.abs = " + Math.abs(Integer.MIN_VALUE) + ", Math.abs((long) ...) = " + Math.abs((long) Integer.MIN_VALUE));
    }

    static long fib(int n) {
        long a = 0, b = 1;
        for (int i = 0; i < n; i++) { long c = a + b; a = b; b = c; }
        return a;
    }

    static long hizliUs(long taban, int us) {
        if (us == 0) return 1;
        long yarim = hizliUs(taban, us / 2);
        if (us % 2 == 0) return yarim * yarim;
        return yarim * yarim * taban;
    }
}

faktoriyel(19) = 121645100408832000
faktoriyel(20) = 2432902008176640000
faktoriyel(21) = -4249290049419214848
faktoriyel(22) = -1250660718674968576
Long.MAX_VALUE = 9223372036854775807
21! (BigInteger) = 51090942171709440000
fib(92), fib(93) long: 7540113804746346429 -6246583658587674878
hizliUs(2, 63) = -9223372036854775808, hizliUs(2, 64) = 0
Integer.MIN_VALUE: Math.abs = -2147483648, Math.abs((long) ...) = 2147483648

faktoriyel(21) negatif bir sayı döndürür. Program çökmediği için hata gözden kaçabilir. Aynı sorun öteki örneklerde de vardır. fib(92) long'a sığar, fib(93) sığmaz ve negatif çıkar. hizliUs(2, 63) long'un en küçük değerini, hizliUs(2, 64) ise 0'ı verir. Daha büyük sonuçlar gerekiyorsa java.math.BigInteger sınıfı kullanılır; bu sınıfın sayıları bellek yettiği sürece büyüyebilir. Programdaki 21! değeri de BigInteger ile hesaplanmıştır.

12.11.2Negatif üs ve öteki uç girdiler

us(2, −1) çağrısı 12.4.1'de tartışıldı. Taban durum n == 0 hiç sağlanmaz; n −1, −2, −3 … diye iner ve çerçeveler birikir. Derinlik programında bu çağrı yaklaşık 8 bin çağrıdan sonra StackOverflowError ile bitmiştir. Bu sayı sonsuz metodunun sayısından küçüktür. Çerçeve boyu metodun parametrelerine ve JVM'in o anki çalışma biçimine bağlı olduğu için taşma noktası metottan metoda değişir.

İki önlem vardır. Birincisi girdiyi denetlemektir. n < 0 ise IllegalArgumentException fırlatılır; faktoriyel metodu bunu negatif girdi için zaten yapar. İkincisi negatif üsü tanımlı hâle getirmektir. Sonuç türü double yapılır ve negatif üs pozitif üse çevrilir: 2⁻² = 1 / 2² = 0,25. Çalışma sorularındaki sürüm bunu bir satırla yapar: if (n < 0) return 1.0 / us(t, -n);. Negatif dal yalnızca ilk çağrıda çalışır; sonraki çağrılarda üs pozitiftir.

Özyinelemeli bir metot test edilirken şu girdiler denenir:

1. Taban durumun kendisi: faktoriyel(0), faktoriyel(1), toplam(0), boş dizgi, tek karakterli dizgi.
2. Taban durumun bir üstü: faktoriyel(2), iki karakterli dizgi. Özyinelemeli durumun en basit kullanımı burada sınanır.
3. Geçersiz girdiler: negatif n, negatif üs, null dizgi. Metot ya anlamlı bir hata fırlatmalı ya da tanımlı bir değer döndürmelidir.
4. Büyük girdiler: sonucun türe sığıp sığmadığı (faktoriyel(21)) ve derinliğin yığına sığıp sığmadığı (toplam(100 000)).
5. Özel değerler: rakam problemlerinde 0 ve Integer.MIN_VALUE, aramada dizinin ilk ve son öğesi ile dizide olmayan değer.

12.11.3Özyinelemeli kodda hata ayıklama

Özyinelemeli bir metot yanlış sonuç veriyorsa ya da hiç bitmiyorsa sorun çoğu zaman iki parçadan birindedir. Hata ayıklama dört adımda yapılır:

1. Taban duruma ulaşılabildiği gösterilir. Her geçerli girdi için çağrı zinciri sonunda taban duruma girmelidir. Atlamalı küçülmelerde (n − 2 gibi) ve negatif girdilerde bu ayrıca denetlenir.
2. Küçülme ölçüsü belirlenir. Her çağrıda azalan bir büyüklük olmalıdır: n, dizginin uzunluğu, aralığın boyu (hi − lo + 1) ya da kalan öğe sayısı (a.length − i).
3. Küçük bir girdi tabloya dökülür. Çağrı ve dönüş anları, derinlik ve dönen değerlerle birlikte yazılır.
4. Derinlik ve tekrar değerlendirilir. En büyük derinlik girdinin boyuyla mı, logaritmasıyla mı büyüyor? Özyineleme ağacında aynı argüman birden çok kez görülüyor mu?

Üçüncü adım için metoda geçici yazdırma satırları eklenebilir. Derinlik bir sayaçla tutulur ve her satır derinlik kadar girintiyle yazılır. Böylece çağrıların iç içe yapısı çıktıda görünür. Tablo 12.22 toplam(2) için böyle bir izlemedir.

Tablo bir çağrının açılışını ve kapanışını aynı girinti düzeyinde gösterir. toplam(2) derinlik 0'da açılır ve en son kapanır. Arada toplam(1) ve toplam(0) açılıp kapanır. Dönen değerler 0, 1 ve 3'tür. Beklenen değerle karşılaştırma yapılırken hangi çağrının ilk kez yanlış değer döndürdüğüne bakılır. Hata o çağrının kendi satırlarındadır, çünkü onun kullandığı bütün alt sonuçlar doğrudur.

Bir metodun ne kadar derine indiği ve kaç çağrı yaptığı, sayaçlı bir sürümle de ölçülebilir. Bu notta verilen bütün çağrı sayıları ve derinlikler böyle ölçülmüştür. Sayaç, metodun girişinde artırılan bir static alandır. Derinlik için girişte artırılıp çıkışta azaltılan ikinci bir alan ve görülen en büyük değeri tutan üçüncü bir alan yeter.

Özyineleme Görselleştirici simülatörü bu izlemeleri etkileşimli olarak gösterir. Simülatörde faktoriyel, fib, us ve hanoi metotlarının çağrıları adım adım açılır ve kapanır. Çağrı yığını ve özyineleme ağacı aynı anda izlenir. Fibonacci'de bellekleme açılıp kapatılarak iki sürümün çağrı sayıları karşılaştırılabilir.

12.12Özet

• Özyineleme, bir metodun problemi aynı problemin daha küçük bir örneğine indirip kendini çağırmasıdır. Her özyinelemeli metotta iki parça bulunur: sonucun doğrudan bilindiği taban durum ve problemi küçültüp kendini çağıran özyinelemeli durum.
• Problem her çağrıda ölçülebilir biçimde küçülmeli ve taban duruma ulaşmalıdır. Atlamalı küçülmelerde ve negatif girdilerde taban durum == yerine <= ile yazılırsa daha güvenlidir.
• Her çağrı, parametreleri, yerel değişkenleri ve dönüş noktasını tutan bir yığın çerçevesi açar. Çerçeveler açıldıkları sıranın tersine kapanır. Özyinelemeli çağrıdan önceki işler açılımda, sonraki işler dönüşte ve ters sırada yapılır.
• Doğrusal özyineleme (faktöriyel, toplam, düz üs) n çerçeve açar: zaman ve ek yığın O(n)'dir. Rakamlar toplamı, hızlı üs ve ikili arama gibi her adımda büyük ölçüde küçülen problemlerde derinlik logaritmiktir.
• Böl ve fethet, problemi parçalara bölüp parçaları özyinelemeyle çözer ve birleştirir. Birleştirme sıralaması O(n log n) zamanda, O(n) ek bellekle ve O(log n) yığın derinliğiyle çalışır.
• Her çağrının iki çağrı yaptığı metotlar bir özyineleme ağacı oluşturur. Hanoi kuleleri 2ⁿ − 1 hamle, alt küme üretimi 2ⁿ alt küme üretir. Bu problemlerde üstel iş problemin kendisinden gelir; yığın derinliği ise n + 1'dir.
• Taban durumu olmayan ya da çok derine inen özyineleme yığını doldurur ve StackOverflowError ile biter. JDK 21'de varsayılan yığın birkaç on bin çağrı taşıyabilmiştir.
• Basit doğrusal tekrarlarda döngü tek çerçevede, O(1) ek yığınla çalışır ve taşmaz. Kendine benzeyen problemlerde özyineleme tanıma yakın ve okunaklıdır. Seçim doğruluk, okunabilirlik ve kaynak kullanımına göre yapılır.
• Doğrudan Fibonacci aynı alt problemleri tekrar tekrar çözer. Çağrı sayısı 2·fib(n + 1) − 1'dir ve üstel büyür: fib(30) için 2 692 537 çağrı.
• Bellekleme, alt problem sonuçlarını saklayarak tekrarı kaldırır. Belleklemeli fib(n) 2n − 1 çağrı yapar; zaman O(n)'e iner, karşılığında O(n) bellek kullanılır.
• Kuyruk özyinelemesinde çağrı metodun son işidir ve ara sonuç bir birikim parametresinde taşınır. Java kuyruk çağrılarını eniyilemez; çerçeveler yine birikir ve ek bellek O(n) kalır.
• Tamsayı taşması yığın taşmasından farklıdır ve sessizdir: long faktoriyel(21) negatif bir sayı döndürür. Özyinelemeli metotlar taban durum, taban durumun bir üstü, geçersiz girdi ve büyük girdilerle test edilir.

12.13Kavram listesi

• özyineleme recursion
• taban durum base case
• özyinelemeli durum recursive case
• çağrı yığını call stack
• yığın çerçevesi stack frame
• özyineleme derinliği recursion depth
• özyineleme ağacı recursion tree
• yardımcı metot helper method
• fırlatma throw (exception)
• palindrom palindrome
• en büyük ortak bölen greatest common divisor
• Öklid algoritması Euclid's algorithm
• alt dizgi substring
• böl ve fethet divide and conquer
• ikili arama binary search
• Hanoi kuleleri Towers of Hanoi
• alt küme subset
• geri izleme backtracking
• yığın taşması stack overflow
• sonsuz özyineleme infinite recursion
• döngülü iterative (version)
• zaman karmaşıklığı time complexity
• üstel exponential (growth)
• Fibonacci dizisi Fibonacci sequence
• bellekleme memoization
• kuyruk özyinelemesi tail recursion
• taşma overflow (integer)

12.14Kendini Dene

1. toplam(5) çağrısında (toplam(n) = n + toplam(n − 1), toplam(0) = 0) toplam metodu kaç kez çağrılır? Yığın en derin anında main dahil kaç çerçeve içerir? Sonuç kaçtır?

   Cevap

   toplam(5), toplam(4), toplam(3), toplam(2), toplam(1) ve toplam(0) çağrılır: 6 çağrı. toplam(0) çağrıldığında hiçbir çağrı henüz dönmemiştir; yığında main ile birlikte 7 çerçeve vardır. Sonuç 5 + 4 + 3 + 2 + 1 + 0 = 15'tir.

2. ebob(21, 13) çağrısının zinciri nasıldır? Kaç çağrı yapılır ve sonuç kaçtır?

   Cevap

   ebob(21, 13) → ebob(13, 8) → ebob(8, 5) → ebob(5, 3) → ebob(3, 2) → ebob(2, 1) → ebob(1, 0). Toplam 7 çağrı yapılır ve sonuç 1'dir. 21 ve 13 ardışık Fibonacci sayılarıdır. Bu yüzden kalanlar da Fibonacci sayıları olarak birer birer küçülür; Öklid algoritmasının en yavaş olduğu durum budur.

3. hizliUs(2, 13) çağrısında üs hangi değerlerden geçer? Kaç çağrı yapılır? Dönüş yolunda hangi çerçeveler tabanla bir kez daha çarpar? Düz us(2, 13) kaç çağrı yapardı?

   Cevap

   Üs 13, 6, 3, 1 ve 0 olur: 5 çağrı. Dönüşte üssü tek olan çerçeveler (1, 3 ve 13) sonucu bir kez daha 2 ile çarpar. Değerler sırasıyla 1, 2, 8, 64 ve 8192'dir: 1·1·2 = 2, 2·2·2 = 8, 8·8 = 64, 64·64·2 = 8192. Düz yöntem n + 1 = 14 çağrı yapardı.

4. Hanoi kulelerinde 6 disk için kaç hamle gerekir? Notta verilen hanoi metodu (hanoi(0) çağrıları dahil) kaç kez çağrılır?

   Cevap

   Hamle sayısı 2⁶ − 1 = 63'tür. Çağrı sayısı 2⁷ − 1 = 127'dir: özyineleme ağacının her düzeyinde çağrı sayısı ikiye katlanır ve 7 düzey vardır (n = 6'dan n = 0'a). Yaprakların hepsi hamle yapmayan hanoi(0) çağrılarıdır.

5. fib(10) hesaplanırken düz özyinelemeli sürüm ve belleklemeli sürüm kaçar çağrı yapar? Hangi formüllerle bulunur?

   Cevap

   Düz sürüm 2·fib(11) − 1 = 2·89 − 1 = 177 çağrı yapar. Belleklemeli sürüm 2·10 − 1 = 19 çağrı yapar. Sonuç ikisinde de fib(10) = 55'tir.

6. Notta verilen altKume metodu {1, 2, 3} dizisiyle çağrılıyor. Kaç satır yazdırılır? 4. satır nedir? Metot kaç kez çağrılır?

   Cevap

   2³ = 8 satır yazdırılır: [1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []. 4. satır [1]'dir: 1 dahil edilmiş, 2 ve 3 hariç tutulmuştur. Çağrı sayısı 2⁴ − 1 = 15'tir.

7. a = {2, 5, 8, 12, 16, 23, 38, 56} dizisinde ara(a, 5, 0, 7) çağrısı kaç çağrı yapar ve ne döndürür?

   Cevap

   İlk çağrıda mid = 3 ve a[3] = 12'dir; 12 > 5 olduğundan ara(a, 5, 0, 2) çağrılır. Bu çağrıda mid = 1 ve a[1] = 5'tir: değer bulunmuştur. 2 çağrı yapılır ve 1 döner.

8. 1'den n'ye toplamın kuyruk özyinelemeli sürümü şöyledir: static int toplamK(int n, int birikim) { if (n == 0) return birikim; return toplamK(n - 1, birikim + n); }. toplamK(4, 0) çağrısının zinciri nasıldır? Java'da en derin anda yığında main dahil kaç çerçeve vardır?

   Cevap

   toplamK(4, 0) → toplamK(3, 4) → toplamK(2, 7) → toplamK(1, 9) → toplamK(0, 10) → 10. Toplamalar çağrıdan önce yapılır ve dönüşte iş kalmaz. Java kuyruk çağrılarını eniyilemediği için beş toplamK çerçevesinin hepsi yığındadır; main ile birlikte 6 çerçeve vardır.

9. Bir dizgide bir karakterin kaç kez geçtiğini sayan say(s, c, i) metodu i'nci indisten başlayarak sayıyor. Taban durum ve özyinelemeli durum ne olmalıdır? say("kayak", 'a', 0) kaç çağrı yapar ve ne döndürür?

   Cevap

   Taban durum i == s.length()'tir: bakılacak karakter kalmamıştır ve 0 döner. Özyinelemeli durumda s.charAt(i) c'ye eşitse 1, değilse 0 alınır ve say(s, c, i + 1) ile toplanır. “kayak” için i = 0'dan 5'e 6 çağrı yapılır. 'a' 1. ve 3. indislerdedir; sonuç 2'dir.

12.15İleri okuma

• R. Sedgewick, K. Wayne, Computer Science: An Interdisciplinary Approach (Addison-Wesley, 2016), Kesim 2.3: özyineleme Öklid algoritması, Hanoi kuleleri, Gray kodları ve özyinelemeli grafiklerle anlatılır; doğrudan Fibonacci'nin neden yavaş olduğu ve belleklemeyle hızlandırılması da bu kesimdedir. Çevrim içi sürümü introcs.cs.princeton.edu adresindedir.
• E. Roberts, Thinking Recursively with Java (Wiley, 2006): bütünüyle özyinelemeli düşünmeye ayrılmış bir kitaptır. Küçük problemin çözüldüğünü varsayıp büyük problemi kurma alışkanlığını adım adım kazandırır.
• A. B. Downey, C. Mayfield, Think Java (2. baskı, O'Reilly, 2019): özyinelemeli metotlar ve yığın diyagramları programlamaya yeni başlayanlar için sade bir dille anlatılır; kitabın çevrim içi sürümü ücretsizdir.
• Oracle, Java SE 21 API: StackOverflowError sınıfının resmî açıklaması; hatanın bir uygulama çok derine özyinelendiğinde fırlatıldığı burada belirtilir.

12.16Kaynaklar

1. E. Roberts, Thinking Recursively with Java, Wiley, 2006.
2. R. Sedgewick, K. Wayne, Computer Science: An Interdisciplinary Approach, Addison-Wesley, 2016: 2.3 Recursion.
3. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022.
4. Y. D. Liang, Introduction to Java Programming and Data Structures, 13. baskı, Pearson, 2024.
5. Oracle, Java SE 21 API: StackOverflowError.
6. A. B. Downey, C. Mayfield, Think Java, 2. baskı, O'Reilly, 2019.

İlgili sayfalar: Özyineleme sunumu · Çalışma soruları · Özyineleme Görselleştirici simülatörü · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.