Bölüm 3.5: Özyineleme

3.5.1Özyineleme kavramı

Metot, bir işi adlandırıp tek satırla çağrılabilir hâle getirir. main bir metodu çağırabilir, o metot da başka bir metodu çağırabilir. Bir metodun çağırdığı metot kendisi de olabilir. Java bunu yasaklamaz ve bu olanak, bazı problemleri döngülerden çok daha kısa ve açık yazmayı sağlar.

3.5.1.1Özyineleme nedir?

Java'da özyineleme için özel bir anahtar kelime yoktur. Metot gövdesinde kendi adını, sıradan bir metot çağırır gibi çağırır. Derleyici için faktoriyel'in faktoriyel'i çağırması, main'in println'i çağırmasından farklı değildir. Fark, çalışma sırasında ortaya çıkar: aynı metodun birden çok çağrısı aynı anda bellekte bekler.

Özyinelemenin gündelik hayatta üç tanıdık karşılığı vardır. Matruşka bebeklerinde her bebeğin içinde daha küçük bir bebek bulunur. En küçük bebek açılmaz; özyinelemedeki karşılığı taban durumdur. Sinema salonunda karanlıkta oturan biri kaçıncı sırada olduğunu öğrenmek istesin. Öndekine sorar, o da öndekine sorar. İlk sıradaki kişi “1” der. Cevaplar geri gelirken her kişi duyduğu sayıya 1 ekler ve arkasındakine söyler. Soru öne doğru ilerler, cevap arkaya doğru döner. Özyinelemeli bir metodun çalışması tam olarak böyledir. Karşılıklı iki aynada ise görüntünün içinde görüntü, onun içinde yine görüntü belirir ve bu dizi bitmez. Bu da taban durumu olmayan özyinelemenin resmidir.

Özyineleme her problem için doğru seçim değildir. Ama bazı problem türlerinde döngüden çok daha anlaşılır bir çözüm verir. Ağaç biçimli veriler, örneğin klasörler ve alt klasörler, bu türdendir. Tanımı kendine dayanan sayı serileri de öyledir. Problemi ikiye bölüp parçaları ayrı çözen böl ve yönet (divide and conquer) algoritmaları da bu gruba girer. Hanoi kuleleri gibi bazı bulmacalar döngüyle zor, özyinelemeyle birkaç satırda yazılır.

3.5.1.2Taban durum ve özyinelemeli adım

Her özyinelemeli metot iki parçadan oluşur. Biri durmayı, öteki ilerlemeyi sağlar.

Faktöriyel bu iki parçayı en açık gösteren örnektir. 1! = 1 bilinir; bunun için hesap gerekmez. 4! ise doğrudan bilinmez, ama 3! bilinirse 4! = 4 × 3! diye bulunur. Matematikteki tümevarımsal tanım, özyinelemeli metodun birebir karşılığıdır:

İlk satır taban durumdur, ikinci satır özyinelemeli adımdır. Tanım döngüsel görünse de değildir: 4! tanımlanırken 3!, 3! tanımlanırken 2! kullanılır. Her adımda argüman küçülür ve sonunda 1'e varılır. Şekil 3.5.1 bu iç içe yapıyı kutularla gösterir.

İki parçanın ikisi de zorunludur. Taban durum yoksa metot kendini sonsuza kadar çağırır. Özyinelemeli adım problemi küçültmüyorsa taban duruma hiç varılmaz ve sonuç yine aynıdır. Özyinelemeli her metodun uyması gereken iki temel kural bu iki koşuldan doğar.

3.5.1.3Çağrı yığını

Özyinelemenin nasıl çalıştığını anlamak için Java'nın metot çağrılarını bellekte nasıl tuttuğunu bilmek gerekir.

Yığın, üst üste konan tabaklara benzer. Yeni tabak en üste konur, alınacak tabak da en üstten alınır. Bu düzene son giren ilk çıkar (last in, first out, LIFO) denir. Bir metot çağrıldığında çerçevesi yığının tepesine eklenir. Metot return ile bittiğinde çerçevesi silinir ve döndürdüğü değer bir alttaki çerçeveye iletilir. Alttaki çerçeve, tam bıraktığı yerden çalışmaya devam eder.

Özyinelemede aynı metodun birden çok çerçevesi aynı anda yaşar. faktoriyel(4), faktoriyel(3)'ü çağırdığında ilk çerçeve silinmez; çarpmayı yapabilmek için alttan gelecek değeri bekler. Her çerçevenin kendi n'si vardır. Yığında dört ayrı n bulunabilir: biri 4, biri 3, biri 2, biri 1. Bunlar aynı adı taşıyan ama birbirinden bağımsız değişkenlerdir. Bir çerçevedeki n'nin değişmesi ötekileri etkilemez.

Şekil 3.5.2, main'in faktoriyel(4)'ü çağırdığı programın en derin anını gösterir. O anda yığında beş çerçeve vardır: main ve dört faktoriyel çerçevesi. Yalnız tepedeki faktoriyel(1) çalışır. Alttaki her çerçeve bir çarpımın yarısında durmuş, eksik çarpanı bekler: 4 * ?, 3 * ?, 2 * ?.

Yığının boyutu sınırlıdır. Java'da her iş parçacığının yığını, program başlarken belirlenen sabit bir bellek alanıdır. Çok derin bir özyineleme bu alanı doldurur ve program StackOverflowError ile durur. Bu sınır, özyinelemenin en önemli pratik kısıtıdır.

3.5.2Faktöriyel ve toplam

Faktöriyel ve 1'den n'ye toplam, özyinelemenin en basit iki örneğidir. İkisi de aynı kalıbı izler: argümanı bir azaltıp kendini çağırır, gelen sonuca kendi katkısını ekler. Bu kalıp iyi anlaşıldığında sonraki örneklerin çoğu onun çeşitlemesi olarak okunur.

3.5.2.1Faktöriyel metodu

n'nin faktöriyeli 1'den n'ye kadar sayıların çarpımıdır: n! = 1 × 2 × … × n. Tanım gereği 0! = 1'dir. Aynı çarpım özyinelemeli olarak n! = n × (n − 1)! diye de yazılır. Java'daki karşılığı şöyledir:

int faktoriyel(int n) {
    if (n == 0 || n == 1) {
        return 1;   // taban durum
    } else {
        return n * faktoriyel(n - 1); // özyineleme
    }
}

Birinci satır metodun başlığıdır: int bir parametre alır, int bir değer döndürür. İkinci ve üçüncü satırlar taban durumdur. n 0 ya da 1 ise cevap 1'dir ve metot kendini çağırmadan döner. Beşinci satır özyinelemeli adımdır: n!, (n − 1)!'in n ile çarpımıdır. faktoriyel(n - 1) ifadesi hesaplanmadan çarpma yapılamaz; bu yüzden metot önce kendini çağırır, cevabı bekler, sonra çarpar ve döner.

Metodun her zaman sona ereceği gösterilebilir. Her çağrıda n 1 azalır. Başlangıçta n ≥ 0 ise bu azalma eninde sonunda 1'e ya da 0'a varır ve taban durum çalışır. Bu ilerleme garantisi her özyinelemeli metotta aranması gereken özelliktir. faktoriyel(5) çağrısı 120, faktoriyel(0) çağrısı 1 döndürür.

Kodun matematiksel olarak doğru olması, her sonucun doğru çıkacağı anlamına gelmez. int en çok 2.147.483.647'yi tutabilir. 12! = 479.001.600 bu sınırın altındadır, 13! = 6.227.020.800 ise üstündedir. Java taşmayı haber vermez: çarpımın sığmayan üst bitleri atılır ve geriye anlamsız bir sayı kalır (Tablo 3.5.1). faktoriyel(13) 1932053504 döndürür; 17! için sonuç negatiftir. Dönüş tipi long yapılırsa 20! = 2.432.902.008.176.640.000'e kadar doğru sonuç alınır; 21! long'a da sığmaz. Daha büyük faktöriyeller için java.math.BigInteger kullanılır.

3.5.2.2faktoriyel(4) çağrısının açılımı

Özyinelemeli bir çağrının sonucunu elle bulmanın en kısa yolu, çağrıyı yerine koyarak açmaktır. Her faktoriyel(k) yazılan yere k * faktoriyel(k - 1) konur ve taban duruma varılınca geri hesaplanır:

faktoriyel(4)
  = 4 * faktoriyel(3)
  = 4 * (3 * faktoriyel(2))
  = 4 * (3 * (2 * faktoriyel(1)))
  = 4 * (3 * (2 * 1))
  = 4 * (3 * 2)
  = 4 * 6
  = 24

Açılım üç evreden oluşur. İlk dört satır iniştir. Her çağrı yeni bir çağrı açar ve çarpımlar bekletilir, çünkü sağ taraftaki değer henüz bilinmez. Beşinci satırda dibe, yani taban duruma varılır. faktoriyel(1) doğrudan 1 döndürür. Kod n == 1'de durduğu için faktoriyel(0) hiç çağrılmaz. Son üç satır çıkıştır. Bekleyen çarpımlar içten dışa doğru tamamlanır: önce 2 × 1 = 2, sonra 3 × 2 = 6, en son 4 × 6 = 24.

Parantezlerin iç içe girmesi, çağrı yığınının yazıyla gösterilmiş hâlidir. En içteki parantez yığının tepesidir ve ilk o tamamlanır. Her kapanan parantez, yığından silinen bir çerçeveye karşılık gelir. Çarpmaların 4 × 3 × 2 × 1 sırasıyla değil, ters sırayla yapıldığına dikkat edilmelidir. Çarpmada sıra sonucu değiştirmez; ama ekrana yazdırma gibi sırası önemli işlerde iniş ile çıkış arasındaki fark belirleyici olur.

3.5.2.3Çağrı yığınında izleme

Aynı hesap, tam bir programın çalışması olarak da izlenebilir. Aşağıdaki programda main, faktoriyel(4)'ü çağırıp sonucu yazdırır:

static int faktoriyel(int n) {
    if (n == 0 || n == 1) {
        return 1;
    } else {
        return n * faktoriyel(n - 1);
    }
}

public static void main(String[] args) {
    System.out.println(faktoriyel(4));
}

24

Tablo 3.5.2, programın her adımında çağrı yığınını aşağıdan yukarıya doğru verir. “Bekleyen iş” sütunu, çerçevenin dönüşte yapacağı hesaptır.

