Recursion (Özyineleme) | Ücretsiz Java Programlama: Sıfırdan İleri Seviyeye Kursu

Giriş — Bir Metot Kendini Çağırabilir mi?

Evet! Bir metot, kendi kendini çağırabilir. Buna recursion (özyineleme) denir. İlk başta garip gelebilir ama bazı problemler doğal olarak özyinelemeli yapıya sahiptir.

Analoji: Karşına bir ayna koyduğunu düşün. Aynada kendini görüyorsun. Ama aynanın arkasında başka bir ayna var ve onda da kendini görüyorsun, o aynanın arkasında da... Bu, sonsuza kadar giden bir tekrar — tıpkı bir metodun kendini çağırması gibi. Ama programlamada durdurma noktası (base case) olmalı, yoksa sonsuza gider ve program çöker.

Temel Kavramlar

Her recursive metotta iki temel bileşen olmalı:

Base case (Temel durum): Metot kendini çağırmayı bırakır ve bir değer döndürür. Durdurma noktası.
Recursive case (Özyinelemeli durum): Metot kendini daha küçük bir alt problemle çağırır.

public static void geriSay(int n) {
    if (n <= 0) {           // Base case
        System.out.println("Bitti!");
        return;
    }
    System.out.println(n);
    geriSay(n - 1);         // Recursive case — n bir azalarak kendini çağırır
}

public static void main(String[] args) {
    geriSay(5);
}

Çıktı:

5
4
3
2
1
Bitti!

Akış:

geriSay(5) → yazdır 5, çağır geriSay(4)
  geriSay(4) → yazdır 4, çağır geriSay(3)
    geriSay(3) → yazdır 3, çağır geriSay(2)
      geriSay(2) → yazdır 2, çağır geriSay(1)
        geriSay(1) → yazdır 1, çağır geriSay(0)
          geriSay(0) → yazdır "Bitti!", return
        return
      return
    return
  return
return

Her çağrı bir önceki çağrının bitmesini bekler. Bir yığın (stack) oluşur — en içteki çağrı biter, sonra dışına doğru teker teker döner.

Klasik Örnek: Faktöriyel

Faktöriyel (n!) en klasik recursive örnektir:

5! = 5 × 4 × 3 × 2 × 1 = 120
Matematiksel tanım: n! = n × (n-1)! ve 0! = 1

Bu tanım zaten recursive! Kendini referans ediyor.

Recursive Çözüm

public static long faktoriyel(int n) {
    if (n <= 1) {          // Base case: 0! = 1, 1! = 1
        return 1;
    }
    return n * faktoriyel(n - 1);  // Recursive case
}

public static void main(String[] args) {
    System.out.println("5! = " + faktoriyel(5));   // 120
    System.out.println("10! = " + faktoriyel(10)); // 3628800
    System.out.println("0! = " + faktoriyel(0));   // 1
}

Adım adım faktoriyel(5):

faktoriyel(5)
  = 5 * faktoriyel(4)
  = 5 * 4 * faktoriyel(3)
  = 5 * 4 * 3 * faktoriyel(2)
  = 5 * 4 * 3 * 2 * faktoriyel(1)
  = 5 * 4 * 3 * 2 * 1
  = 120

Iteratif Çözüm (Karşılaştırma)

public static long faktoriyelIteratif(int n) {
    long sonuc = 1;
    for (int i = 2; i <= n; i++) {
        sonuc *= i;
    }
    return sonuc;
}

İkisi de aynı sonucu verir. Iteratif versiyonu genellikle daha performanslıdır ama recursive versiyonu matematiksel tanıma daha yakındır.

Klasik Örnek: Fibonacci

Fibonacci serisi: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Tanım:

fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2) (n > 1 için)

Naif Recursive Çözüm

public static int fibonacci(int n) {
    if (n <= 0) return 0;  // Base case
    if (n == 1) return 1;  // Base case
    return fibonacci(n - 1) + fibonacci(n - 2);  // Recursive case
}

public static void main(String[] args) {
    for (int i = 0; i <= 10; i++) {
        System.out.print(fibonacci(i) + " ");
    }
    // 0 1 1 2 3 5 8 13 21 34 55
}

