Özyineleme (recursion)

Özyineleme (recursion), bir metodun problemi çözmek için kendini daha küçük bir girdiyle çağırmasıdır. Sınavda iki biçimde gelir: “What is printed?” (çağrı yığınını izleyip çıktı sırasını bulmak) ve “write a recursive method” (döngü kullanmadan). İkisinin de anahtarı aynı: her çağrının kendi değişkenleri olan ayrı bir kopya gibi çalıştığını görmek.

Altın kurallar:

1. Base case olmadan özyineleme olmaz. En küçük durumda metot kendini çağırmadan döner.
2. Her çağrı base case’e yaklaşmalı. n - 1, n / 10, substring(1) gibi.
3. Her çağrının kendi değişkenleri var. Bir çağrıdaki n, diğerinin n’ini etkilemez.
4. Çağrıdan sonra gelen satırlar ters sırada çalışır. En son çağrılan ilk biter.

Base case ve recursive step

Faktöriyel tanımı zaten özyinelemelidir: $n! = n \cdot (n-1)!$, ve $0! = 1! = 1$.

static long factorial(int n) {
    if (n <= 1) return 1;            // base case
    return n * factorial(n - 1);     // recursive step
}
System.out.println(factorial(5) + " " + factorial(0) + " " + factorial(20));

120 1 2432902008176640000

long kullandık çünkü faktöriyel çok hızlı büyür; int ile 13! taşar. 20! long’un sığabildiği en büyük faktöriyeldir.

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

Her metot çağrısı yığına (stack) bir çerçeve (stack frame) ekler: parametreler, yerel değişkenler ve “dönünce nereden devam edeceğim” bilgisi. Metot dönünce çerçevesi yığından çıkar. Özyinelemede aynı metodun birçok çerçevesi aynı anda yığında durur.

Faktöriyele girinti ekleyip her çağrıyı ve dönüşü basarsak:

factorial(4)
  factorial(3)
    factorial(2)
      factorial(1)
      return 1
    return 2
  return 6
return 24

yığın (en üst = şu an çalışan)
                       ┌────────────┐
                       │ f(1) → 1   │   base case, döner
                  ┌────┴────────────┤
                  │ f(2) → 2 * 1    │
             ┌────┴─────────────────┤
             │ f(3) → 3 * 2         │
        ┌────┴──────────────────────┤
        │ f(4) → 4 * 6 = 24         │
        └───────────────────────────┘

Çıktı sırası: önce mi, sonra mı?

İzleme sorularının çoğu bu tek fikre dayanır: özyinelemeli çağrıdan önce yazılan satırlar iniş sırasında, sonra yazılan satırlar dönüş sırasında (ters sırayla) çalışır.

static void printBefore(int n) {
    if (n == 0) return;
    System.out.print(n + " ");      // önce bas
    printBefore(n - 1);
}
static void printAfter(int n) {
    if (n == 0) return;
    printAfter(n - 1);
    System.out.print(n + " ");      // dönüşte bas
}
static void both(int n) {
    if (n == 0) return;
    System.out.print("<" + n);
    both(n - 1);
    System.out.print(n + ">");
}
printBefore(3); System.out.println();
printAfter(3);  System.out.println();
both(3);        System.out.println();

3 2 1 
1 2 3 
<3<2<11>2>3>

İki çağrı yapan metotlarda bir ağaç çiz. tree(n) önce tree(n-1), sonra n’yi basar, sonra yine tree(n-1):

tree(3)
├─ tree(2)
│  ├─ tree(1) → "1"
│  ├─ "2"
│  └─ tree(1) → "1"
├─ "3"
└─ tree(2) → "121"
sonuç: 1213121

Klasik örnekler

Fibonacci

$F(0) = 0$, $F(1) = 1$, $F(n) = F(n-1) + F(n-2)$.

static int fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}
for (int i = 0; i <= 10; i++) System.out.print(fib(i) + " ");

0 1 1 2 3 5 8 13 21 34 55 

Kısa ve okunaklı, ama çok yavaş: aynı değerleri tekrar tekrar hesaplar. Bir sayaçla toplam çağrı sayısını ölçtük:

Çağrı sayısı yaklaşık $O(2^n)$ büyür. Aynı işi döngü $O(n)$ adımda yapar. Sınavda “neden yavaş” sorusunun cevabı: tekrar eden alt problemler.

Üs alma

static double power(double base, int exp) {
    if (exp == 0) return 1;
    if (exp < 0) return 1 / power(base, -exp);
    return base * power(base, exp - 1);          // exp kadar çağrı
}
static long fastPower(long b, int e) {
    if (e == 0) return 1;
    long half = fastPower(b, e / 2);             // problemi yarıya böl
    return (e % 2 == 0) ? half * half : half * half * b;
}
System.out.println(power(2, 10) + " " + power(3, 0) + " " + power(2, -2));
System.out.println(fastPower(2, 30) + " calls=" + pcalls);