Dört faktoriyel çağrısı yapılır. En derin anda, yani beşinci adımda yığında beş çerçeve vardır: main ile dört faktoriyel. Şekil 3.5.3 aynı izlemenin üç anını çağrı zinciri olarak gösterir. Üstte inişin dibi, altta bütün dönüşler tamamlandıktan sonraki durum vardır.

Bir özyinelemeli metodun zaman ve bellek maliyeti bu izlemeden okunur. faktoriyel(n) tam n çağrı yapar ve her çağrıda bir karşılaştırma ile bir çarpma vardır. Çalışma süresi n ile doğru orantılıdır, yani O(n)'dir. Yığında aynı anda en çok n çerçeve bulunur; bellek de O(n)'dir. Aynı işi yapan döngü de O(n) sürer, ama tek bir çerçeveyle çalışır ve belleği O(1)'dir. Derinlik büyüdükçe bu fark önem kazanır.

3.5.2.41'den n'ye toplam

1'den n'ye kadar sayıların toplamı da aynı kalıpla yazılır: toplam(n) = n + toplam(n − 1) ve toplam(1) = 1. Faktöriyelden tek farkı, çarpma yerine toplama yapılması ve taban durumun yalnız n == 1 olmasıdır.

int toplam(int n) {
    if (n == 1) {
        return 1;
    } else {
        return n + toplam(n - 1);
    }
}

toplam(5) = 5 + toplam(4)
          = 5 + (4 + (3 + (2 + toplam(1))))
          = 5 + (4 + (3 + (2 + 1)))
          = 15

Açılımda her çağrı kendi sayısını bekleyen bir toplama olarak dışarıda bırakır. Dibe varıldığında 2 + 1 = 3, sonra 3 + 3 = 6, 4 + 6 = 10 ve 5 + 10 = 15 hesaplanır. toplam(100) aynı yolla 5050'yi verir. Bu sonuç, Gauss'un n(n + 1)/2 formülüyle de doğrulanır: 100 · 101 / 2 = 5050.

Bu metodun bir zayıf noktası vardır. Taban durum yalnız n == 1'dir. toplam(0) ya da negatif bir sayıyla çağrıldığında n hiç 1 olmaz: 0, −1, −2, … diye sonsuza kadar azalır. Sonuç sonsuz özyinelemedir ve program StackOverflowError ile durur. Güvenli sürümde taban durum if (n <= 0) return 0; olur. Bu sürüm geçersiz girdileri de yakalar ve toplam(1) için 1 + 0 = 1'i doğru verir.

3.5.3Seriler

Birçok sayı serisi, her terimi önceki terimlerden hesaplayan bir kuralla tanımlanır. Böyle bir kurala yineleme bağıntısı (recurrence relation) denir. Yineleme bağıntısı, özyinelemeli bir metoda neredeyse harfi harfine çevrilir: başlangıç değerleri taban durum, bağıntının kendisi özyinelemeli adım olur. Bu kesimde dört seri ele alınır. Fibonacci ve Lucas serilerinde metot kendini iki kez çağırır. Catalan ve Bell serilerinde ise çağrılar bir döngünün içinde yapılır.

3.5.3.1Fibonacci serisi

Seri, adını İtalyan matematikçi Leonardo Fibonacci'den alır. Fibonacci 1202'de yazdığı Liber Abaci kitabında tavşanların çoğalmasıyla ilgili bir problem sorar. Her çift tavşan iki aylık olunca her ay yeni bir çift doğurur; bir yılın sonunda kaç çift tavşan olur? Ay ay çift sayısı bu seriyi izler. Serinin ilk on üç terimi Tablo 3.5.3'te verilmiştir.

Ardışık iki terimin oranı, n büyüdükçe altın orana (≈ 1,618) yaklaşır: 144 / 89 ≈ 1,6180. Tanımı Java'ya çevirmek kolaydır:

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

Taban durum n <= 1'dir ve iki başlangıç değerini tek satırda karşılar: n 0 ise 0, 1 ise 1 döner. Yani bu durumda cevap n'nin kendisidir. Özyinelemeli adımda metot kendini iki kez çağırır. Faktöriyeldeki çağrılar düz bir zincir oluştururken burada her çağrı iki dala ayrılır ve çağrılar bir ağaç oluşturur. Bu tür özyinelemeye ağaç özyinelemesi (tree recursion) denir.

3.5.3.2fibonacci(4) çağrı ağacı

Ağaç özyinelemesinde çağrıların sırası önemlidir. Java bir ifadeyi soldan sağa hesaplar. fibonacci(n - 1) + fibonacci(n - 2) ifadesinde önce sol terim tamamen hesaplanır. Sağ terim için çağrı, sol terimin bütün alt çağrıları bittikten sonra yapılır. Bu yüzden ağaç, en soldaki dalın dibine kadar inilerek, ardından sağa doğru dolaşılarak gezilir.

Tablo 3.5.4, dokuz çağrıyı yapılış sırasıyla verir. Yığın hiçbir anda dört fibonacci çerçevesinden derine inmez, çünkü en uzun dal 4 → 3 → 2 → 1'dir. Ama toplam çağrı sayısı 9'dur ve fib(2) iki kez, fib(1) üç kez, fib(0) iki kez hesaplanmıştır. Şekil 3.5.4 ağacın iki anını gösterir: üstte inişin ilk kez dibe vardığı an, altta bütün çağrıların değer döndürdüğü son durum.

Tekrarlanan hesaplama küçük n için zararsız görünür. Ama ağacın büyüklüğü n ile hızla artar. fibonacci(n)'in yaptığı çağrı sayısı Ç(n) = 1 + Ç(n − 1) + Ç(n − 2) bağıntısını sağlar ve Ç(n) = 2F(n + 1) − 1'dir. fibonacci(5) 15, fibonacci(10) 177, fibonacci(40) 331.160.281 çağrı yapar. Ağaç her düzeyde yaklaşık 1,6 kat genişler ve aynı alt ağaçlar defalarca kurulur.

3.5.3.3Lucas serisi

Lucas serisi, Fibonacci ile aynı bağıntıyı farklı başlangıç değerleriyle kullanır. Fransız matematikçi Édouard Lucas'nın adını taşır.

int lucas(int n) {
    if (n == 0) {
        return 2;
    } else if (n == 1) {
        return 1;
    } else {
        return lucas(n - 1) + lucas(n - 2);
    }
}

Fibonacci'de iki başlangıç değeri return n; ile tek satırda karşılanabiliyordu, çünkü F(0) = 0 ve F(1) = 1'dir. Lucas'ta L(0) = 2 olduğu için bu kısayol yoktur ve iki ayrı taban durum gerekir. else if zinciri önce n == 0'ı, sonra n == 1'i sınar; ikisi de değilse özyinelemeli adım çalışır.

İki seri birbirine bağlıdır: L(n) = F(n − 1) + F(n + 1). Örneğin L(5) = F(4) + F(6) = 3 + 8 = 11'dir. Lucas'ın çağrı ağacı Fibonacci'ninkiyle aynı biçimdedir, çünkü taban durumlar yine n = 0 ve n = 1'dedir. Bu yüzden lucas(5) de 15 çağrı yapar.

3.5.3.4Catalan serisi

Catalan sayıları birçok sayma probleminin cevabıdır. Seri, Belçikalı matematikçi Eugène Catalan'ın adını taşır.

Özyinelemeli formülde bir terim, kendisinden küçük bütün terimlerden kurulur. Java kodu bu toplamı bir for döngüsüyle hesaplar ve özyinelemeli çağrıları döngünün içinde yapar:

long catalan(int n) {
    if (n <= 1) {
        return 1;
    }
    long sonuc = 0;
    for (int i = 0; i < n; i++) {
        sonuc += catalan(i) * catalan(n - i - 1);
    }
    return sonuc;
}

Dönüş tipi long'dur, çünkü Catalan sayıları hızla büyür. sonuc 0'dan başlar; toplamanın etkisiz elemanı 0'dır. Döngü i'yi 0'dan n - 1'e kadar dolaştırır ve her turda catalan(i) * catalan(n - i - 1) çarpımını toplama ekler. Örneğin C(3) şöyle hesaplanır:

Kapalı formül de aynı sonucu verir: 6! / (4! · 3!) = 720 / 144 = 5. Serinin ilk dokuz terimi 1, 1, 2, 5, 14, 42, 132, 429, 1430'dur; kod çalıştırıldığında da bu değerler çıkar.

Catalan sayıları ne sayar? En bilinen cevap, n çift parantezin doğru dizilişleridir. Doğru dizilişte her açılan parantez daha sonra kapanır ve hiçbir noktada kapanan parantez sayısı açılanı geçmez. n = 3 için beş diziliş vardır: ((())), (()()), (())(), ()(()), ()()(). Aynı sayı, n + 1 sayının çarpımının kaç farklı sırayla parantezlenebileceğini ve n düğümlü kaç farklı ikili ağaç bulunduğunu da verir.

Bu metodun maliyeti Fibonacci'den de hızlı büyür. Her catalan(n), küçük bütün terimleri iki kez çağırır ve hiçbir sonucu saklamaz. Ölçülen çağrı sayıları n = 2, 3, 4, 5, 6 için sırasıyla 5, 15, 45, 135, 405'tir; n 1 artınca çağrı sayısı üç katına çıkar. Bu tür bir metot küçük n için kısa ve açıktır, ama büyük n için belleklemeye ihtiyaç duyar.

3.5.3.5Bell serisi

int bell(int n) {
    if (n == 0) { return 1; }
    int sayi = 0;
    for (int k = 0; k < n; k++) {
        sayi += katsayi(n - 1, k) * bell(k);
    }
    return sayi;
}

int katsayi(int n, int k) {       // C(n, k)
    return faktoriyel(n) / (faktoriyel(k) * faktoriyel(n - k));
}

Kod iki metottan oluşur. bell, Catalan'daki gibi bir döngü içinde kendini çağırır ve her terimi kombinasyon katsayısıyla çarpıp toplar. katsayi ise C(n, k) = n! / (k! · (n − k)!) formülünü faktoriyel metoduyla hesaplar. Burada bir metodun hem kendini hem de başka bir özyinelemeli metodu çağırdığı görülür.

Bell sayıları, n elemanlı bir kümenin kaç farklı biçimde gruplara ayrılabileceğini sayar. {a, b, c} kümesi için beş yol vardır: tek grup abc; bir eleman ayrı, ikisi birlikte olan üç yol a|bc, b|ac, c|ab; her eleman ayrı a|b|c. Gerçekten de B(3) = 5'tir. Serinin ilk sekiz terimi 1, 1, 2, 5, 15, 52, 203, 877'dir.

