Özyineleme (recursion)

Özyineleme (recursion), bir metodun kendini daha küçük bir girdiyle çağırmasıdır. İlk başta büyü gibi görünür ama arkasındaki mantık basit: problemi bir parça + aynı problemin küçük hali olarak yaz, en küçük hali doğrudan çöz. Bağlı liste zaten özyinelemeli bir yapıdır (bir düğüm + geri kalan liste), o yüzden liste metotları özyinelemeyle çok kısa yazılır. Sınav soruları: kodun ne bastığı, kaç çağrı yapıldığı ve kısa bir özyinelemeli metot yazmak. Bir sonraki hafta bu metotların karmaşıklığını hesaplayacağız.

Altın kurallar:

1. Taban durum (base case) olmadan özyineleme yazma. Önce onu yaz.
2. Her çağrı tabana yaklaşmalı. n − 1, n / 2, p.next.
3. Sonuca güven. size(p.next) doğru çalışıyor kabul et, sadece kendi adımını ekle.
4. Print’in yeri sırayı belirler. Çağrıdan önce mi sonra mı?

Taban durum ve özyinelemeli adım

static int factorial(int n) {
    if (n <= 1) return 1;          // taban durum: doğrudan cevap
    return n * factorial(n - 1);   // özyinelemeli adım: küçült ve çağır
}

Matematikteki tanımın aynısı: $n! = n \cdot (n-1)!$ ve $1! = 1$. factorial(5) 120, factorial(0) 1 döner.

Çağrı yığını (call stack)

Her metot çağrısı, kendi parametrelerini ve yerel değişkenlerini tutan bir yığın çerçevesi (stack frame) açar. Çağrı bitince çerçeve pop edilir ve dönüş değeri çağırana iletilir. 5. haftadaki yığının ta kendisi.

factorial(4) izinin program çıktısı (girinti = derinlik):

factorial(4) called
  factorial(3) called
    factorial(2) called
      factorial(1) called
      factorial(1) returns 1
    factorial(2) returns 2
  factorial(3) returns 6
factorial(4) returns 24

İniş sırasında hiçbir çarpma yapılmaz; hepsi bekler. Taban duruma ulaşınca dönüş başlar ve çarpmalar içten dışa yapılır: 1, 2 · 1, 3 · 2, 4 · 6.

çağrı yığını, en derin anda (tepe üstte):
| factorial(1) |
| factorial(2) |  2 * ? bekliyor
| factorial(3) |  3 * ? bekliyor
| factorial(4) |  4 * ? bekliyor
| main         |

Taban durumu olmayan ya da tabana yaklaşmayan özyineleme bu yığını doldurur ve StackOverflowError alırsın. Varsayılan JVM ayarlarında bu birkaç bin ile birkaç on bin çağrı derinliğinde olur.

Print nerede?

static void down(int n) { if (n == 0) return; System.out.print(n + " "); down(n - 1); }
static void up(int n)   { if (n == 0) return; up(n - 1); System.out.print(n + " "); }

3 2 1 
1 2 3 

down inerken basar, up dönerken basar. Çıktı sorusunda ilk sorman gereken: print özyinelemeli çağrıdan önce mi, sonra mı?

Birden fazla çağrı: ağaç özyinelemesi

Bir metot kendini iki kez çağırırsa çağrılar bir ağaç oluşturur ve sayıları hızla büyür.

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

fib(5)=5 calls=15
fib(10)=55 calls=177
fib(20)=6765 calls=21891
fib(25)=75025 calls=242785

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1)
│   │   │   └── fib(0)
│   │   └── fib(1)
│   └── fib(2)
│       ├── fib(1)
│       └── fib(0)
└── fib(3)
    ├── fib(2)
    │   ├── fib(1)
    │   └── fib(0)
    └── fib(1)

fib(3) iki kez, fib(2) üç kez hesaplanıyor. Bu yüzden naif Fibonacci üsteldir; döngüyle ya da hesaplananları saklayarak (memoization) O(n) yapılır.

İki çağrının arasında print olursa ilginç bir desen çıkar:

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

1 2 1 3 1 2 1 

Hız farkı: n − 1 mi, n / 2 mi?

static long pow(long b, int n) {       // n+1 çağrı
    if (n == 0) return 1;
    return b * pow(b, n - 1);
}

static long fastPow(long b, int n) {   // ~log n çağrı
    if (n == 0) return 1;
    long half = fastPow(b, n / 2);
    return (n % 2 == 0) ? half * half : half * half * b;
}

1024 calls=11
1024 calls=5

$b^{10} = (b^5)^2$, $b^5 = (b^2)^2 \cdot b$. Girdiyi yarıya indirmek, logaritmik derinlik demektir. 11. haftada bunu formülle göstereceğiz.