1024.0 1.0 0.25
1073741824 calls=6

Düz sürüm $2^{30}$ için 31 çağrı yapardı; yarıya bölen sürüm 6 çağrıda bitirdi (30, 15, 7, 3, 1, 0). Bu $O(\log n)$ fikri ikili aramada da var.

Palindrom

static boolean isPalindrome(String s) {
    if (s.length() <= 1) return true;
    if (s.charAt(0) != s.charAt(s.length() - 1)) return false;
    return isPalindrome(s.substring(1, s.length() - 1));
}
System.out.println(isPalindrome("racecar") + " " + isPalindrome("abca") + " "
                   + isPalindrome("") + " " + isPalindrome("noon"));

true false true true

İkili arama (binary search)

Sıralı dizide aranan değeri ortadaki elemanla karşılaştır; küçükse sol yarıda, büyükse sağ yarıda aynı işi tekrarla. Her çağrı arama aralığını yarıya indirir. (13. haftada döngülü sürümüyle karşılaştıracağız.)

static int binarySearch(int[] a, int key, int low, int high) {
    if (low > high) return -1;                       // aralık boş: yok
    int mid = (low + high) / 2;
    System.out.println("  low=" + low + " high=" + high + " mid=" + mid + " a[mid]=" + a[mid]);
    if (a[mid] == key) return mid;
    if (key < a[mid]) return binarySearch(a, key, low, mid - 1);
    return binarySearch(a, key, mid + 1, high);
}
int[] a = {3, 8, 15, 21, 30, 42, 57, 66, 80};
System.out.println("found at " + binarySearch(a, 57, 0, a.length - 1));
System.out.println("found at " + binarySearch(a, 10, 0, a.length - 1));

  low=0 high=8 mid=4 a[mid]=30
  low=5 high=8 mid=6 a[mid]=57
found at 6
  low=0 high=8 mid=4 a[mid]=30
  low=0 high=3 mid=1 a[mid]=8
  low=2 high=3 mid=2 a[mid]=15
found at -1

İz satırları “found at” satırından önce basılıyor: println’ın argümanındaki birleştirme, binarySearch tamamen bitince yapılabilir.

Diğer kalıplar

static int sumDigits(int n) {               // 9045 → 9+0+4+5
    if (n < 10) return n;
    return n % 10 + sumDigits(n / 10);
}
static int sumArray(int[] a, int i) {       // dizi + indeks parametresi
    if (i == a.length) return 0;
    return a[i] + sumArray(a, i + 1);
}
static int countX(String s) {               // String'i harf harf küçült
    if (s.isEmpty()) return 0;
    return (s.charAt(0) == 'x' ? 1 : 0) + countX(s.substring(1));
}
System.out.println(sumDigits(9045));
System.out.println(sumArray(new int[]{4, 7, 1, 8}, 0));
System.out.println(countX("xaxbxx"));

18
20
4

Özyineleme mi, döngü mü?

TUZAK · base case’i atlamak. m2(n) metodu n + m2(n - 2) döndürüyorsa ve base case n == 0 ise, tek sayılar 0’ı hiç görmez (7, 5, 3, 1, −1, …) ve yığın taşar. n <= 0 yazmak bu yüzden daha güvenli. Base case yazarken “her girdi buraya ulaşıyor mu?” diye sor.

Base case’siz bir metot (return n + bad(n - 1);) derlenir ama çalışınca StackOverflowError fırlatır; denemede tam olarak bu oldu. Her yolun return etmediği bir metot ise hiç derlenmez: missing return statement.

Sık yapılan hatalar

static void printBefore(int n) {
    if (n == 0) return;
    System.out.print(n + " ");
    printBefore(n - 1);
}
static void printAfter(int n) {
    if (n == 0) return;
    printAfter(n - 1);
    System.out.print(n + " ");
}
// in main:
printBefore(3); System.out.println();
printAfter(3);

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

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

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

static int mystery(int a, int b) {
    if (b == 0) return a;
    return mystery(b, a % b);
}
// in main:
System.out.println(mystery(48, 18) + " " + mystery(17, 5));

static String reverse(String s) {
    if (s.isEmpty()) return s;
    return reverse(s.substring(1)) + s.charAt(0);
}
// in main:
System.out.println(reverse("stack"));

static int m2(int n) {
    if (n <= 0) return 0;
    return n + m2(n - 2);
}
// in main:
System.out.println(m2(7) + " " + m2(6));

static int sum(int n) {
    if (n == 0) return 0;
    else if (n > 0) return n + sum(n - 1);
}

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

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

public static boolean isPalindrome(String s) {
    if (s.length() <= 1) return true;                       // base case
    if (s.charAt(0) != s.charAt(s.length() - 1)) return false;
    return isPalindrome(s.substring(1, s.length() - 1));    // ortası
}