Bu kodda taşma iki ayrı yerden gelir. katsayi, int döndüren faktoriyel'i kullanır ve 13! int'e sığmaz. bell(14), katsayi(13, k)'yi çağırdığı için yanlışlaşır. bell(13) = 27.644.437 doğru çıkar, bell(14) ise 77.914.768 verir; doğru değer 190.899.322'dir. Bu yüzden kod yalnız n ≤ 13 için doğrudur. faktoriyel düzeltilse bile sonuç int olduğu için B(16) = 10.480.142.147 yine sığmazdı.

3.5.4Özyinelemeli metot yazma

Özyinelemeli bir metodu okumak, yazmaktan kolaydır. Yazarken iki kurala uymak ve probleme belirli bir bakış açısıyla yaklaşmak gerekir. Önce iki kural, ardından bu kurallar çiğnendiğinde ortaya çıkan hata, en son da bir problemi özyinelemeli düşünmenin adımları işlenir.

3.5.4.1İki temel kural

İlerlemenin ne demek olduğu, “taban duruma uzaklık” diye bir ölçüyle somutlaştırılır. Faktöriyelde bu ölçü n'nin kendisidir: her çağrıda 1 azalır ve 1'e varınca durur (Şekil 3.5.5). Rakamlar toplamında ölçü basamak sayısıdır, palindromda dizginin uzunluğu, Öklid algoritmasında ikinci parametre. Ölçü bir doğal sayıysa ve her çağrıda kesin olarak küçülüyorsa sonsuza kadar küçülemez; sonunda taban duruma varılır.

En sık iki hata bu kuralların çiğnenmesidir. Sonsuz özyinelemede taban durum ya hiç yoktur ya da ona hiç ulaşılamaz. Yetersiz ilerlemede parametre değişmez; örneğin return n * faktoriyel(n); yazılmıştır. İki hatanın sonucu da aynıdır: StackOverflowError.

Kurallara üç alışkanlık eklenir. Birincisi, her özyinelemeli çağrı problemin daha küçük bir alt kümesine odaklanır. İkincisi, taban durum her zaman özyinelemeli çağrıdan önce sınanır; çağrı önce yapılırsa sınama hiç sırası gelmeden yığın dolar. Üçüncüsü, olası bütün girdiler hesaba katılır. Negatif sayı, 0, boş dizgi ya da Integer.MIN_VALUE taban duruma ulaşıyor mu, sorusu sorulur.

3.5.4.2Sonsuz özyineleme

Sonsuz özyinelemenin nasıl göründüğünü tam bir programla görmek öğreticidir. Aşağıdaki program, taban durumu yalnız n == 1 olan toplam'ı 0 ile çağırır:

public class Toplam {
    static int toplam(int n) {
        if (n == 1) {
            return 1;
        } else {
            return n + toplam(n - 1);   // satır 6
        }
    }
    public static void main(String[] args) {
        System.out.println(toplam(0));
    }
}

Program derlenir; derleyici hiçbir uyarı vermez. Çalıştırıldığında ise bir süre sonra şu iletiyle durur:

Exception in thread "main" java.lang.StackOverflowError
	at Toplam.toplam(Toplam.java:6)
	at Toplam.toplam(Toplam.java:6)
	at Toplam.toplam(Toplam.java:6)
	...

Ne olduğunu adım adım izleyelim. main, toplam(0)'ı çağırır. n = 0 için 0 == 1 yanlıştır ve 0 + toplam(-1) hesaplanmak üzere yeni bir çağrı yapılır. n = -1 de 1 değildir; -1 + toplam(-2) bekler. n her çağrıda taban durumdan biraz daha uzaklaşır. Her çağrı yığına yeni bir çerçeve ekler ve hiçbiri dönemez, çünkü hepsi bir sonrakinin sonucunu bekler. Bin çağrıdan sonra yığında 1001 çerçeve vardır ve hâlâ hata yoktur. Sonunda yığın için ayrılan bellek dolar (Şekil 3.5.6).

Taşmanın kaç çağrıdan sonra olduğu sabit değildir. Yığının boyutuna, çerçevenin büyüklüğüne ve JVM'nin o anda kodu yorumlayıp yorumlamadığına bağlıdır. JDK 21 ile Windows'ta varsayılan ayarlarla yapılan beş ölçümde taşma 18.487 ile 18.822 çağrı arasında oldu. Yığın -Xss512k seçeneğiyle yarıya indirildiğinde derinlik 6.235'e düştü. Aynı JVM içinde ikinci kez denendiğinde, derlenmiş kodun çerçeveleri küçüldüğü için 41.480 çağrıya kadar inilebildi. Sonuç olarak varsayılan yığınla birkaç on bin çağrı derinliği güvenli sınırın ötesidir.

Bu hatanın iki önemli özelliği vardır. Birincisi, derleyici onu yakalamaz; sorun ancak çalışma zamanında ortaya çıkar. Derleyici her yolun bir return ile bittiğini görür ve metodu geçerli sayar; değerlerin taban duruma ulaşıp ulaşmayacağını bilemez. İkincisi, hata iletisinin altındaki izleme listesi (stack trace) tanıdık bir görüntü verir: aynı satır (Toplam.java:6) alt alta yüzlerce kez tekrarlanır. JVM izleme listesinin en çok 1024 satırını yazdırır. Aynı satırın tekrar tekrar görünmesi sonsuz özyinelemenin işaretidir.

Çözüm üç yoldan biridir. Taban durum genişletilir (n <= 1 ya da n <= 0). Girdi metodun başında denetlenir ve geçersizse bir istisna fırlatılır. Problem doğası gereği çok derinse, örneğin bir milyon elemanlı bir liste dolaşılıyorsa, özyineleme yerine döngü kullanılır.

3.5.4.3Özyinelemeli düşünme

Özyinelemeli bir metot yazarken dört adım izlenir:

1. Küçültme: problem, kendisinin daha küçük bir kopyası cinsinden ifade edilir.
2. Taban durum: cevabı doğrudan bilinen en küçük girdi bulunur.
3. Güven: küçük kopyanın doğru çözüldüğü varsayılır; çağrının içi zihinde açılmaz.
4. Birleştirme: küçük cevaptan büyük cevap kurulur.

Üçüncü adım en zor olanıdır ve inanç sıçraması (leap of faith) diye anılır. Yeni başlayanlar bir özyinelemeli çağrı gördüklerinde onun içine girip bütün zinciri kafalarında açmaya çalışır. Küçük örneklerde bu işe yarar, ama Hanoi kuleleri gibi örneklerde hızla içinden çıkılmaz hâle gelir. Güven adımı şunu söyler: metot n − 1 için doğru çalışıyorsa n için de doğru çalıştığı gösterilebiliyorsa, metot her n için doğrudur. Bu, matematikteki tümevarımın ta kendisidir. Taban durum tümevarımın başlangıç adımı, özyinelemeli adım ise tümevarım adımıdır.

int basamakSayisi(int n) {
    if (n < 10) {                       // taban durum
        return 1;
    }
    return 1 + basamakSayisi(n / 10);   // küçült + birleştir
}

basamakSayisi(48729) 5, basamakSayisi(7) doğrudan 1 döndürür. Çağrılar 48729 → 4872 → 487 → 48 → 4 diye ilerler; beş çağrının sonuncusu taban durumdur. Kodda else yoktur. Taban durum return ile bittiği için sonraki satıra yalnız n >= 10 iken gelinir. Bu yazım, özyinelemeli metotlarda sık görülür: önce taban durum elenir, kalan gövde genel durumu işler.

Metodun negatif sayılarda da çalıştığına dikkat edilmelidir. −45 için -45 < 10 doğrudur ve sonuç 1 olur; bu yanlıştır. Negatif girdiler önemliyse metodun başına bir işaret düzeltmesi eklenir. Bu düzeltmenin nasıl yapıldığı rakamlar toplamı örneğinde görülür.

3.5.4.4İnişte ve dönüşte yapılan iş

Özyinelemeli bir metotta iş iki yerde yapılabilir: kendini çağırmadan önce ya da çağrı döndükten sonra. Bu fark, özellikle ekrana yazdırma gibi sırası görünen işlerde çok belirgindir. Aşağıdaki iki metot yalnız iki satırın sırasıyla ayrılır:

static void yaz(int n) {
    if (n == 0) return;
    System.out.print(n + " ");
    yaz(n - 1);
}
static void yaz2(int n) {
    if (n == 0) return;
    yaz2(n - 1);
    System.out.print(n + " ");
}
static int gizem(int a, int b) {
    if (b == 0) return 0;
    return a + gizem(a, b - 1);
}

yaz(3), sayıyı yazdırıp sonra kendini çağırır. Yazdırma inişte yapılır ve çıktı 3 2 1 olur. yaz2(3) ise önce kendini çağırır, yazdırmayı dönüşe bırakır. yaz2(3), yaz2(2)'yi, o da yaz2(1)'i, o da yaz2(0)'ı çağırır. yaz2(0) hiçbir şey yazmadan döner. Ardından en derindeki çerçeve olan yaz2(1) 1'i yazar, sonra yaz2(2) 2'yi, en son yaz2(3) 3'ü. Çıktı 1 2 3'tür.

Aynı kodda üçüncü bir metot, gizem, bulunur. gizem(4, 3) şöyle açılır: 4 + gizem(4, 2) = 4 + 4 + gizem(4, 1) = 4 + 4 + 4 + gizem(4, 0) = 4 + 4 + 4 + 0 = 12. Metot a × b'yi, a'yı b kez toplayarak hesaplar. Taban durum b == 0'dır ve ilerleme b'nin 1 azalmasıyla sağlanır. Ama gizem(4, -1) çağrısında b −1, −2, … diye azalır ve hiçbir zaman 0 olmaz. Sonuç yine StackOverflowError'dır. İkinci kural, ilerlemenin taban durumun yönünde olmasını ister; yalnız “değişiyor” olması yetmez.

Dönüşte yapılan iş, özyinelemenin en güçlü yanlarından biridir. Bir sayının ikili gösterimini yazdırmak bunun güzel bir örneğidir. Kalanlar (n % 2) en düşük basamaktan başlayarak bulunur, ama en yüksek basamaktan başlayarak yazdırılmalıdır. Dönüşte yazdıran bir metot bu ters çevirmeyi kendiliğinden yapar:

static void ikili(int n) {
    if (n > 1) {
        ikili(n / 2);
    }
    System.out.print(n % 2);
}