⚠️ Dikkat: Bu naif Fibonacci implementasyonu çok yavaştır! fibonacci(40) bile saniyeler sürer. Neden? Çünkü aynı değerler defalarca hesaplanır:

fibonacci(5)
├── fibonacci(4)
│   ├── fibonacci(3)
│   │   ├── fibonacci(2) ← tekrar!
│   │   └── fibonacci(1)
│   └── fibonacci(2) ← tekrar!
└── fibonacci(3) ← tekrar!
    ├── fibonacci(2) ← tekrar!
    └── fibonacci(1)

fibonacci(2) 3 kez, fibonacci(3) 2 kez hesaplanıyor. n büyüdükçe bu katlanarak artar — O(2ⁿ) zaman karmaşıklığı!

Memoization ile İyileştirme

Hesaplanan değerleri bir dizide saklayarak tekrar hesaplamayı önleyebilirsin:

public static long fibMemo(int n, long[] cache) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    
    if (cache[n] != 0) {
        return cache[n];  // Zaten hesaplandı, cache'den döndür
    }
    
    cache[n] = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
    return cache[n];
}

public static void main(String[] args) {
    int n = 50;
    long[] cache = new long[n + 1];
    System.out.println("fib(50) = " + fibMemo(50, cache));
    // 12586269025 — anında hesaplar!
}

Memoization ile zaman karmaşıklığı O(n)'e düşer. Bu, dynamic programming yaklaşımının temelidir.

Iteratif Fibonacci (En Verimli)

public static long fibIteratif(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    
    long a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        long c = a + b;
        a = b;
        b = c;
    }
    return b;
}

Bu, O(n) zaman ve O(1) alan kullanır — en verimli çözüm.

Stack Overflow — Recursive'ın Karanlık Yüzü

Her metot çağrısı call stack'e bir frame ekler. Recursive çağrılar çok derine inerse stack dolar ve StackOverflowError alırsın.

// KÖT�— base case yok!
public static void sonsuzRecursion() {
    sonsuzRecursion();  // Sonsuza kadar kendini çağırır
}
// java.lang.StackOverflowError!

// DİKKATLİ — base case var ama n çok büyük
public static long faktoriyel(int n) {
    if (n <= 1) return 1;
    return n * faktoriyel(n - 1);
}

faktoriyel(100000);  // StackOverflowError! Stack bu kadar derinliği kaldırmaz.

Java'da varsayılan stack boyutu genellikle ~512KB-1MB'dır. Her frame birkaç yüz byte tuttuğu için yaklaşık 5.000-10.000 derinlikte stack overflow olur.

Stack Overflow'u Önleme

Her zaman base case yaz — ve base case'e ulaşıldığından emin ol
Her recursive çağrıda problem küçülmeli — sonsuz recursion'ı önler
Çok derin recursion bekliyorsan iteratife geç — döngü stack kullanmaz
JVM stack boyutunu artır — geçici çözüm: java -Xss4m Program

⚠️ Dikkat: Stack overflow, programı kurtarılamaz şekilde çökertir. Error'dur, exception değil — catch etmen genellikle mantıksızdır.

Tail Recursion (Kuyruk Özyineleme)

Tail recursion, recursive çağrının metodun son işlemi olduğu durumdur. Çağrıdan sonra başka bir işlem yapılmaz.

Normal Recursion vs Tail Recursion

// Normal recursion — çağrıdan sonra çarpma işlemi var
public static long faktoriyel(int n) {
    if (n <= 1) return 1;
    return n * faktoriyel(n - 1);  // faktoriyel() dönüşü * n
}

// Tail recursion — çağrı son işlem, başka bir şey yok
public static long faktoriyelTail(int n, long accumulator) {
    if (n <= 1) return accumulator;
    return faktoriyelTail(n - 1, n * accumulator);  // Son işlem — başka hesap yok
}

// Kullanım
faktoriyelTail(5, 1);

Tail recursion'da sonuç accumulator parametresinde biriktiriliyor. Metot döndüğünde yapılacak başka iş yok.

Tail Recursion Neden Önemli?

Bazı diller (Scala, Kotlin, Haskell) tail recursion'ı optimize eder — recursive çağrıyı döngüye çevirir, böylece stack dolmaz. Buna Tail Call Optimization (TCO) denir.

Java TCO yapmaz! Java'da tail recursion yazsan bile stack hâlâ dolar. Ama:

Kodu daha okunabilir yapar
Kolayca iteratife çevrilebilir
Kotlin'e geçersen tailrec keyword'ü ile optimize edilir

// Tail recursion → iteratife çevirmek kolay
public static long faktoriyelIteratif(int n) {
    long accumulator = 1;
    while (n > 1) {
        accumulator *= n;
        n--;
    }
    return accumulator;
}

💡 İpucu: Java'da derin recursion gerekiyorsa, tail recursion yaz ve sonra iteratife çevir. Bu dönüşüm mekanik bir işlemdir.

Recursion Kullanım Alanları

Recursion şu durumlarda doğal ve güçlüdür:

1. Ağaç Yapıları

Dosya sistemi, DOM ağacı, oyun ağaçları... hep recursive yapılardır:

// Dosya sistemi — klasörlerin içinde klasörler var
public static void dosyalariListele(File dizin, String girinti) {
    File[] dosyalar = dizin.listFiles();
    if (dosyalar == null) return;
    
    for (File dosya : dosyalar) {
        System.out.println(girinti + dosya.getName());
        if (dosya.isDirectory()) {
            dosyalariListele(dosya, girinti + "  ");  // Recursive!
        }
    }
}

2. Bölüp Fethet (Divide and Conquer)

Problemi küçük parçalara böl, her parçayı recursive çöz, sonuçları birleştir:

// Binary Search — sıralı dizide eleman arama
public static int binarySearch(int[] dizi, int hedef, int sol, int sag) {
    if (sol > sag) return -1;  // Base case: bulunamadı
    
    int orta = (sol + sag) / 2;
    
    if (dizi[orta] == hedef) return orta;       // Base case: bulundu
    if (dizi[orta] > hedef) return binarySearch(dizi, hedef, sol, orta - 1);
    return binarySearch(dizi, hedef, orta + 1, sag);
}

// Kullanım
int[] dizi = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int index = binarySearch(dizi, 23, 0, dizi.length - 1);
System.out.println("23 → index " + index);  // 5

3. Üs Alma (Hızlı)

// O(log n) — divide and conquer
public static long hizliUs(long taban, int us) {
    if (us == 0) return 1;           // Base case
    if (us % 2 == 0) {
        long yarim = hizliUs(taban, us / 2);
        return yarim * yarim;         // Çift üs: x^n = (x^(n/2))^2
    }
    return taban * hizliUs(taban, us - 1);  // Tek üs: x^n = x * x^(n-1)
}

System.out.println(hizliUs(2, 10));  // 1024
System.out.println(hizliUs(3, 5));   // 243

4. String İşlemleri

// String ters çevirme
public static String tersCevir(String s) {
    if (s.length() <= 1) return s;  // Base case
    return tersCevir(s.substring(1)) + s.charAt(0);
}

System.out.println(tersCevir("Java"));  // avaJ

// Palindrom kontrolü
public static boolean palindromMu(String s) {
    if (s.length() <= 1) return true;  // Base case
    if (s.charAt(0) != s.charAt(s.length() - 1)) return false;
    return palindromMu(s.substring(1, s.length() - 1));
}

System.out.println(palindromMu("kayak"));  // true
System.out.println(palindromMu("java"));   // false

Recursion vs Iteration — Hangisini Kullanalım?

Kriter	Recursion	Iteration
Okunabilirlik	Doğal recursive problemlerde daha iyi	Basit tekrarlarda daha iyi
Performans	Stack overhead var	Genellikle daha hızlı
Bellek	Her çağrı stack frame tutar	Sabit bellek
Stack overflow	Risk var	Risk yok
Ağaç yapıları	Mükemmel	Zor ve karmaşık
Basit tekrar	Gereksiz karmaşıklık	İdeal

Kural: Eğer problem doğal olarak recursive ise (ağaçlar, divide & conquer), recursion kullan. Eğer basit bir tekrar ise (1'den N'e kadar say), iteration kullan.

Pratik Örnek: Hanoi Kuleleri

Klasik recursion problemi. 3 çubuk var, birinde n tane disk (küçükten büyüğe). Tüm diskleri başka bir çubuğa taşı. Kurallar:

Bir seferde bir disk taşınır
Büyük disk küçüğün üstüne konamaz

