Bölüm 12: Özyineleme
Çoktan Seçmeli · Temeller
Soru 1: Hangisi Sonlanmaz?
Aşağıdaki gövdelerden hangisiyle f(5) çağrısı sonlanmaz?
B: B'de n: 5, 3, 1, −1, −3, … diye iner; tek sayılardan hiçbiri 0'a eşit olmaz, taban durum atlanır → StackOverflowError. Taban durumu n <= 0 yazmak bunu önler.
Çoktan Seçmeli · Faktöriyel
Soru 2: while Sürümünün Özyinelemeli Karşılığı
While ile faktöriyel metodu yanda. Aşağıdaki özyinelemeli f(int n) gövdelerinden hangisi n ≥ 0 için aynı sonucu verir?
static long faktoriyelHesapla(int n) { long sonuc = 1; int i = 1; while (i <= n) { sonuc *= i; i++; } return sonuc; }
D: 0! = 1! = 1 taban durumdur, n her çağrıda 1 azalır. A'da taban durum yok (StackOverflowError), B'de n küçülmüyor (n ≥ 2 için StackOverflowError). C taban durumda 0 döndürdüğü için her sonuç 0 olur.
Adım Adım Çalıştırma · Faktöriyel
Soru 3: faktoriyel(5) Çağrı Yığını
Özyinelemeli faktöriyelde çağrılar yığında nasıl açılır ve kapanır? Çağrı yığınını izleyin.
main, faktoriyel(5)'i çağırır ve sonucu bekler.
5 <= 1 → false. 5 * faktoriyel(4): çarpma için önce alt sonuç gerekir → bu çerçeve bekler.
Yeni çerçeve, kendi n'si (4) ile. 4 * faktoriyel(3) bekler.
3 * faktoriyel(2) bekler.
2 * faktoriyel(1) bekler.
1 <= 1 → true: taban durum, return 1. Yığın en derin hâlinde: 6 çerçeve.
Son açılan ilk kapanır: 2 * 1 = 2 döner.
3 * 2 = 6.
4 * 6 = 24.
5 * 24 = 120.
Çarpmaların hepsi dönüş yolunda yapıldı.
static long faktoriyel(int n) { if (n <= 1) return 1; return n * faktoriyel(n - 1); } // main içinde: System.out.println(faktoriyel(5));
Çıktı Sorusu · Faktöriyel
Soru 4: Çağrı ve Dönüş Sırası
Metot hem çağrı anında hem dönüşte yazdırıyor. Çıktı nedir?
static int f(int n) { System.out.print("g" + n + " "); if (n <= 1) return 1; int r = n * f(n - 1); System.out.print("d" + n + " "); return r; } // main içinde: System.out.println(f(3));
Cevabı göster
Çıktı: g3 g2 g1 d2 d3 6
- Çağrılar açılırken "g" satırları sırayla yazılır: 3, 2, 1.
- f(1) taban durumda
returnettiği için "d1" yazılmaz. - Çerçeveler ters sırada kapanır: d2, d3. En son main sonucu (3·2·1 = 6) yazar.
Çoktan Seçmeli · Üs Alma
Soru 5: Negatif Üs Kontrolü Yoksa
Dersteki özyinelemeli us metodunda us(2, -1) çağrılırsa ne olur?
static long us(long taban, int n) { if (n == 0) return 1; return taban * us(taban, n - 1); }
C: n: −1, −2, −3, … diye iner; n == 0 taban durumuna hiç ulaşılmaz, çerçeveler birikir. Önlem: n < 0 için hata fırlatmak ya da dönüş tipini double yapıp 1.0 / us(taban, -n) ile pozitif üsse çevirmek.
Çıktı Sorusu · Üs Alma
Soru 6: Tamamen Özyinelemeli Üs
Bu fikir tamamen özyinelemeli bir metoda taşındı. Çıktı nedir?
static double us(double t, int n) { if (n < 0) return 1.0 / us(t, -n); if (n == 0) return 1; return t * us(t, n - 1); } // main içinde: System.out.println(us(2, -2) + " " + us(3, 3));
Cevabı göster
Çıktı: 0.25 27.0
- us(2, −2) → 1.0 / us(2, 2); us(2, 2) = 2 · 2 · 1 = 4.0 → 0.25.
- us(3, 3) = 3 · 3 · 3 · 1 = 27.0 (n + 1 = 4 çağrı).
- Negatif dal yalnızca ilk çağrıda çalışır; sonraki çağrılarda n ≥ 0'dır.
Çoktan Seçmeli · Üs Alma
Soru 7: Hızlı Üs Çağrı Sayısı
Dersteki hizliUs ile hizliUs(3, 16) toplam kaç çağrı yapar (ilk çağrı dahil)?
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; }
D: Üs her çağrıda yarıya iner: 16 → 8 → 4 → 2 → 1 → 0, yani 6 çağrı (log₂16 + 2). Düz us metodu 17 çağrı yapardı. Sonuç 3¹⁶ = 43.046.721.
Adım Adım Çalıştırma · Rakam ve Basamak
Soru 8: rakamToplami(908)
Rakamlar toplamını özyinelemeli bulan metodu çağrı yığınıyla izleyin. Çıktı nedir?
main, rakamToplami(908)'i çağırır.
908 < 10 → false. Son rakam 908 % 10 = 8 bekletilir; 908 / 10 = 90 ile yeni çağrı.
90 < 10 → false. 90 % 10 = 0 bekletilir; 9 ile çağrı.
9 < 10 → true: tek basamak, return 9 (taban durum).
0 + 9 = 9 döner.
8 + 9 = 17 döner.
9 + 0 + 8 = 17. Derinlik = basamak sayısı (3).
static int rakamToplami(int n) { if (n < 10) return n; return n % 10 + rakamToplami(n / 10); } // main içinde: System.out.println(rakamToplami(908));
Çıktı Sorusu · Rakam ve Basamak
Soru 9: Özyinelemeli Basamak Sayısı
Döngüyle yazılan basamak sayısı metodu özyinelemeli yazıldı. Çıktı nedir?
static int basamak(int n) { n = Math.abs(n); if (n < 10) return 1; return 1 + basamak(n / 10); } // main içinde: System.out.println(basamak(123456)); System.out.println(basamak(0) + " " + basamak(-470));
Cevabı göster
Çıktı:
6 1 3
- Her çağrı son basamağı atar (n / 10) ve 1 ekler; tek basamağa inince 1 döner.
- 0 tek basamaklıdır → 1 (taban durum
n < 10bunu doğal olarak kapsar). - Negatif sayıda önce
Math.abs: −470 → 470 → 3.
Çıktı Sorusu · Rakam ve Basamak
Soru 10: Yazdırma Çağrıdan Önce mi Sonra mı?
İki metot yalnızca yazdırma ile özyinelemeli çağrının sırasında farklı. Çıktı nedir?
static void yazA(int n) { if (n == 0) return; System.out.print(n % 10); yazA(n / 10); } static void yazB(int n) { if (n == 0) return; yazB(n / 10); System.out.print(n % 10); } // main içinde: yazA(472); System.out.print(" "); yazB(472);
Cevabı göster
Çıktı: 274 472
- yazA önce yazar, sonra çağırır: çağrılar açılırken son rakamlar yazılır → 2, 7, 4 (ters sıra).
- yazB önce çağırır, yazmayı dönüşe bırakır: en derin çağrı (n = 4) ilk yazar → 4, 7, 2 (özgün sıra).
Adım Adım Çalıştırma · Toplam
Soru 11: Dizinin Özyinelemeli Toplamı
toplam(a, i) = a[i] + toplam(a, i + 1) tanımıyla dizinin toplamı bulunuyor. Çağrı yığınını izleyin.
Dizi oluşturulur; tüm çağrılar aynı diziyi (referans) paylaşır.
0 == 3 → false. a[0] = 4 bekletilir, toplam(a, 1) çağrılır.
a[1] = 7 bekletilir, toplam(a, 2).
a[2] = 2 bekletilir, toplam(a, 3).
3 == a.length → taban durum: return 0 (dizinin sonu).
2 + 0 = 2 döner.
7 + 2 = 9 döner.
4 + 9 = 13 döner.
n öğeli dizide n + 1 çağrı; yığın derinliği O(n).
static int toplam(int[] a, int i) { if (i == a.length) return 0; return a[i] + toplam(a, i + 1); } // main içinde: int[] d = {4, 7, 2}; System.out.println(toplam(d, 0));
Klasik Soru · Fibonacci
Soru 12: fib(4) Özyineleme Ağacı
Düz özyinelemeli fib metodu (if (n <= 1) return n; return fib(n - 1) + fib(n - 2);) için fib(4) özyineleme ağacını çizin. Toplam kaç çağrı yapılır; fib(2), fib(1) ve fib(0) kaçar kez çağrılır?
Cevabı göster
9 çağrı: fib(4) 1, fib(3) 1, fib(2) 2, fib(1) 3, fib(0) 2 kez. Sonuç fib(4) = 3.
fib(n − 1) ve fib(n − 2) alt ağaçları örtüşür; çağrı sayısı n ile yaklaşık üstel büyür (fib(5): 15, fib(30): 2.692.537 çağrı).
Adım Adım Çalıştırma · Fibonacci
Soru 13: fib(3) Adım Adım
fib(3) çağrısında yığını ve ağaçta hangi çağrının çalıştığını izleyin. Çıktı nedir?
main, fib(3)'ü çağırır.
3 <= 1 → false. Önce sol terim fib(2) hesaplanacak.
2 <= 1 → false. Önce fib(1).
Taban durum: return 1.
Sol terim 1 hazır; şimdi sağ terim fib(0).
Taban durum: return 0.
fib(2) = 1 + 0 = 1 döner; çerçevesi kapandı.
fib(3) şimdi sağ terim fib(1)'i çağırır → taban durum, 1.
fib(3) = 1 + 1 = 2.
5 çağrı yapıldı; yığın en fazla 4 çerçeve (main dahil) derinleşti.
static int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } // main içinde: System.out.println(fib(3));
Çoktan Seçmeli · Fibonacci
Soru 14: fib(5) Çağrı Sayısı
Düz özyinelemeli fib ile fib(5) hesaplanırken metot toplam kaç kez çağrılır (ilk çağrı dahil)?
D: Çağrı sayısı ç(n) = 1 + ç(n − 1) + ç(n − 2), ç(0) = ç(1) = 1: ç(2) = 3, ç(3) = 5, ç(4) = 9, ç(5) = 15. Sonuç fib(5) = 5 olsa da 15 çağrı yapılır.
Çoktan Seçmeli · İyileştirme
Soru 15: Bellekleme ile Çağrı Sayısı
Belleklemeli fib(6) (bellek başlangıçta boş) toplam kaç çağrı yapar? (Düz sürüm 25 çağrı yapar.)
static long[] bellek = new long[50]; static long fib(int n) { if (n <= 1) return n; if (bellek[n] != 0) return bellek[n]; bellek[n] = fib(n - 1) + fib(n - 2); return bellek[n]; }
B: Her fib(k) (k ≥ 2) bir kez hesaplanır ve iki çağrı yapar; sağdaki fib(k − 2) çağrısı bellekte hazır bulunur ve hemen döner. Sayım: 1 + 2 × 5 = 11. Sonuç fib(6) = 8; karşılığında O(n) bellek kullanılır.
Çoktan Seçmeli · Çağrı Yığını
Soru 16: En Derin An
faktoriyel(4) çağrıldığında çağrı yığını en derin anında main dahil kaç çerçeve içerir?
A: main, f(4), f(3), f(2), f(1): taban duruma ulaşıldığında hiçbir çağrı dönmemiştir, hepsi yığındadır. Döngülü sürüm ise yalnızca 2 çerçeve (main + metot) kullanır.
Çoktan Seçmeli · İyileştirme
Soru 17: Kuyruk Özyinelemesi Zinciri
fakt(4, 1) çağrısının zinciri hangisidir?
static long fakt(int n, long birikim) { if (n <= 1) return birikim; return fakt(n - 1, n * birikim); }
C: Çarpma çağrıdan önce yapılır: 4·1 = 4, 3·4 = 12, 2·12 = 24. Taban durumda birikim olduğu gibi döner; dönüş yolunda iş kalmaz.
Çıktı Sorusu · Diğer Örnekler
Soru 18: Onluktan İkiliye
Aşağıdaki kodun çıktısı nedir?
static String ikili(int n) { if (n < 2) return "" + n; return ikili(n / 2) + (n % 2); } // main içinde: System.out.println(ikili(13) + " " + ikili(6) + " " + ikili(1));
Cevabı göster
Çıktı: 1101 110 1
- Kalan (n % 2) özyinelemeli çağrının sağına eklenir; bu yüzden en son bulunan kalan (en anlamlı bit) en solda olur.
- 13 → 6 kalan 1 → 3 kalan 0 → 1 kalan 1 → taban durum "1": "1" + 1 + 0 + 1.
Çıktı Sorusu · Diğer Örnekler
Soru 19: Hanoi: 2 Disk
Dersteki Hanoi metodu iki diskle çalıştırılıyor. Çıktı nedir?
static void hanoi(int n, char kaynak, char hedef, char ara) { if (n == 0) return; hanoi(n - 1, kaynak, ara, hedef); System.out.println(n + ": " + kaynak + " -> " + hedef); hanoi(n - 1, ara, hedef, kaynak); } // main içinde: hanoi(2, 'A', 'C', 'B');
Cevabı göster
1: A -> B 2: A -> C 1: B -> C
- Önce üstteki disk yardımcıya (A → B), sonra büyük disk hedefe (A → C), en son küçük disk hedefe (B → C).
- Yazdırma iki özyinelemeli çağrının arasındadır (ağacın ortadan gezilmesi).
Çoktan Seçmeli · Diğer Örnekler
Soru 20: Hanoi Hamle Sayısı
Hanoi kulelerinde 5 disk için en az kaç hamle gerekir?
C: h(n) = 2·h(n − 1) + 1, h(0) = 0 → 1, 3, 7, 15, 31. Genel olarak 2ⁿ − 1: 2⁵ − 1 = 31. Hamle sayısı üstel büyür.