ikili(13), 13 → 6 → 3 → 1 diye iner. Dipte ikili(1) 1 % 2 = 1'i yazar. Dönüşte sırasıyla 3 % 2 = 1, 6 % 2 = 0 ve 13 % 2 = 1 yazılır. Çıktı 1101'dir: 13 = 8 + 4 + 1. Döngüyle aynı işi yapmak için kalanları bir dizide toplayıp ters sırada yazdırmak gerekirdi. Burada o dizinin işini çağrı yığını görür.

3.5.5Örnekler

Bu kesimdeki dört örnek, özyinelemenin farklı yüzlerini gösterir. Rakamlar toplamında problem sayının basamaklarına göre küçülür. Palindromda dizgi iki uçtan kısalır ve iki ayrı taban durum vardır. Öklid algoritmasında dönüşte hiçbir iş yapılmaz. Hanoi kulelerinde ise metot kendini iki kez çağırır ve döngüyle yazması zor bir problem birkaç satıra iner.

3.5.5.1Rakamlar toplamı

Bir tam sayının rakamlarının toplamı, örneğin 48729 için 4 + 8 + 7 + 2 + 9 = 30, özyinelemeyle şöyle bulunur:

int rakamlarToplami(int n) {
    if (n < 0) {
        return rakamlarToplami(-n);
    } else if (n < 10) {
        return n;
    } else {
        return rakamlarToplami(n / 10) + (n % 10);
    }
}

Metodun üç dalı vardır. İkinci ve üçüncü satırlar negatif sayıyı ele alır: işaret değiştirilir ve aynı metot pozitif sayıyla yeniden çağrılır. Rakamların toplamı işaretten bağımsızdır; −48729'un rakamları da 4, 8, 7, 2, 9'dur. Dördüncü ve beşinci satırlar taban durumdur: tek basamaklı bir sayının rakamları toplamı kendisidir. Son dal genel durumdur: son basamak ile kalan basamakların toplamı toplanır.

Parçalama iki tam sayı işlemiyle yapılır (Şekil 3.5.7). n / 10, iki tam sayı arasında bölme olduğu için kesirli kısmı atar ve son basamağı silinmiş sayıyı verir: 48729 / 10 = 4872. n % 10, 10'a bölümden kalanı, yani son basamağı verir: 48729 % 10 = 9. Her çağrıda sayı bir basamak kısalır; ilerleme garantilidir. Açılım şöyledir:

rakamlarToplami(-48729)
  = rakamlarToplami(48729)
  = rakamlarToplami(4872) + 9
  = (rakamlarToplami(487) + 2) + 9
  = ((rakamlarToplami(48) + 7) + 2) + 9
  = (((rakamlarToplami(4) + 8) + 7) + 2) + 9
  = (((4 + 8) + 7) + 2) + 9
  = ((12 + 7) + 2) + 9
  = (19 + 2) + 9
  = 21 + 9
  = 30

İlk çağrı yalnız işareti düzeltir. Sonraki her adımda son basamak (9, 2, 7, 8) bekleyen bir toplama olarak dışarıda kalır. Taban durum rakamlarToplami(4) → 4'tür. Dönüşte toplamlar içten dışa yapılır: 4 + 8 = 12, 12 + 7 = 19, 19 + 2 = 21, 21 + 9 = 30. Toplam altı çağrı yapılır: bir işaret düzeltmesi ve beş basamak. Genel olarak d basamaklı bir sayı için d çağrı (negatifse d + 1) yapılır; süre ve bellek O(d)'dir.

Daha kısa bir örnek, rakamlarToplami(-357), çağrı yığınıyla birlikte Tablo 3.5.7'de izlenmiştir. Kısalık için metot adı r diye yazılmıştır.

static int rakamlarToplami(int n) {
    if (n < 0) {
        return rakamlarToplami(-n);
    } else if (n < 10) {
        return n;
    } else {
        return rakamlarToplami(n / 10) + (n % 10);
    }
}

public static void main(String[] args) {
    System.out.println(rakamlarToplami(-357));
}

Dört çağrı yapılır: bir işaret düzeltmesi ve üç basamak. Sonuç 3 + 5 + 7 = 15'tir (Şekil 3.5.8).

3.5.5.2Palindrom kontrolü

Bir dizginin palindrom olup olmadığı dıştan içe doğru bakılarak anlaşılır. İlk ve son karakter aynıysa, bu iki karakter atıldığında kalan dizginin de palindrom olması gerekir (Şekil 3.5.9). Bu, özyinelemeli bir tanımdır:

static boolean palindromMu(String s) {
    if (s.length() <= 1) {
        return true;
    } else if (s.charAt(0) == s.charAt(s.length() - 1)) {
        return palindromMu(s.substring(1, s.length() - 1));
    }
    return false;
}

Kod iki String metodunu kullanır. s.charAt(i), dizginin i. karakterini verir; indisler 0'dan başlar, son karakterin indisi s.length() - 1'dir. s.substring(1, s.length() - 1) ise 1. indisten başlayıp s.length() - 1. indisin hemen öncesinde biten parçayı verir; yani ilk ve son harfi atılmış dizgiyi. substring'in ikinci parametresi parçaya dâhil değildir.

Metotta iki taban durum vardır. Uzunluk 1 ya da 0 ise dizgi palindromdur ve true döner. Boş dizgi, çift uzunluklu palindromlarda ortaya çıkar: “abba” → “bb” → “” diye kısalır. Uçlar farklıysa dizgi palindrom değildir ve false döner; içerisine bakmaya gerek yoktur. Bu ikinci taban durum, if ve else if'in ikisi de tutmadığında son satırdaki return false; ile karşılanır.

Son satır önemli bir ayrıntıyı gösterir: karşılaştırma büyük-küçük harfe duyarlıdır. 'K' ile 'k' farklı karakterlerdir ve “Kayak” palindrom sayılmaz. “ey edip adanada pide ye” ise boşluklarıyla birlikte simetrik olduğu için true verir. Boşluk ve noktalama içeren tümcelerde önce bu karakterlerin atılması ve harflerin küçültülmesi gerekir.

“racecar” sözcüğü için yapılan çağrılar Tablo 3.5.9'da izlenmiştir.

Dördüncü çağrı taban durumdur (Şekil 3.5.10). Dönüşte her çerçeve aldığı true'yu değiştirmeden yukarı aktarır; dönüşte yapılacak başka bir iş yoktur. Sonuç: “racecar” bir palindromdur.

Maliyet açısından bu metot ilk bakışta göründüğünden pahalıdır. n uzunluklu bir dizgi için yaklaşık n/2 çağrı yapılır. Ama her çağrıdaki substring, Java'da yeni bir dizgi nesnesi oluşturur ve karakterleri kopyalar. Kopyalanan karakterlerin toplamı (n − 2) + (n − 4) + … ≈ n²/4'tür. Yani süre O(n²), bellek de bekleyen dizgiler yüzünden O(n²)'dir. Dizgi yerine iki indis taşıyan bir sürüm, örneğin palindromMu(s, bas, son), bu kopyalamayı önler ve O(n) sürede çalışır.

İndisli sürüm şöyledir:

static boolean palindromMu(String s, int bas, int son) {
    if (bas >= son) {
        return true;
    } else if (s.charAt(bas) != s.charAt(son)) {
        return false;
    }
    return palindromMu(s, bas + 1, son - 1);
}

Dizgi hiç kısalmaz; onun yerine incelenen parçanın sınırları daralır. bas parçanın ilk, son son karakterinin indisidir. İlk çağrı palindromMu(s, 0, s.length() - 1) biçiminde yapılır. Taban durumlar aynı mantığı izler. bas >= son ise parçada en çok bir karakter kalmıştır ve sonuç true'dur. Uçlar farklıysa sonuç false'tur. İlerleme, iki indisin birbirine yaklaşmasıyla sağlanır: aradaki fark her çağrıda 2 azalır. “racecar” için çağrılar (0, 6), (1, 5), (2, 4), (3, 3) olur ve dördüncü çağrı taban durumdur. Boş dizgi için ilk çağrı (0, −1) olur ve hemen true döner. Bu teknik, dizgi ve dizi üzerinde çalışan özyinelemeli metotlarda yaygındır: veriyi kopyalamak yerine sınırları parametre olarak taşımak.

3.5.5.3En büyük ortak bölen

İki pozitif tam sayının en büyük ortak böleni (EBOB), ikisini de kalansız bölen en büyük sayıdır. İngilizce adı greatest common divisor olduğu için kodda metot gcd diye adlandırılmıştır. Yaklaşık 2300 yıllık Öklid algoritması EBOB'u bölme kalanlarıyla bulur:

static int gcd(int x, int y) {
    if (y == 0) {
        return x;
    }
    return gcd(y, x % y);
}

Taban durum y == 0'dır: bir sayının 0 ile EBOB'u kendisidir. Genel durumda x yerine y, y yerine x % y geçer. Bağıntının doğruluğu şuna dayanır: x ile y'yi bölen her sayı x − k·y'yi de böler, dolayısıyla x mod y'yi de böler. Ortak bölenler kümesi her adımda aynı kalır, yalnız sayılar küçülür.

İlerleme kalanın küçülmesiyle sağlanır. x mod y her zaman y'den küçüktür; ikinci parametre her çağrıda kesin olarak azalır ve sonunda 0'a ulaşır. Parametrelerin sırası da önemli değildir. gcd(93, 444) çağrısında 93 % 444 = 93 olduğu için ilk adım yalnız iki sayının yerini değiştirir ve gcd(444, 93) olur.

gcd(444, 93)
  = gcd(93, 72)     // 444 % 93 = 72
  = gcd(72, 21)     // 93 % 72 = 21
  = gcd(21, 9)      // 72 % 21 = 9
  = gcd(9, 3)       // 21 % 9 = 3
  = gcd(3, 0)       // 9 % 3 = 0
  = 3

Altı çağrı yapılır ve EBOB(444, 93) = 3 bulunur (Tablo 3.5.10). Bu metodun öncekilerden farkı dönüşte görülür. return gcd(y, x % y); satırında çağrı döndükten sonra yapılacak hiçbir iş yoktur. Son çağrının bulduğu 3, her çerçeveden değişmeden geçerek main'e ulaşır. Böyle çağrılara kuyruk çağrısı denir. Başka bir örnek: gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) → 6.

Öklid algoritması çok hızlıdır. Her iki adımda ilk sayı en az yarıya iner; bu yüzden çağrı sayısı sayıların basamak sayısıyla orantılıdır, yani O(log min(x, y))'dir. En kötü durum ardışık iki Fibonacci sayısıyla ortaya çıkar; örneğin gcd(89, 55) on çağrı yapar.

