Bölüm 12: Özyineleme

Özyineleme · Çalışma Soruları
Taban durum ve özyinelemeli durumFaktöriyelÜs alma (usHesapla)Rakam toplamı ve basamak sayısıÇağrı yığınıFibonacci ve özyineleme ağacıBellekleme ve kuyruk özyinelemesi
Sercan KÜLCÜ · Giresun Üniversitesi · Bilgisayar Mühendisliği

Ç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.

f(5)120f(4)24f(3)6f(2)2f(1)1

Ç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 return ettiği için "d1" yazılmaz.
  • Çerçeveler ters sırada kapanır: d2, d3. En son main sonucu (3·2·1 = 6) yazar.
en derin anf(1)→ 1f(2)→ 2f(3)→ 6main()

Ç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.
us(2,−2)0.25us(2,2)4.0us(2,1)2.0us(2,0)1.0

Ç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.

1684210

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.

9088 + 9 = 17900 + 9 = 999

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 < 10 bunu doğal olarak kapsar).
  • Negatif sayıda önce Math.abs: −470 → 470 → 3.
123456612345512344123312211

Çı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).
yazB: dönüşte yazyazB(0)yazB(4)yaz 4yazB(47)yaz 7yazB(472)yaz 2

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.

d041722

Dizi oluşturulur; tüm çağrılar aynı diziyi (referans) paylaşır.

a041722i = 0

0 == 3 → false. a[0] = 4 bekletilir, toplam(a, 1) çağrılır.

a041722i = 1

a[1] = 7 bekletilir, toplam(a, 2).

a041722i = 2

a[2] = 2 bekletilir, toplam(a, 3).

a041722

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
fib(4)3fib(3)2fib(2)1fib(1)fib(0)fib(1)fib(2)1fib(1)fib(0)kesikli = daha önce hesaplanmış alt problemin tekrarı

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?

fib(3)fib(2)fib(1)fib(0)fib(1)

main, fib(3)'ü çağırır.

fib(3)fib(2)fib(1)fib(0)fib(1)

3 <= 1 → false. Önce sol terim fib(2) hesaplanacak.

fib(3)fib(2)fib(1)fib(0)fib(1)

2 <= 1 → false. Önce fib(1).

fib(3)fib(2)fib(1)1fib(0)fib(1)

Taban durum: return 1.

fib(3)fib(2)fib(1)1fib(0)fib(1)

Sol terim 1 hazır; şimdi sağ terim fib(0).

fib(3)fib(2)fib(1)1fib(0)0fib(1)

Taban durum: return 0.

fib(3)fib(2)1fib(1)1fib(0)0fib(1)

fib(2) = 1 + 0 = 1 döner; çerçevesi kapandı.

fib(3)fib(2)1fib(1)1fib(0)0fib(1)1

fib(3) şimdi sağ terim fib(1)'i çağırır → taban durum, 1.

fib(3)2fib(2)1fib(1)1fib(0)0fib(1)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.
ikili(13)"1101"ikili(6)"110"ikili(3)"11"ikili(1)"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
h(2,A,C,B)2: A→Ch(1,A,B,C)1: A→Bh(1,B,C,A)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.

Son

Özyineleme: Çalışma Soruları
Konu anlatımı: Özyineleme sunumu
1 / 1 Sercan KÜLCÜ, Tüm hakları saklıdır.