public static void hanoi(int n, char kaynak, char hedef, char yardimci) {
    if (n == 1) {
        System.out.println("Disk 1: " + kaynak + " → " + hedef);
        return;
    }
    
    hanoi(n - 1, kaynak, yardimci, hedef);  // n-1 diski yardımcıya taşı
    System.out.println("Disk " + n + ": " + kaynak + " → " + hedef);
    hanoi(n - 1, yardimci, hedef, kaynak);  // n-1 diski yardımcıdan hedefe taşı
}

public static void main(String[] args) {
    hanoi(3, 'A', 'C', 'B');
}

Çıktı:

Disk 1: A → C
Disk 2: A → B
Disk 1: C → B
Disk 3: A → C
Disk 1: B → A
Disk 2: B → C
Disk 1: A → C

3 disk için 7 hamle. n disk için 2ⁿ - 1 hamle gerekir. Bu problemi iteratif çözmek çok daha karmaşıktır.

Pratik Örnek: Toplama (Recursive)

// Dizinin toplamını recursive hesapla
public static int diziToplami(int[] dizi, int index) {
    if (index >= dizi.length) return 0;  // Base case
    return dizi[index] + diziToplami(dizi, index + 1);
}

public static void main(String[] args) {
    int[] sayilar = {3, 7, 1, 8, 4};
    System.out.println("Toplam: " + diziToplami(sayilar, 0)); // 23
}

Mutual Recursion (Karşılıklı Özyineleme)

İki metot birbirini çağırabilir:

public static boolean ciftMi(int n) {
    if (n == 0) return true;
    return tekMi(n - 1);
}

public static boolean tekMi(int n) {
    if (n == 0) return false;
    return ciftMi(n - 1);
}

System.out.println(ciftMi(4));  // true
System.out.println(tekMi(7));   // true

Bu akademik bir örnek — pratikte n % 2 kullanırsın. Ama mutual recursion, parser'larda ve state machine'lerde kullanılır.

Recursion Düşünme Tekniği

Recursive çözüm bulmak başta zor gelebilir. Şu adımları izle:

Adım 1: Base case'i tanımla

"En basit durum ne? Hesaplamaya gerek olmadan cevabı ne?"

Faktöriyel: n <= 1 → 1
Fibonacci: n = 0 → 0, n = 1 → 1
Dizi toplamı: boş dizi → 0
String ters çevirme: uzunluk <= 1 → kendisi

Adım 2: Recursive case'i tanımla

"Problemi nasıl küçültebilirim? Küçük çözümden büyük çözümü nasıl elde ederim?"

Faktöriyel: n! = n × (n-1)!
Fibonacci: fib(n) = fib(n-1) + fib(n-2)
Dizi toplamı: toplam = ilkEleman + kalanınToplamı
String ters çevirme: ters = ters(kalanString) + ilkKarakter

Adım 3: Base case'e yaklaşıldığından emin ol

"Her recursive çağrıda problem gerçekten küçülüyor mu?"

Faktöriyel: n → n-1 → küçülüyor ✓
Binary search: aralık yarıya iniyor ✓
Hatalı: n → n+1 → büyüyor ✗

Pratik: Recursive Düşünme Alıştırması

Problem: Bir string'deki belirli bir karakterin kaç kez geçtiğini say.

Base case: String boşsa → 0
Recursive case: İlk karakter eşleşiyorsa 1 + kalan, eşleşmiyorsa 0 + kalan
Küçülme: Her adımda string 1 karakter kısalıyor ✓

public static int karakterSay(String s, char hedef) {
    if (s.isEmpty()) return 0;  // Base case
    
    int ilkKarakter = (s.charAt(0) == hedef) ? 1 : 0;
    return ilkKarakter + karakterSay(s.substring(1), hedef);
}

System.out.println(karakterSay("merhaba", 'a'));  // 2

Recursion ve Backtracking (Kısa Bakış)

Backtracking, recursion'ın güçlü bir uygulamasıdır. Bir çözüm ararken ilerler, çıkmaza girince geri döner ve başka bir yol dener.