3.5.5.4Hanoi kuleleri

Hanoi kuleleri, 1883'te Édouard Lucas'nın ortaya attığı bir bulmacadır. Üç çubuk (A, B, C) vardır ve A çubuğunda büyükten küçüğe dizilmiş n disk bulunur. Disklerin hepsi C'ye taşınacaktır. İki kural vardır: her hamlede yalnız bir disk, bir çubuğun en üstündeki disk taşınır; büyük bir disk hiçbir zaman küçük bir diskin üstüne konmaz.

Bulmaca döngüyle düşünüldüğünde zordur, ama özyinelemeli düşünüldüğünde çözüm kendiliğinden ortaya çıkar. En büyük disk C'ye ancak üstündeki n − 1 disk başka bir yere, yani yardımcı çubuk B'ye çekildiğinde taşınabilir. Öyleyse çözüm üç adımdır: üstteki n − 1 disk yardımcıya, en büyük disk hedefe, sonra n − 1 disk yardımcıdan hedefe taşınır. Birinci ve üçüncü adımlar, bir disk eksik aynı problemdir. Taban durum tek disktir: doğrudan taşınır.

public class HanoiKuleleri {
    static void coz(int n, char kaynak,
                    char hedef, char yardimci) {
        if (n == 1) {   // tek disk: doğrudan taşı
            System.out.println(n + ": " + kaynak + "->" + hedef);
        } else {
            coz(n - 1, kaynak, yardimci, hedef);
            System.out.println(n + ": " + kaynak + "->" + hedef);
            coz(n - 1, yardimci, hedef, kaynak);
        }
    }
    public static void main(String[] args) {
        coz(3, 'A', 'C', 'B');
    }
}

1: A->C
2: A->B
1: C->B
3: A->C
1: B->A
2: B->C
1: A->C

coz metodu dört parametre alır: disk sayısı ve kaynak, hedef, yardımcı çubukların adları. Çubuk adları char tipindedir. Özyinelemeli çağrılarda çubukların rolleri değişir. İlk çağrıda coz(n - 1, kaynak, yardimci, hedef) yazılır: n − 1 disk kaynaktan yardımcıya taşınır ve bu sırada asıl hedef yardımcı rolünü üstlenir. Üçüncü satırdaki çağrıda coz(n - 1, yardimci, hedef, kaynak) yazılır: n − 1 disk yardımcıdan hedefe taşınır, bu kez kaynak boş kaldığı için yardımcı olur. Yazdırılan satırdaki sayı, taşınan diskin numarasıdır; en küçük disk 1'dir.

Hamleler Tablo 3.5.11'de, yapan çağrıyla birlikte verilmiştir. İlk üç hamle coz(2, A, B, C)'nin işidir; dördüncü hamle coz(3, …)'ün ortadaki satırıdır; son üç hamle coz(2, B, C, A)'nın işidir (Şekil 3.5.11). Çağrı yığını hiçbir anda üç coz çerçevesinden derine inmez; yığın derinliği disk sayısına eşittir.

Hamle sayısı H(n), metodun yapısından okunur: n − 1 disk için iki kez çözüm ve bir hamle. H(n) = 2 · H(n − 1) + 1 ve H(1) = 1'dir. Buradan H(2) = 3, H(3) = 7, H(4) = 15 bulunur ve genel olarak H(n) = 2ⁿ − 1'dir. Bu sayı çok hızlı büyür. 10 disk için 1023 hamle gerekir. Efsanedeki 64 disk için 2⁶⁴ − 1 ≈ 1,8 × 10¹⁹ hamle gerekir; saniyede bir hamleyle bu, yaklaşık 585 milyar yıl sürer. Metodun süresi de O(2ⁿ)'dir, ama bu kez israf yoktur: her hamle gereklidir ve daha kısa bir çözüm bulunmaz.

Bulmacanın ilginç bir özelliği, ilk hamlenin disk sayısına bağlı olmasıdır. Ölçülen ilk hamleler, n tek ise 1: A->C, n çift ise 1: A->B'dir. Örneğin 4 disk için 15 hamle yapılır ve ilk hamle en küçük diski yardımcı çubuğa taşır. Döngüyle yazılmış Hanoi çözümleri bu tür gözlemlere dayanır ve özyinelemeli sürümden çok daha uzundur. Özyinelemeli sürüm ise problemin yapısını olduğu gibi yansıttığı için birkaç satırdır.

3.5.6Verimlilik

Özyinelemeli bir çözüm kısa ve açık olabilir, ama bu onun hızlı ya da hafif olduğu anlamına gelmez. Bu kesim özyinelemenin bedelini üç başlıkta toplar: her çağrının kendi maliyeti, yığın derinliği ve aynı değerlerin defalarca hesaplanması. Ardından özyinelemeli metotların döngüye nasıl çevrildiği gösterilir.

3.5.6.1Bir çağrının bedeli

Her metot çağrısında JVM bir iş yapar: yeni çerçeve açılır, parametreler kopyalanır, dönülecek yer kaydedilir. Dönüşte çerçeve silinir ve değer alttaki çerçeveye taşınır. Bir döngü turunda ise yalnız birkaç değişken güncellenir. Bu yüzden aynı işi yapan özyinelemeli metot çoğu zaman döngüden biraz yavaştır.

Daha önemli fark bellektedir. Özyinelemeli çağrılar yapıldıkça bekleyen kısmi sonuçlar, yani her çerçevedeki 4 * ? gibi yarım işler, çağrı yığınında birikir. Tablo 3.5.12 üç ana bedeli özetler.

Sorunlu durumlarda çözüm ilerlemeli sürüme geçmektir. Faktöriyel bunun en basit örneğidir: faktoriyel(100000) özyinelemeli sürümde, sonucun taşması bir yana, büyük olasılıkla StackOverflowError ile biter. JDK 21 ile yapılan denemede gerçekten de böyle oldu. Döngülü sürüm aynı çağrıyı tek çerçevede ve bir saniyeden kısa sürede bitirir; sonucu yanlış olsa da hiçbir zaman yığın taşmasına uğramaz.

3.5.6.2Tekrarlanan hesaplama

Ağaç özyinelemesinin asıl sorunu bellek değil, zamandır. Şekil 3.5.12, fibonacci(5)'in çağrı ağacını gösterir. Ağaçta 15 düğüm vardır. Kırmızı düğümler, daha önce hesaplanmış değerlerin yeniden hesaplanmasıdır: fib(3) iki kez, fib(2) üç kez hesaplanır.

Tekrar n büyüdükçe katlanarak artar. Çağrı sayısı Ç(n) = 2F(n + 1) − 1 formülüyle bulunur ve n 1 artınca yaklaşık 1,6 katına çıkar; bu oran altın orandır. Tablo 3.5.13, JDK 21 ile ölçülen çağrı sayılarını ve süreleri verir.

Tablodaki her on adımda çağrı sayısı yaklaşık 120 katına çıkar. fibonacci(40) yarım saniye sürer. Bu hızla fibonacci(50) iki dakikayı bulur; yani dakikalar alır. Bu koda Java'ya özgü bir sorun daha eklenir: F(47) = 2.971.215.073, int'in sınırını aşar. int döndüren fibonacci(50) iki dakika çalıştıktan sonra −298632863 gibi anlamsız bir sayı döndürür. Doğru değer 12.586.269.025'tir.

Sorunun kaynağı, metodun daha önce hesapladığı değerleri unutmasıdır. fibonacci(40)'ın ihtiyaç duyduğu farklı değer sayısı yalnız 41'dir (F(0)'dan F(40)'a kadar). Her biri bir kez hesaplanıp saklansa birkaç düzine işlem yeterdi. Bunu yapmanın iki yolu vardır: döngüye çevirmek ve bellekleme.

3.5.6.3Döngüye çevirme

Doğrusal özyinelemeli metotlar, yani kendini bir kez çağıran metotlar, genellikle kolayca döngüye çevrilir. Yöntem şudur: dönüşte yapılan iş, döngüde bir biriktirici değişkenle yapılır. Faktöriyelin iki sürümü yan yana şöyledir:

int faktoriyel(int n) {
    if (n == 0 || n == 1) {
        return 1;
    } else {
        return n * faktoriyel(n - 1);
    }
}

int faktoriyel(int n) {
    int carpim = 1;
    for (int i = 1; i <= n; i++) {
        carpim *= i;
    }
    return carpim;
}

Döngülü sürümde carpim 1'den başlar; çarpmanın etkisiz elemanı 1'dir. Döngü i'yi 1'den n'ye kadar dolaştırır ve her turda carpim'ı i ile çarpar. faktoriyel(5) için carpim sırasıyla 1, 1, 2, 6, 24, 120 olur. n = 0 için döngü hiç dönmez ve 1 döner; 0! = 1 ayrıca yazılmaya gerek kalmadan karşılanır. İki sürüm aynı sonucu verir, ama bellek kullanımları farklıdır (Şekil 3.5.13).

Rakamlar toplamı ve palindrom da aynı yolla döngüye çevrilir:

int rakamlarToplami(int n) {
    int toplam = 0;
    int kalan = Math.abs(n);
    while (kalan > 0) {
        toplam += kalan % 10;
        kalan /= 10;
    }
    return toplam;
}

kalan, sayının mutlak değeriyle başlar. Her turda son basamak toplam'a eklenir ve kalan'dan atılır. 48729 için toplam 9, 11, 18, 26, 30 olur; kalan 4872, 487, 48, 4, 0 olur ve döngü biter. rakamlarToplami(-48729) 30 döndürür; özyinelemeli sürümle aynıdır. İşaret Math.abs ile atılır, çünkü rakamların toplamı negatif olamaz. Bu sürüm Integer.MIN_VALUE için yığın taşmasına uğramaz, ama Math.abs negatif bir değer döndürdüğü için döngüye hiç girmez ve 0 verir; doğru cevap 47'dır.

boolean palindromMu(String s) {
    s = s.toLowerCase();
    int uzunluk = s.length();
    for (int i = 0; i < uzunluk / 2; i++) {
        if (s.charAt(i) != s.charAt(uzunluk - 1 - i)) {
            return false;
        }
    }
    return true;
}

Döngülü palindrom, dizgiyi kısaltmak yerine iki uçtan içe doğru ilerleyen indisler kullanır. i baştan, uzunluk - 1 - i sondan ilerler. Döngü dizginin yarısına kadar döner; tek uzunlukta ortadaki karakter kendisiyle eşleşir ve bakılmaz. İlk farklı çiftte false döner. Hiç farklı çift bulunmazsa döngü biter ve true döner. Bu sürüm başta toLowerCase() çağırdığı için “Kayak”'ı da palindrom sayar.