Bağlı listede özyineleme

Liste = boş (null) ya da bir düğüm + liste. Bu tanım doğrudan koda dönüşür:

static int size(Node p)  { if (p == null) return 0; return 1 + size(p.next); }
static int sum(Node p)   { if (p == null) return 0; return p.data + sum(p.next); }

static boolean contains(Node p, int x) {
    if (p == null) return false;
    if (p.data == x) return true;
    return contains(p.next, x);
}

static void printReverse(Node p) {
    if (p == null) return;
    printReverse(p.next);           // önce geri kalanı
    System.out.print(p.data + " "); // sonra kendini
}

4 → 7 → 1 → 9 listesi için size, sum, contains(1), contains(5) ve printReverse:

4 21 true false
9 1 7 4 

printReverse tek yönlü listeyi bozmadan tersten yazar; döngüyle bunu yapmak için ya listeyi ters çevirmen ya da bir yığın kullanman gerekirdi. Özyinelemede o yığın çağrı yığınının kendisi.

TUZAK · Taban durumu p.next == null yapmak. if (p.next == null) return 1; boş listede (p null) NullPointerException verir. Taban durumu en küçük girdi olan boş liste için yaz: p == null.

Geri izleme (backtracking) girişi

Bazı problemler “tüm olası seçimleri dene” ister: tüm alt kümeler, tüm permütasyonlar, satranç tahtasına vezir yerleştirme. Geri izleme şablonu:

çöz(durum):
    eğer durum tamsa: kaydet / yazdır, dön
    her seçenek için:
        seçeneği uygula
        çöz(yeni durum)
        seçeneği GERİ AL

Tüm alt kümeler

static void subsets(int[] a, int i, List<Integer> cur) {
    if (i == a.length) { System.out.print(cur + " "); return; }
    cur.add(a[i]);                 // al
    subsets(a, i + 1, cur);
    cur.remove(cur.size() - 1);    // geri al
    subsets(a, i + 1, cur);        // alma
}

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

Permütasyonlar

static void perms(String prefix, String rest) {
    if (rest.isEmpty()) { System.out.print(prefix + " "); return; }
    for (int i = 0; i < rest.length(); i++)
        perms(prefix + rest.charAt(i), rest.substring(0, i) + rest.substring(i + 1));
}

ABC ACB BAC BCA CAB CBA

N-Queens

n × n tahtaya n vezir, hiçbiri diğerini tehdit etmeyecek. Her satıra bir vezir koy; sütun ya da çapraz çakışıyorsa o sütunu atla, hiçbir sütun olmuyorsa bir önceki satıra dönüp onun vezirini kaydır. Programın saydığı çözüm sayıları:

4-queens: 2
5-queens: 10
6-queens: 4
7-queens: 40
8-queens: 92

Geri izleme kaba kuvvetten (brute force) iyidir çünkü çakışma görür görmez o dalı keser; 8 × 8’de $8^8 \approx 16$ milyon yerleşimin çok azını dener.

Sık yapılan hatalar

static int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

static void down(int n) {
    if (n == 0) return;
    System.out.print(n + " ");
    down(n - 1);
}
static void up(int n) {
    if (n == 0) return;
    up(n - 1);
    System.out.print(n + " ");
}

static int mystery(int n) {
    if (n == 0) return 0;
    return n % 10 + mystery(n / 10);
}

static long pow(long b, int n) {
    if (n == 0) return 1;
    return b * pow(b, n - 1);
}
static long fastPow(long b, int n) {
    if (n == 0) return 1;
    long half = fastPow(b, n / 2);
    return (n % 2 == 0) ? half * half : half * half * b;
}

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

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

static int size(Node p) {
    if (p == null) return 0;
    return 1 + size(p.next);
}

static void printReverse(Node p) {
    if (p == null) return;
    printReverse(p.next);
    System.out.print(p.data + " ");
}

static int bad(int n) {
    return n + bad(n - 1);
}

static boolean isPal(String s, int lo, int hi) {
    if (lo >= hi) return true;                       // 0 veya 1 karakter kaldı
    if (s.charAt(lo) != s.charAt(hi)) return false;
    return isPal(s, lo + 1, hi - 1);
}

static void subsets(int[] a, int i, List<Integer> cur) {
    if (i == a.length) { System.out.print(cur + " "); return; }
    cur.add(a[i]);
    subsets(a, i + 1, cur);
    cur.remove(cur.size() - 1);
    subsets(a, i + 1, cur);
}

static void perms(String prefix, String rest) {
    if (rest.isEmpty()) { System.out.print(prefix + " "); return; }
    for (int i = 0; i < rest.length(); i++)
        perms(prefix + rest.charAt(i),
              rest.substring(0, i) + rest.substring(i + 1));
}