Bölüm 4: Özyineleme
Çoktan Seçmeli · Özyineleme Nedir
Soru 1: Sonlanma Koşulu
Özyinelemeli bir metodun her girdi için sonlanmasını aşağıdakilerden hangisi sağlar?
B: Taban durum özyinelemeyi durdurur; özyinelemeli adım girdiyi her çağrıda taban duruma yaklaştırmalıdır (n − 1, n / 2 …). Çağrı sayısı ya da dönüş tipi sonlanmayı belirlemez; parametre büyüyorsa taban duruma hiç ulaşılmaz.
Klasik Soru · Özyineleme Nedir
Soru 2: Önce ve Sonra Yazdırma
f(3) çağrısının çıktısı nedir? Çağrıdan önceki ve sonraki yazdırmaların sırasını açıklayınız.
void f(int n) { if (n == 0) return; System.out.print(n + " "); f(n - 1); System.out.print(n + " "); }
Cevabı göster
Çıktı: 3 2 1 1 2 3
- Satır 3 çağrıdan önce çalışır: çağrılar inerken 3, 2, 1 yazılır.
- f(0) taban durumdur, hiçbir şey yazmaz.
- Satır 5 çağrıdan sonra çalışır: çerçeveler yığından ters sırayla çıkarken f(1), f(2), f(3) sırasıyla 1, 2, 3 yazar.
Adım Adım Çalıştırma · Çağrı Yığını
Soru 3: Dönüşte Yazdırma
yaz(6) çağrısı ekrana ne yazar ve çağrı yığınında (main dahil) en fazla kaç çerçeve bulunur?
main, yaz(6)'yı çağırır.
n = 6 ≠ 0 → satır 3'te yaz(3) çağrılır; yazdırma bekler.
Yeni çerçeve n = 3 → yaz(1) çağrılır.
n = 1 → 1 / 2 = 0: yaz(0) çağrılır.
Taban durum: hiçbir şey yazmadan döner. Yığın en derinde: 5 çerçeve.
yaz(1) kaldığı yerden sürer: 1 % 2 = 1 yazılır.
yaz(3): 3 % 2 = 1 yazılır.
yaz(6): 6 % 2 = 0 yazılır.
Çıktı 110 (6'nın ikili gösterimi); en fazla 5 çerçeve. n her çağrıda yarıya iner → O(log n).
void yaz(int n) { if (n == 0) return; yaz(n / 2); System.out.print(n % 2); } // main: yaz(6);
Çoktan Seçmeli · Çağrı Yığını
Soru 4: Ulaşılamayan Taban Durum
f(5) ve f(6) çağrılarının sonucu nedir?
int f(int n) { if (n == 1) return 1; return n * f(n - 2); }
B: f(5) = 5 · f(3) = 5 · 3 · f(1) = 15. f(6) ise 6, 4, 2, 0, −2 … diye ilerler; n hiçbir zaman 1 olmaz, çağrı yığını dolar. Taban durum n <= 1 olsaydı f(6) = 6 · 4 · 2 · 1 = 48 olurdu.
Klasik Soru · Çağrı Yığını
Soru 5: Yığın Derinliği
h(20) kaç döndürür? Kaç çağrı yapılır ve çağrı yığınında (main dahil) en çok kaç çerçeve bulunur?
int h(int n) { if (n <= 1) return 0; return 1 + h(n / 2); }
Cevabı göster
Çağrılar: h(20) → h(10) → h(5) → h(2) → h(1). h(1) taban durumdur ve 0 döndürür.
Dönüşte her çerçeve 1 ekler: h(2) = 1, h(5) = 2, h(10) = 3, h(20) = 4 (⌊log₂ 20⌋).
5 çağrı; en derinde 5 çerçeve + main = 6. n her çağrıda yarıya indiği için zaman ve bellek O(log n).
Klasik Soru · Doğrusal Özyineleme
Soru 6: Eksik Satır: En Büyük Öğe
Metot dizinin ilk n öğesinin en büyüğünü döndürmelidir. Boşluğa ne yazılmalıdır? a = {4, 9, 2, 7} için enBuyuk(a, 4) kaç çağrı yapar?
int enBuyuk(int[] a, int n) { if (n == 1) return a[0]; int m = enBuyuk(a, n - 1); return ______; }
Cevabı göster
Boşluk: Math.max(m, a[n - 1])
m, ilk n − 1 öğenin en büyüğüdür; geriye yalnızca son öğe a[n − 1] ile karşılaştırmak kalır.
Çağrılar n = 4, 3, 2, 1: 4 çağrı. Dönüşte: 4 → max(4, 9) = 9 → max(9, 2) = 9 → max(9, 7) = 9. T(n) = T(n − 1) + c → O(n).
Çoktan Seçmeli · Doğrusal Özyineleme
Soru 7: Hızlı Üs Alma
hizliUs(2, 13) toplam kaç kez çağrılır (ilk çağrı dahil)?
long hizliUs(long x, int n) { if (n == 0) return 1; long y = hizliUs(x, n / 2); if (n % 2 == 0) return y * y; return x * y * y; }
B: n değerleri 13, 6, 3, 1, 0 → 5 çağrı (⌊log₂ 13⌋ + 2). Sonuç 2¹³ = 8192. Yavaş us(2, 13) ise 14 çağrı yapar.
Adım Adım Çalıştırma · Doğrusal Özyineleme
Soru 8: Palindrom İzleme
Program ne yazar ve kaç çağrı yapılır?
main, palindrom("kayık", 0, 4)'ü çağırır.
i = 0 < j = 4. s[0] = k, s[4] = k: eşit → satır 5'te iç parça için çağrı.
s[1] = a, s[3] = ı: farklı → taban durum, false döner.
palindrom(0, 4) aldığı false'u olduğu gibi iletir (kuyruk çağrısı).
Çıktı false; yalnızca 2 çağrı yapıldı. İlk uyuşmazlıkta özyineleme durur; en kötü durumda ⌊n/2⌋ + 1 çağrı, O(n).
boolean palindrom(String s, int i, int j) { if (i >= j) return true; if (s.charAt(i) != s.charAt(j)) return false; return palindrom(s, i + 1, j - 1); } // main: boolean p = palindrom("kayık", 0, 4); System.out.println(p);
Çoktan Seçmeli · İkili Özyineleme
Soru 9: fib(5) Çağrı Sayısı
Özyinelemeli fib(n) (n <= 1 ise n döner, değilse fib(n − 1) + fib(n − 2)) için fib(5) toplam kaç çağrı yapar?
C: Çağrı sayısı C(n) = C(n − 1) + C(n − 2) + 1, C(0) = C(1) = 1: C(2) = 3, C(3) = 5, C(4) = 9, C(5) = 15 (= 2 · F(6) − 1). 9, fib(4)'ün; 25, fib(6)'nın çağrı sayısıdır.
Klasik Soru · İkili Özyineleme
Soru 10: Tekrarlanan Alt Problemler
fib(5) çağrı ağacında fib(3), fib(2), fib(1) ve fib(0) kaçar kez çağrılır? Yığında aynı anda en çok kaç fib çerçevesi bulunur?
Cevabı göster
| fib(5) | fib(4) | fib(3) | fib(2) | fib(1) | fib(0) | toplam |
|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 3 | 5 | 3 | 15 |
fib(3) iki kez, fib(2) üç kez hesaplanır: aynı alt problem tekrar tekrar çözülür.
En derin zincir fib(5) → fib(4) → fib(3) → fib(2) → fib(1): 5 çerçeve. Zaman üstel, bellek O(n).
Değerler bir dizide saklanırsa her fib(k) bir kez hesaplanır → O(n).
Çoktan Seçmeli · İkili Özyineleme
Soru 11: Bulunamayan Öğe
a = {3, 8, 15, 21, 30, 42, 57} için özyinelemeli ikiliAra(a, 20, 0, 6) kaç çağrı yapar ve ne döndürür?
B: (0, 6) mid = 3, 20 < 21 → (0, 2) mid = 1, 20 > 8 → (2, 2) mid = 2, 20 > 15 → (3, 2) lo > hi: aralık boş, −1. Son çağrı da sayılır: 4 çağrı. 3 döndürmek, 20'nin eklenebileceği yerdir ama metot −1 döndürür.
Klasik Soru · Hanoi ve Geri İzleme
Soru 12: Hanoi Hamleleri
hanoi(4, 'A', 'B', 'C') çağrısı toplam kaç satır yazdırır ve yazdırılan 8. satır nedir? Gerekçesini özyinelemeli yapıdan çıkarın.
void hanoi(int n, char k, char y, char h) { if (n == 1) { System.out.println("1: " + k + "→" + h); return; } hanoi(n - 1, k, h, y); System.out.println(n + ": " + k + "→" + h); hanoi(n - 1, y, k, h); }
Cevabı göster
T(n) = 2T(n−1) + 1, T(1) = 1 → T(n) = 2ⁿ − 1. T(4) = 15 satır.
Çağrı önce hanoi(3, A, C, B) ile üstteki 3 diski B'ye taşır: T(3) = 7 satır. Ardından en büyük disk taşınır; dolayısıyla 8. satır 4: A→C olur. Son 7 satır hanoi(3, B, A, C)'den gelir.
(n çift olduğu için ilk hamle 1: A→B'dir.) Zaman O(2ⁿ); çağrı yığınının derinliği en çok n (+ main) → bellek O(n).
Çoktan Seçmeli · Hanoi ve Geri İzleme
Soru 13: Hanoi: 5. Satır
hanoi(3, 'A', 'B', 'C') (n == 1 ise "1: k→h" yazar; değilse hanoi(n − 1, k, h, y), "n: k→h", hanoi(n − 1, y, k, h)) çıktısının 5. satırı nedir?
C: İlk 3 satır hanoi(2, A, C, B)'den gelir (1: A→C, 2: A→B, 1: C→B); 4. satır en büyük disk: 3: A→C. Kalan satırlar hanoi(2, B, A, C)'den gelir ve ilki hanoi(1, B, C, A): 1: B→A.
Klasik Soru · Hanoi ve Geri İzleme
Soru 14: Dalların Sırası
Alt küme üretirken her öğe için iki seçim vardır: al (a[i] alt kümeye eklenir) ve alma (a[i] eklenmez). Sunumdaki altKumeler önce “al” dalını dener. Aşağıdaki alt ise önce “alma” dalını dener. alt(new int[]{1, 2, 3}, 0, new ArrayList<>()) ne yazar? Sıra değişince çıktı nasıl değişir?
void alt(int[] a, int i, List<Integer> s) { if (i == a.length) { System.out.print(s + " "); return; } alt(a, i + 1, s); // 1) alma: a[i]'siz s.add(a[i]); alt(a, i + 1, s); // 2) al: a[i] ile s.remove(s.size() - 1); }
Cevabı göster
Çıktı: [] [3] [2] [2, 3] [1] [1, 3] [1, 2] [1, 2, 3]
Her düğümde önce “alma” dalına inilir. Sunumdaki altKumeler ise önce “al” dalına iner ve [1, 2, 3] [1, 2] [1, 3] [1] [2, 3] [2] [3] [] yazar; yani çıktı tam ters sıraya döner. Alt kümeler aynıdır: yine 8 alt küme ve 15 çağrı vardır.
Geri alma (s.remove) ikinci çağrıdan sonradır: s, metodun başındaki hâline döner.
Çoktan Seçmeli · Hanoi ve Geri İzleme
Soru 15: Geri Almayı Unutmak
Alt küme metodunda s.remove(s.size() - 1); satırı silinirse {1, 2} için çıktı ne olur?
void altKumeler(int[] a, int i, List<Integer> s) { if (i == a.length) { System.out.print(s + " "); return; } s.add(a[i]); altKumeler(a, i + 1, s); // s.remove(...) satırı silindi altKumeler(a, i + 1, s); }
B: Hiçbir seçim geri alınmaz. Sol dal [1, 2]'yi yazar; sağ dal da aynı listeyi görür: [1, 2]. Kök sağ dala geçerken s hâlâ [1, 2]'dir; 2 yeniden eklenir: [1, 2, 2] iki kez yazılır. Doğru çıktı A'dır.
Klasik Soru · Hanoi ve Geri İzleme
Soru 16: Permütasyon Sayısı
Aşağıdaki perm metodu her düzeyde henüz kullanılmamış harflerden birini soldan sağa sırayla seçer. perm("ABCD".toCharArray(), new boolean[4], new StringBuilder()) çağrılırsa kaç permütasyon yazılır, kaç çağrı yapılır ve ilk üç çıktı nedir?
void perm(char[] h, boolean[] kul, StringBuilder s) { if (s.length() == h.length) { // taban System.out.print(s + " "); return; } for (int k = 0; k < h.length; k++) { if (kul[k]) continue; // kullanıldı kul[k] = true; s.append(h[k]); // seç perm(h, kul, s); kul[k] = false; // geri al s.deleteCharAt(s.length() - 1); } }
Cevabı göster
4! = 24 permütasyon.
Çağrı ağacının düzeyleri: 1 (boş) + 4 + 4 · 3 + 4 · 3 · 2 + 4 · 3 · 2 · 1 = 1 + 4 + 12 + 24 + 24 = 65 çağrı.
İlk çıktılar: ABCD ABDC ACBD. Yığın derinliği n + 1 = 5 çerçeve; zaman O(n · n!).
Çoktan Seçmeli · Yineleme Bağıntıları
Soru 17: Bağıntıyı Tanımak
Metodun yineleme bağıntısı ve çözümü hangisidir?
void yaz(int n) { if (n == 0) return; yaz(n - 1); yaz(n - 1); System.out.print(n); }
B: Her çağrı n − 1 boyutlu iki çağrı yapar; düzey k'de 2ᵏ çağrı vardır, toplam 2ⁿ⁺¹ − 1 çağrı. yaz(3) 15 çağrı yapar ve 1121123 yazar.
Klasik Soru · Yineleme Bağıntıları
Soru 18: Çağrı Ağacıyla Çözmek
say(8) kaç döndürür ve toplam kaç çağrı yapar? Yığında aynı anda en çok kaç say çerçevesi bulunur? Çağrı ağacını düzey düzey çiziniz.
int say(int n) { if (n <= 1) return 1; return say(n / 2) + say(n / 2); }
Cevabı göster
| Düzey | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| n | 8 | 4 | 2 | 1 |
| çağrı | 1 | 2 | 4 | 8 |
Toplam 1 + 2 + 4 + 8 = 15 çağrı (2n − 1). 8 yaprağın her biri 1 döndürür: say(8) = 8.
En derin zincir 8 → 4 → 2 → 1: 4 çerçeve (log₂ n + 1). T(n) = 2T(n/2) + c → O(n) zaman, O(log n) bellek.
Çoktan Seçmeli · Kuyruk Özyinelemesi
Soru 19: Hangisi Kuyruk Özyinelemeli?
Aşağıdaki özyinelemeli adımlardan hangisi kuyruk özyinelemelidir?
C: Çağrı metodun son işidir; toplama çağrıdan önce yapılır ve dönen değer olduğu gibi iletilir. A ve B'de çağrı dönünce çarpma/toplama, D'de yazdırma yapılır.
Klasik Soru · Kuyruk Özyinelemesi
Soru 20: Döngüye Çevirme
toplaK(4, 0) hangi çağrı zinciriyle hangi değeri döndürür? Metodun döngülü karşılığını yazınız. Java'da hangisi daha az bellek kullanır?
int toplaK(int n, int acc) { if (n == 0) return acc; return toplaK(n - 1, acc + n); }
Cevabı göster
(4, 0) → (3, 4) → (2, 7) → (1, 9) → (0, 10): taban durumda acc = 10 döner ve değişmeden iletilir; 5 çağrı.
int toplaD(int n) { int acc = 0; while (n != 0) { acc = acc + n; n = n - 1; } return acc; }
Java kuyruk çağrısını eniyilemez: özyinelemeli sürüm O(n) yığın kullanır, döngü O(1).
Çoktan Seçmeli · Bağlı Listede Özyineleme
Soru 21: Liste Üzerinde Özyineleme
Liste 5 → 8 → 2 → 3 → null ise f(bas) ne yazar?
void f(Dugum d) { if (d == null) return; if (d.veri % 2 == 0) System.out.print(d.veri + " "); f(d.sonraki); if (d.veri % 2 == 1) System.out.print(d.veri + " "); }
A: Çift değerler çağrıdan önce, liste sırasıyla yazılır: 8 2. Tek değerler çağrıdan sonra, yani yığın çözülürken sondan başa yazılır: 3 5.
Ucu Açık Soru · Bağlı Listede Özyineleme
Soru 22: Uzun Listenin Toplamı
Bir sensör, ölçümleri tek yönlü bir bağlı listeye ekliyor; listede bir milyon düğüm olabiliyor. Ölçümlerin toplamı için return d.veri + topla(d.sonraki); biçiminde özyinelemeli bir metot mu, yoksa döngü mü kullanılmalı? Gerekçelendiriniz.
Örnek cevap
Özyinelemeli sürüm kısa ve tanıma yakındır, ama her düğüm için bir çerçeve açar: derinlik n = 10⁶. Varsayılan Java yığını bu kadar çerçeveyi taşıyamaz → StackOverflowError.
Metot kuyruk özyinelemeli yazılsa bile (biriktirici parametreyle) Java kuyruk çağrısını eniyilemez; sorun sürer.
Döngü (for (Dugum d = bas; d != null; d = d.sonraki) t += d.veri;) O(n) zaman ve O(1) bellekle çalışır. Toplam taşabileceği için long kullanılmalıdır.