“Kepek” için izleme Tablo 3.5.14'te verilmiştir.

static boolean palindromMu(String s) {
    s = s.toLowerCase();
    int uzunluk = s.length();
    for (int i = 0; i < uzunluk / 2; i++) {
        if (s.charAt(i) != s.charAt(uzunluk - 1 - i)) {
            return false;
        }
    }
    return true;
}

public static void main(String[] args) {
    System.out.println(palindromMu("Kepek"));
}

Ortadaki 'p' hiç karşılaştırılmaz; kendisiyle eşleşmesi zaten kesindir (Şekil 3.5.14). Tek çerçeve kullanılır ve özyinelemeli sürümdeki gibi her adımda yeni bir dizgi üretilmez. Süre O(n), ek bellek ise toLowerCase()'in ürettiği tek kopya dışında O(1)'dir.

Ağaç özyinelemesi de döngüye çevrilebilir, ama bu kez biriktirici tek değişken değildir. Fibonacci'de her terim önceki iki terime bağlıdır; döngü de bu iki terimi taşır:

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

a ve b, ardışık iki Fibonacci sayısıdır ve F(0) = 0, F(1) = 1 ile başlar. Her turda ikisi birden bir adım ileri kayar: yeni a eski b, yeni b eski toplam olur. Geçici yeni değişkeni olmadan yazılırsa eski a kaybolur. n turdan sonra a = F(n)'dir. fibonacci(10) için (a, b) çifti (0, 1), (1, 1), (1, 2), (2, 3), (3, 5), (5, 8), (8, 13), (13, 21), (21, 34), (34, 55), (55, 89) diye ilerler ve 55 döner. Bu sürüm n tur döner: süre O(n), bellek O(1)'dir. fibonacci(50) = 12586269025'i ve fibonacci(90)'ı anında verir. Özyinelemeli sürümün 331 milyon çağrıyla yaptığı işi bu döngü 40 turda yapar.

3.5.6.4Özyineleme mi döngü mü?

İki yaklaşım aynı tekrarın iki farklı yazımıdır. Tablo 3.5.15 aralarındaki farkları özetler.

Hata satırındaki fark ilginçtir. Bozuk bir döngü hiç bitmez ve program donar; dışarıdan durdurulması gerekir. Bozuk bir özyineleme ise kısa sürede yığını doldurur ve bir hata iletisiyle durur. Hatayı bulmak açısından ikincisi daha kolaydır, çünkü izleme listesi sorunun yerini gösterir.

Her özyinelemeli çözüm döngüyle yazılabilir; tersi de doğrudur. Doğrusal özyinelemede bu çeviri bir biriktiriciyle kolayca yapılır. Hanoi gibi ağaç özyinelemelerinde ise döngülü sürüm, çağrı yığınının işini kendi tuttuğu bir yığın veri yapısıyla taklit etmek zorundadır ve kod uzar. Seçim üç ölçüte göre yapılır. Kodun açıklığı özyinelemeden yanaysa ve derinlik küçükse (Hanoi'de disk sayısı, dengeli bir ağaçta yükseklik) özyineleme uygundur. Derinlik girdiyle doğrusal büyüyorsa (bir milyon elemanlı liste) döngü seçilir. Performans kritikse ve ağaç özyinelemesi tekrar içeriyorsa döngü ya da bellekleme gerekir.

3.5.7Kuyruk özyinelemesi

Özyinelemeli metotlarda bellek sorunu, dönüşte yapılacak işlerin yığında beklemesinden doğar. Dönüşte yapılacak hiçbir iş kalmazsa çerçevelerin beklemesine de gerek kalmaz. Kuyruk özyinelemesi bu fikre dayanır.

3.5.7.1Kuyruk çağrısı ve biriktirici

Ayrım bir satırda görülür. Sıradan faktöriyel ile kuyruk özyinelemeli faktöriyelin özyinelemeli satırları şöyledir:

return n * faktoriyel(n - 1);
// çağrı döndükten SONRA çarpma var

return faktoriyel(n - 1, n * birikim);
// çarpma çağrıdan ÖNCE; son iş çağrı

Soldaki satırda önce faktoriyel(n - 1) çağrılır, döndükten sonra sonuç n ile çarpılır. Çarpma bekleyen iştir ve n'nin değeri bu yüzden çerçevede saklanmak zorundadır. Sağdaki satırda çarpma çağrıdan önce, argüman hesaplanırken yapılır. n * birikim değeri yeni çağrıya parametre olarak gönderilir. Çağrı döndüğünde gelen değer olduğu gibi döndürülür; yapılacak başka iş yoktur (Şekil 3.5.15).

Bu biçim, derleyicinin kuyruk çağrısı optimizasyonu (tail call optimization, TCO) yapmasını mümkün kılar. Bekleyen iş olmadığı için yeni çağrı, eski çerçeveyi yeniden kullanabilir; çağrı bir döngü gibi işlenir ve çerçeveler yığılmaz. Bellek O(n)'den O(1)'e iner ve derinlik sınırı ortadan kalkar.

Java ise bu optimizasyonu yapmaz. Ne javac derleyicisi ne de JVM, kuyruk çağrılarını döngüye çevirir. Kuyruk özyinelemeli Java kodu yine her çağrı için bir çerçeve açar ve O(n) yığın kullanır; derinlik sınırı da aynen geçerlidir. Kuyruk çağrısı optimizasyonu Scheme dilinde zorunludur. Scala'da derleyici kendini çağıran kuyruk özyinelemelerini döngüye çevirir ve @tailrec işareti bunu denetletir. Kotlin'de tailrec anahtar kelimesiyle işaretlenen metotlar döngüye çevrilir. Java'da kuyruk özyinelemesinin değeri, döngüye çevirmeyi kolaylaştırmasıdır: biriktiricili bir kuyruk özyinelemesi, neredeyse mekanik olarak bir while döngüsüne dönüştürülür.

3.5.7.2Örnekler ve sarmalayıcı metot

Doğrusal özyinelemeli bir metot, bir biriktirici parametre eklenerek kuyruk özyinelemeli yapılır. Rakamlar toplamı ve faktöriyel için sonuç şöyledir:

int rakamlarToplami(int sayi, int toplam) {
    if (sayi == 0) {
        return toplam;
    } else {
        return rakamlarToplami(sayi / 10,
                               toplam + sayi % 10);
    }
}

Son basamak çağrıdan önce toplam'a eklenir. rakamlarToplami(48729, 0) şöyle ilerler: (48729, 0) → (4872, 9) → (487, 11) → (48, 18) → (4, 26) → (0, 30). sayi == 0 olunca biriktiricideki 30 döner. Bu sürüm yalnız n ≥ 0 için doğrudur; rakamlarToplami(-357, 0), Java'nın negatif sayılarda kalanı negatif vermesi yüzünden −15 döndürür.

int faktoriyel(int n, int birikim) {
    if (n == 0) {
        return birikim;
    } else {
        return faktoriyel(n - 1, n * birikim);
    }
}

Faktöriyelde çarpım çağrıdan önce birikim'e katılır ve faktoriyel(5, 1) 120 döndürür. Taban durum bu kez n == 0'dır; o anda biriktiricide sonuç hazırdır.

Biriktiricinin başlangıç değeri, işlemin etkisiz elemanıdır: toplama için 0, çarpma için 1. Bu ayrıntı metodu kullanan kişiye yük olmamalıdır. Bu yüzden biriktiriciyi gizleyen tek parametreli bir sarmalayıcı metot yazılır:

static int faktoriyel(int n) {
    return faktoriyel(n, 1);
}

İki metot aynı adı taşır, ama parametre sayıları farklıdır. Java bu durumda çağrıdaki argüman sayısına bakarak hangisinin kastedildiğini anlar; bu özelliğe metot aşırı yüklemesi (method overloading) denir. Kullanıcı faktoriyel(5) yazar ve biriktiriciyi hiç görmez.

Bir de karşı örnek: ters metodu bir dizgiyi ters çevirir.

static String ters(String s) {
    if (s.isEmpty()) return "";
    return ters(s.substring(1)) + s.charAt(0);
}

ters("java"), ters("ava") + 'j' olarak hesaplanır; o da ters("va") + 'a' ister ve böyle sürer. Sonuç "avaj"'dır. Bu metot kuyruk özyinelemeli değildir, çünkü çağrı döndükten sonra birleştirme (+) yapılır. gcd ise kuyruk özyinelemelidir: son işi çağrının kendisidir.

Fibonacci'nin kuyruk özyinelemeli sürümü, döngülü sürümdeki iki değişkeni parametre olarak taşır:

static long fibK(int n, long a, long b) {
    if (n == 0) {
        return a;
    }
    return fibK(n - 1, b, a + b);
}

a ve b yine ardışık iki terimdir ve ilk çağrı fibK(n, 0, 1)'dir. Her çağrı n'yi 1 azaltır ve çifti bir adım kaydırır. n 0'a indiğinde a, istenen terimdir. fibK(10, 0, 1) 55 döndürür ve yalnız 11 çağrı yapar. Ağaç özyinelemeli sürümle karşılaştırıldığında fark çarpıcıdır: aynı bağıntı, sonucun nasıl taşındığına göre 177 çağrıyla ya da 11 çağrıyla hesaplanır. Döngülü sürüm ile kuyruk özyinelemeli sürüm satır satır eşleşir. Döngü değişkenleri parametrelere, döngü koşulu taban durumun tersine, bir tur da bir çağrıya karşılık gelir.

3.5.7.3faktoriyel(4, 1) çağrısının izlenmesi

static int faktoriyel(int n, int birikim) {
    if (n == 0) {
        return birikim;
    } else {
        return faktoriyel(n - 1, n * birikim);
    }
}

Bütün çarpmalar inişte yapılır (Tablo 3.5.16). Taban duruma varıldığında sonuç zaten birikim'dedir. Dönüşte hiçbir hesap yapılmaz; 24 aynen yukarı aktarılır. Sıradan faktöriyelle karşılaştırıldığında çarpmaların sırası da tersine dönmüştür: burada 4, 3, 2, 1 sırasıyla çarpılır.

Şekil 3.5.16 önemli bir gerçeği gösterir: Java kuyruk çağrısını optimize etmediği için beş faktoriyel çerçevesinin hepsi yine de yığına girer. Kuyruk çağrısı optimizasyonu yapan bir dilde tek çerçeve yeterdi. Aynı metodun Java'daki döngü karşılığı şöyledir: while (n != 0) { birikim = n * birikim; n = n - 1; } return birikim;. Parametreler değişken olur, özyinelemeli çağrı ise bu değişkenlerin güncellenmesine dönüşür.

3.5.8Bellekleme

Ağaç özyinelemesindeki tekrarı gidermenin bir yolu döngüye geçmekti. İkinci yol, özyinelemeli yapıyı koruyup metoda bir hafıza vermektir. Metot bir değeri ilk kez hesapladığında onu bir yere yazar; aynı değer yeniden istenirse hesaplamadan okur.

3.5.8.1Belleklemeli Fibonacci

Java'da önbellek için en kolay araç Map'tir. Map, anahtarları değerlere eşleyen bir veri yapısıdır; burada anahtar n, değer F(n)'dir. Map<Integer, Long> yazımı, anahtarların Integer, değerlerin Long olduğunu belirtir. Map ilkel tipleri tutamadığı için int ve long yerine bunların sarmalayıcı sınıfları kullanılır; Java dönüşümü kendiliğinden yapar.

import java.util.HashMap;
import java.util.Map;

static Map<Integer, Long> hafiza = new HashMap<>();

static long fibonacci(int n) {
    if (hafiza.containsKey(n)) {
        return hafiza.get(n);    // daha önce hesaplandı
    }
    if (n == 0 || n == 1) {
        return n;
    }
    long sonuc = fibonacci(n - 1) + fibonacci(n - 2);
    hafiza.put(n, sonuc);        // sonucu sakla
    return sonuc;
}

Metodun gövdesi dört adımdan oluşur. Önce hafızaya bakılır: hafiza.containsKey(n), n anahtarı daha önce yazılmışsa true döndürür ve değer hafiza.get(n) ile okunup döndürülür. Hafızada yoksa taban durum sınanır. İkisi de değilse değer her zamanki gibi iki özyinelemeli çağrıyla hesaplanır. Son olarak hafiza.put(n, sonuc) sonucu saklar ve sonuç döndürülür.

hafiza bir alan (field) olarak, metodun dışında ve static tanımlanmıştır. Yerel değişken olsaydı her çağrıda yeniden ve boş olarak oluşturulur, hiçbir şey hatırlanmazdı. Bütün çağrıların aynı hafızayı paylaşması için onu metodun dışında tutmak gerekir. Dönüş tipi de long'a çevrilmiştir. Bellekleme büyük n'leri hızla hesaplanabilir kıldığı için int artık yetmez: fibonacci(90) anında 2880067194370816120 döndürür. long'a sığan en büyük Fibonacci sayısı F(92) = 7540113804746346429'dur.

Anahtarlar 0'dan başlayan ardışık tam sayılar olduğu için Map yerine bir dizi de kullanılabilir:

static long[] tablo = new long[93];

static long fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    if (tablo[n] != 0) {
        return tablo[n];
    }
    tablo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return tablo[n];
}