// Basit labirent: 1 = yol, 0 = duvar, 2 = çözüm yolu
public static boolean labirentCoz(int[][] labirent, int x, int y) {
    // Sınır kontrolü
    if (x < 0 || x >= labirent.length || y < 0 || y >= labirent[0].length) {
        return false;
    }
    // Duvar veya zaten geçilmiş
    if (labirent[x][y] != 1) return false;
    
    // Hedefe ulaştık (sağ alt köşe)
    if (x == labirent.length - 1 && y == labirent[0].length - 1) {
        labirent[x][y] = 2;
        return true;
    }
    
    labirent[x][y] = 2;  // Yolu işaretle
    
    // 4 yöne dene (sağ, aşağı, sol, yukarı)
    if (labirentCoz(labirent, x, y + 1)) return true;
    if (labirentCoz(labirent, x + 1, y)) return true;
    if (labirentCoz(labirent, x, y - 1)) return true;
    if (labirentCoz(labirent, x - 1, y)) return true;
    
    labirent[x][y] = 1;  // Geri dön (backtrack)
    return false;
}

Bu ileri seviye bir konu — şimdi anlamak zorunda değilsin. Ama recursion'ın gücünü göstermesi açısından güzel bir örnek.

Performans Karşılaştırması

Aynı problemi recursive ve iteratif çözelim ve performansı karşılaştıralım:

// Benchmark: 1'den N'e toplam
public static void main(String[] args) {
    int n = 10_000;
    
    // Iteratif
    long baslangic = System.nanoTime();
    long sonucIter = 0;
    for (int i = 1; i <= n; i++) sonucIter += i;
    long iterSure = System.nanoTime() - baslangic;
    
    // Recursive
    baslangic = System.nanoTime();
    long sonucRec = toplamRecursive(n);
    long recSure = System.nanoTime() - baslangic;
    
    System.out.printf("Iteratif: %d (%d ns)%n", sonucIter, iterSure);
    System.out.printf("Recursive: %d (%d ns)%n", sonucRec, recSure);
}

public static long toplamRecursive(int n) {
    if (n <= 0) return 0;
    return n + toplamRecursive(n - 1);
}

Sonuç: Recursive versiyon genellikle 2-5x daha yavaştır (stack frame overhead). Basit tekrar problemlerinde iteration her zaman tercih et.

Yaygın Hatalar

1. Base Case Unutmak

// SONSUZ RECURSION — base case yok!
public static int topla(int n) {
    return n + topla(n - 1);  // Ne zaman duracak?
}

2. Base Case'e Ulaşamama

// SONSUZ RECURSION — n hiç 0 olmaz!
public static void say(int n) {
    if (n == 0) return;
    say(n + 1);  // n artıyor, azalmıyor!
}
say(5);  // 5, 6, 7, 8... sonsuz!

3. Gereksiz Recursion

// GEREKSIZ — döngü çok daha basit
public static int topla(int n) {
    if (n <= 0) return 0;
    return n + topla(n - 1);
}

// DAHA İYİ
int toplam = n * (n + 1) / 2;  // Gauss formülü — O(1)!

Özet

Recursion, bir metodun kendini çağırmasıdır. Her recursive metotta base case (durdurma) ve recursive case (kendini çağırma) olmalı.
Faktöriyel ve Fibonacci klasik recursive örneklerdir. Fibonacci'nin naif recursive çözümü çok yavaştır — memoization veya iteration kullan.
StackOverflowError, recursion çok derine indiğinde oluşur. Base case'in doğru olduğundan ve probleminher adımda küçüldüğünden emin ol.
Tail recursion, recursive çağrının son işlem olduğu durumdur. Java optimize etmez ama kolayca iteratife çevrilebilir.
Ağaç yapıları ve divide & conquer problemlerinde recursion doğal çözümdür. Basit tekrarlarda iteration tercih et.
Base case'i asla unutma — yoksa sonsuz recursion ve stack overflow kaçınılmaz.
Recursive düşünmeyi öğren: Base case → recursive case → küçülme garantisi. Bu üç adımı her problemde uygula.

Alıştırma Fikirleri

usAl(int taban, int us) — taban^üs hesapla (recursive)
enBuyuk(int[] dizi, int index) — dizideki en büyük elemanı recursive bul
ikiliSistem(int sayi) — bir sayıyı ikili (binary) sisteme recursive çevir
tersSirala(int[] dizi, int sol, int sag) — diziyi recursive ters çevir