Dizinin boyu 93'tür, çünkü long'a sığan son terim F(92)'dir. Java yeni bir long dizisinin bütün elemanlarını 0 ile doldurur. Bu sürümde 0, “henüz hesaplanmadı” anlamına gelir. Bu kabul güvenlidir, çünkü n ≥ 2 için hiçbir Fibonacci sayısı 0 değildir. Dizi, Map'e göre daha az bellek kullanır ve daha hızlıdır. Sarmalayıcı nesneler oluşturulmaz, anahtar araması da tek bir indis erişimine iner. Bedeli esnekliktir: dizinin boyu önceden bilinmelidir ve anahtarlar küçük, negatif olmayan tam sayılar olmalıdır. fibonacci(90) bu sürümde de 2880067194370816120 döndürür.

3.5.8.2Belleklemeli fibonacci(4) izleme

static Map<Integer, Long> hafiza = new HashMap<>();
static long fibonacci(int n) {
    if (hafiza.containsKey(n)) {
        return hafiza.get(n);
    }
    if (n == 0 || n == 1) {
        return n;
    }
    long sonuc = fibonacci(n - 1) + fibonacci(n - 2);
    hafiza.put(n, sonuc);
    return sonuc;
}

İlk altı çağrı belleklemesiz sürümle aynıdır (Tablo 3.5.17). Fark yedinci çağrıda ortaya çıkar. fibonacci(4)'ün sağ terimi fibonacci(2)'dir ve bu değer beşinci çağrının sonunda hafızaya yazılmıştır. Metot ilk satırında onu bulur ve 1'i hemen döndürür. Belleklemesiz sürüm burada üç çağrı daha yapardı: fib(2), fib(1), fib(0). Toplam çağrı sayısı 9'dan 7'ye iner. Taban durum değerleri hafızaya yazılmaz; onlar zaten hesap gerektirmez.

3.5.8.3Çağrı ağacı ve kazanç

Belleklemenin etkisi n büyüdükçe çarpıcı hâle gelir. Şekil 3.5.18, belleklemeli fibonacci(5)'in çağrı ağacını gösterir. Sol kol 5'ten 0'a kadar bir kez hesaplanır. Sağdaki fib(2) ve fib(3) hafızadan gelir ve altlarında yeni dal açılmaz. 15 yerine 9 çağrı yapılır.

Genel olarak hafıza boşken fibonacci(n), n ≥ 1 için tam 2n − 1 çağrı yapar. Sol kol n'den 1'e inerken n çağrı yapılır. 2'den n'ye kadar her değer için sağ terim bir çağrı daha ister; bunlar n − 1 çağrıdır. Toplam n + (n − 1) = 2n − 1'dir. Üstel büyüme doğrusala inmiştir. Tablo 3.5.18 iki sürümü ölçümlerle karşılaştırır.

Süreler makineye göre değişir, oran değişmez. Son satırdaki belleklemesiz çağrı sayısı 2F(91) − 1'dir; saniyede bir milyar çağrıyla bile yaklaşık 300 yıl sürerdi. Belleklemeli sürüm aynı sonucu 179 çağrıda verir.

Bu kazancın bir bedeli vardır: bellek. Hafıza, n değeri kadar kayıt tutar ve her kayıt bir Integer ile bir Long nesnesi içerir. Bellekleme, hız için bellek harcamaktır. Fibonacci'de bu takas açıkça kazançlıdır; bazı problemlerde ise saklanacak sonuç sayısı belleğe sığmayacak kadar çok olabilir. Bir başka sınır yığındır: belleklemeli sürümün sol kolu hâlâ n çerçeve derinliğe iner. fibonacci(100000) belleklemeyle de StackOverflowError verir, üstelik sonucu long'a sığmaz.

3.5.8.4Belleklemeli faktöriyel

Aynı kalıp her özyinelemeli metoda uygulanabilir: önce hafızaya bak, yoksa hesapla, sakla, döndür.

static Map<Integer, Long> hafiza = new HashMap<>();

static long faktoriyel(int n) {
    if (hafiza.containsKey(n)) {
        return hafiza.get(n);
    }
    if (n == 0 || n == 1) {
        return 1;
    }
    long sonuc = n * faktoriyel(n - 1);
    hafiza.put(n, sonuc);
    return sonuc;
}

long sayesinde 20!'e kadar doğru sonuç alınır: faktoriyel(20) = 2432902008176640000. faktoriyel(21) ise taşar ve −4249290049419214848 döndürür; taşmış değer de hafızaya yazılır.

Burada ilginç bir durum vardır. Faktöriyel ağaç özyinelemesi değildir; tek bir faktoriyel(n) çağrısında hiçbir değer iki kez hesaplanmaz. Bu yüzden hafıza tek bir çağrıyı hızlandırmaz, hatta Map işlemleri yüzünden biraz yavaşlatır. Kazanç, program birçok kez faktöriyel istediğinde ortaya çıkar. hafiza statik olduğu için çağrılar arasında korunur. faktoriyel(10) çağrıldıktan sonra 1!'den 10!'e kadar değerler hafızadadır. Ardından faktoriyel(12) istenirse yalnız 12 × 11! ve 11 × 10! diye iki yeni çarpma yapılır; 10! hafızadan okunur. Kombinasyon gibi faktöriyeli defalarca kullanan hesaplarda bu kazanç anlamlıdır.

3.5.9Sık yapılan hatalar

Özyinelemeli kodlardaki hataların çoğu birkaç kalıba girer. Bazıları derleme sırasında, bazıları çalışma sırasında ortaya çıkar; en sinsileri ise hiçbir ileti vermez. Tablo 3.5.19 bu kalıpları JDK 21'in gerçek iletileriyle toplar.

Eksik return hatası, Java derleyicisinin koşulları değerlendirmemesinden doğar. Aşağıdaki metot bir sayının en büyük rakamını bulmak için yazılmıştır:

static int enBuyuk(int n) {
    if (n < 10) {
        return n;
    } else if (n % 10 > enBuyuk(n / 10)) {
        return n % 10;
    } else if (n % 10 <= enBuyuk(n / 10)) {
        return enBuyuk(n / 10);
    }
}

error: missing return statement
    }
    ^

İki else if koşulu birbirinin tersidir ve biri mutlaka doğrudur. Ama derleyici bunu anlamaz; koşulların değerini derleme sırasında hesaplamaz. Gördüğü şey, üç koşulun da yanlış olabileceği ve o durumda metodun değer döndürmeden biteceğidir. Son dal else yapılınca hata kaybolur. Aynı metotta ikinci bir sorun daha vardır: enBuyuk(n / 10) bir çağrıda üç kez hesaplanabilir. Bu da çağrı sayısını her basamakta üçe katlar. Doğru yazım, alt problemin sonucunu bir kez hesaplayıp bir değişkende tutmaktır: int geri = enBuyuk(n / 10); return Math.max(n % 10, geri);. Bu sürüm 48729 için 9 döndürür ve beş çağrı yapar.

Çağrının sonucunu kullanmamak, özellikle yeni başlayanlarda görülür. faktoriyel(n - 1); satırı geçerli bir Java deyimidir: metot çağrılır, değer hesaplanır ve sonra atılır. Derleyici bunun için uyarı vermez. Özyinelemeli çağrının döndürdüğü değer, ya return ifadesinin içinde kullanılmalı ya da bir değişkene yazılmalıdır.

Taşma ve gereksiz ağaç özyinelemesi en sinsi iki hatadır, çünkü hiçbiri ileti vermez. Program çalışır ve bir sonuç üretir. Taşma yanlış bir sayı verir. Ağaç özyinelemesi ise doğru sonucu çok geç verir. İkisini de önlemenin yolu, metodu yazarken girdinin ne kadar büyüyebileceğini düşünmek ve sınır değerlerle denemektir.

3.5.10Özet

• Özyineleme: bir metodun kendini daha küçük bir girdiyle çağırmasıdır. Java'da özel bir anahtar kelime gerekmez; metot gövdesinde kendi adını çağırır.
• Taban durum ve ilerleme: taban durum, doğrudan çözülen en küçük durumdur ve özyinelemeyi durdurur. Her çağrı taban duruma yaklaşmalıdır (n - 1, n / 10, substring, x % y). İki kuraldan biri bozulursa StackOverflowError alınır.
• Çağrı yığını: her çağrıya bir çerçeve açılır; çerçevenin kendi parametreleri ve yerel değişkenleri vardır. Çerçeveler LIFO sırasıyla kapanır. Varsayılan yığınla derinlik birkaç on bin çağrıyı geçemez; sınır JVM ayarına göre değişir.
• İniş ve dönüş: çağrıdan önce yapılan iş inişte, sonra yapılan iş dönüşte yürür. Dönüşte yazdıran metot sırayı ters çevirir (yaz2, ikili).
• Seriler: yineleme bağıntısı özyinelemeli metoda doğrudan çevrilir. Fibonacci ve Lucas kendini iki kez çağırır; Catalan ve Bell çağrıları döngü içinde yapar. int 12!'ye, long 20!'ye kadar yeter; taşma sessizdir.
• Örnekler: rakamlar toplamı basamak basamak, palindrom iki uçtan, Öklid algoritması kalanla küçülür. Hanoi kuleleri 2ⁿ − 1 hamle yapar ve özyinelemeyle birkaç satırdır.
• Ağaç özyinelemesi: birden çok çağrı (Fibonacci, Hanoi) ağaç oluşturur; tekrar varsa çağrı sayısı üstel büyür. Belleklemesiz fibonacci(40) 331.160.281 çağrı yapar.
• İlerlemeli çözüm: döngü ve biriktirici değişkenle tek çerçevede, sabit bellekle çalışır ve genellikle daha hızlıdır. Her özyinelemeli çözüm döngüyle yazılabilir.
• Kuyruk özyinelemesi: son iş çağrının kendisidir ve sonuç biriktirici parametrede taşınır. Biriktiricinin başlangıcı etkisiz elemandır ve bir sarmalayıcı metotla gizlenir. Java kuyruk çağrısı optimizasyonu yapmaz.
• Bellekleme: hesaplanan sonuçlar bir Map'te saklanıp yeniden kullanılır. Belleklemeli Fibonacci 2n − 1 çağrı yapar; bedeli bellektir.

3.5.11Kavram listesi

• özyineleme recursion
• taban durum base case
• özyinelemeli adım recursive step
• çağrı yığını call stack
• çerçeve stack frame
• yığın taşması stack overflow
• izleme listesi stack trace
• ağaç özyinelemesi tree recursion
• yineleme bağıntısı recurrence relation
• inanç sıçraması leap of faith
• ilerlemeli çözüm iterative solution
• kuyruk özyinelemesi tail recursion
• biriktirici accumulator
• kuyruk çağrısı optimizasyonu tail call optimization
• bellekleme memoization
• Öklid algoritması Euclidean algorithm
• palindrom palindrome

3.5.12Kendini Dene

1. Aşağıdaki metot için f(6) kaçtır? Metot kaç kez çağrılır (ilk çağrı dahil)? Metot ne hesaplar?

   static int f(int n) {
       if (n <= 0) return 0;
       return (n % 2 == 0 ? n : 0) + f(n - 1);
   }

   Cevap

   f(6) = 6 + 0 + 4 + 0 + 2 + 0 + 0 = 12. Argümanlar 6, 5, 4, 3, 2, 1, 0'dır; 7 çağrı yapılır. Metot 1'den n'ye kadar çift sayıların toplamını hesaplar. Taban durum n <= 0 olduğu için negatif girdide de durur.

2. g(3) ne yazdırır?

   static void g(int n) {
       if (n == 0) return;
       System.out.print(n);
       g(n - 1);
       System.out.print(n);
   }

   Cevap

   321123. İlk print inişte çalışır ve 3, 2, 1 yazar. İkinci print dönüşte çalışır; en derindeki çerçeve önce döndüğü için 1, 2, 3 yazılır.

3. Aşağıdaki üs metodu us(2, 10) için hangi değeri döndürür ve kaç çağrı yapar? Üssü bir azaltan taban * us(taban, us - 1) sürümü kaç çağrı yapardı?

   static long us(long t, int u) {
       if (u == 0) return 1;
       long y = us(t, u / 2);
       return u % 2 == 0 ? y * y : y * y * t;
   }

   Cevap

   1024 döner; üsler 10, 5, 2, 1, 0 olduğu için 5 çağrı yapılır. us(2, 5) = 32 (tek üs: 4 · 4 · 2), sonra 32 · 32 = 1024. Üssü bir azaltan sürüm 11 çağrı yapardı. Üssü yarıya indirmek çağrı sayısını O(u)'dan O(log u)'ya düşürür. Alt sonucun y'de tutulması önemlidir; us(t, u / 2) * us(t, u / 2) yazılsaydı kazanç kaybolurdu.

4. basamakSayisi metodu, biriktirici kullanan kuyruk özyinelemeli bir bs(int n, int k) metodu olarak nasıl yazılır? bs(48729, 0) kaç döndürmelidir?

   Cevap

   static int bs(int n, int k) {
       if (n < 10) return k + 1;
       return bs(n / 10, k + 1);
   }

   k, o ana kadar atılan basamakları sayar ve 0 ile başlar. (48729, 0) → (4872, 1) → (487, 2) → (48, 3) → (4, 4) → 4 + 1 = 5. Son iş çağrı olduğu için kuyruk özyinelemelidir.

5. static int h(int n) { if (n == 0) return 1; return h(n - 1) + h(n - 1); } için h(4) kaçtır ve kaç çağrı yapılır? Son satır return 2 * h(n - 1); yapılırsa çağrı sayısı ne olur?

   Cevap

   h(4) = 2⁴ = 16. Her çağrı iki çağrı açtığı için ağaçta 1 + 2 + 4 + 8 + 16 = 31 çağrı vardır. 2 * h(n - 1) ile aynı sonuç 5 çağrıda bulunur. Aynı alt problemi iki kez çağırmak, sonucu değiştirmeden maliyeti üstele çıkarır.

6. gcd(89, 55) kaç çağrı yapar ve sonucu nedir? En derin anda yığında main dahil kaç çerçeve vardır?

   Cevap

   EBOB 1'dir. Zincir (89, 55) → (55, 34) → (34, 21) → (21, 13) → (13, 8) → (8, 5) → (5, 3) → (3, 2) → (2, 1) → (1, 0)'dır; 10 çağrı yapılır. Hepsi aynı anda yığındadır, çünkü Java kuyruk çağrılarını optimize etmez: main ile 11 çerçeve. Ardışık Fibonacci sayıları, her adımda kalanın en yavaş küçüldüğü durumdur.

7. Aşağıdaki metot say("kelebek", 'e') için ne döndürür? Kaç çağrı yapılır? Taban durum hangisidir?

   static int say(String s, char c) {
       if (s.length() == 0) return 0;
       int k = s.charAt(0) == c ? 1 : 0;
       return k + say(s.substring(1), c);
   }

   Cevap

   3 döner: “kelebek”te üç 'e' vardır. Dizgi her çağrıda bir karakter kısalır; yedi harf için 7 çağrı ve boş dizgi için 1 çağrı, toplam 8 çağrı yapılır. Taban durum boş dizgidir ve 0 döndürür.

8. 5 diskli Hanoi kuleleri coz(5, 'A', 'C', 'B') ile çözülüyor. Kaç hamle yazdırılır ve ilk hamle nedir? En büyük disk kaçıncı hamlede taşınır?

   Cevap

   2⁵ − 1 = 31 hamle. Disk sayısı tek olduğu için ilk hamle 1: A->C'dir. En büyük disk, üstteki 4 diskin 2⁴ − 1 = 15 hamlede B'ye çekilmesinden sonra, 16. hamlede A'dan C'ye taşınır.

3.5.13İleri okuma

• A. B. Downey ve C. Mayfield, Think Java (2. baskı, 2019), Bölüm 8: özyinelemeli metotlar yığın diyagramlarıyla ve “inanç sıçraması” kavramıyla anlatılır. Kitap çevrimiçi ücretsiz okunabilir.
• R. Sedgewick ve K. Wayne, Computer Science: An Interdisciplinary Approach, Kesim 2.3: Öklid, Hanoi, Gray kodları ve özyinelemeli çizimlerle özyinelemenin gücü; üstel Fibonacci tuzağı ve dinamik programlama ile çaresi işlenir.
• P. Deitel ve H. Deitel, Java: How to Program, Bölüm 18: özyinelemeyi yineleme ile karşılaştırır ve fraktal çizimleri, sekiz vezir ve labirent gibi ek örnekler verir.
• H. Abelson ve G. J. Sussman, Structure and Interpretation of Computer Programs (2. baskı, MIT Press, 1996), Kesim 1.2: doğrusal ve ağaç özyinelemesi, ilerlemeli süreç ve kuyruk çağrısı kavramlarının klasik anlatımı.

3.5.14Kaynaklar

1. P. Deitel, H. Deitel, Java: How to Program (Early Objects), 11. baskı, Pearson, 2017 (Bölüm 18: Recursion).
2. A. B. Downey, C. Mayfield, Think Java, 2. baskı, O'Reilly, 2019 (Bölüm 8: Recursive Methods).
3. J. Gosling, B. Joy, G. Steele, G. Bracha, A. Buckley, D. Smith, G. Bierman, The Java Language Specification, Java SE 21 Edition, Oracle, 2023 (15.12: Method Invocation Expressions).
4. C. S. Horstmann, Core Java, Volume I: Fundamentals, 12. baskı, Pearson, 2022.
5. Oracle, The Java Tutorials: Defining Methods; Returning a Value from a Method, docs.oracle.com/javase/tutorial/java/javaOO/.
6. R. Sedgewick, K. Wayne, Computer Science: An Interdisciplinary Approach, Addison-Wesley, 2016 (2.3: Recursion).
7. H. Abelson, G. J. Sussman, J. Sussman, Structure and Interpretation of Computer Programs, 2. baskı, MIT Press, 1996.

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