Recursion (Özyineleme)

Bir ayna karşısında durduğunu ve arkanda da başka bir ayna olduğunu düşün. Kendin aynada yansıyor, o yansıma da diğer aynada yansıyor, o da ötekinde... Sonsuz bir tekrar. İşte recursion (özyineleme) bir fonksiyonun kendini çağırmasıdır. Ama aynalardan farklı olarak, programlamada bu tekrarın bir durma noktası olmalı — yoksa sonsuza kadar gider ve program çöker.

Recursion bazı problemleri çok zarif şekilde çözer. Ama yanlış kullanıldığında performans canavarına dönüşür. Bu derste recursion'ı, ne zaman kullanılacağını ve tehlikelerini öğreneceksin.

Recursion Nasıl Çalışır?

Recursive bir fonksiyon iki parçadan oluşur:

1. Base case (taban durum): Fonksiyonun kendini çağırmayı bıraktığı nokta — durma koşulu

2. Recursive case (özyinelemeli durum): Fonksiyonun kendini daha küçük bir problemle çağırdığı kısım

#include <iostream>
using namespace std;

void geriSay(int n) {
    // Base case — durma noktası
    if (n <= 0) {
        cout << "Başla!" << endl;
        return;
    }

    // Recursive case — kendini çağır
    cout << n << "..." << endl;
    geriSay(n - 1);  // Daha küçük problemle tekrar çağır
}

int main() {
    geriSay(5);
    return 0;
}

Çıktı:

5...
4...
3...
2...
1...
Başla!

Akış şöyle ilerler:

• geriSay(5) → 5 yazdır, geriSay(4) çağır

• geriSay(4) → 4 yazdır, geriSay(3) çağır

• ...

• geriSay(1) → 1 yazdır, geriSay(0) çağır

• geriSay(0) → base case! "Başla!" yazdır ve dön

Her çağrı, problemi bir adım küçültür. Base case'e ulaşınca çağrılar geriye doğru çözülür.

⚠️ Dikkat: Base case olmadan recursion sonsuz döngüye girer ve program stack overflow hatası ile çöker. Her recursive fonksiyonda base case olduğundan emin ol.

Faktöriyel — Klasik Örnek

Matematik'te faktöriyel:

• 5! = 5 × 4 × 3 × 2 × 1 = 120

• n! = n × (n-1)!

• 0! = 1 (base case)

Bu tanım zaten özyinelemeli! Doğrudan koda çevirebiliriz:

#include <iostream>
using namespace std;

int faktoriyel(int n) {
    // Base case
    if (n <= 1) {
        return 1;
    }

    // Recursive case
    return n * faktoriyel(n - 1);
}

int main() {
    cout << "5! = " << faktoriyel(5) << endl;   // 120
    cout << "0! = " << faktoriyel(0) << endl;   // 1
    cout << "10! = " << faktoriyel(10) << endl; // 3628800

    return 0;
}

faktoriyel(5) çağrı zinciri:

faktoriyel(5) = 5 * faktoriyel(4)
faktoriyel(4) = 4 * faktoriyel(3)
faktoriyel(3) = 3 * faktoriyel(2)
faktoriyel(2) = 2 * faktoriyel(1)
faktoriyel(1) = 1  ← base case

Geriye doğru çözülme:

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

Fibonacci — İkili Özyineleme

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

Her sayı önceki iki sayının toplamıdır: fib(n) = fib(n-1) + fib(n-2)

#include <iostream>
using namespace std;

int fibonacci(int n) {
    // Base cases
    if (n <= 0) return 0;
    if (n == 1) return 1;

    // Recursive case — iki kez kendini çağırır
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    cout << "Fibonacci dizisi: ";
    for (int i = 0; i < 10; i++) {
        cout << fibonacci(i) << " ";
    }
    cout << endl;
    // Çıktı: 0 1 1 2 3 5 8 13 21 34

    return 0;
}

Bu kod doğru çalışır ama büyük bir problemi var: aynı değerler defalarca hesaplanır. fibonacci(5) hesaplanırken fibonacci(3) iki kez, fibonacci(2) üç kez hesaplanır. fibonacci(40) gibi bir değer için milyarlarca çağrı yapılır.

⚠️ Dikkat: Naif (memoization'sız) Fibonacci implementasyonu üstel karmaşıklığa (O(2^n)) sahiptir. fibonacci(45) bile dakikalar sürebilir. Gerçek projelerde ya memoization ya da iteratif çözüm kullan.

Stack Overflow Riski

Her fonksiyon çağrısı bellekte stack frame oluşturur. Recursive çağrılar bu frame'leri üst üste yığar. Stack belleği sınırlı olduğu için çok derin recursion stack overflow hatasına yol açar.

#include <iostream>
using namespace std;

// TEHLİKELİ — base case yok!
void sonsuzRecursion(int n) {
    cout << n << endl;
    sonsuzRecursion(n + 1);  // Sonsuza kadar çağrı
}

// TEHLİKELİ — base case var ama çok derin
long long tehlikeliFaktoriyel(int n) {
    if (n <= 1) return 1;
    return n * tehlikeliFaktoriyel(n - 1);
}

int main() {
    // sonsuzRecursion(1);  // Stack overflow!

    // Genellikle 10.000-100.000 arası çağrı stack'i doldurur
    // tehlikeliFaktoriyel(1000000);  // Stack overflow!

    return 0;
}

Stack Overflow'dan Kaçınma

1. Base case'in doğru olduğundan emin ol — her çağrıda base case'e yaklaşılmalı

2. Recursion derinliğini sınırla — çok derin gidecekse iteratif çözüm tercih et

3. Tail recursion kullan (bir sonraki bölüm)

Tail Recursion — Kuyruk Özyineleme

Bir recursive fonksiyonda, recursive çağrı fonksiyonun en son işi ise buna tail recursion (kuyruk özyineleme) denir. Bazı derleyiciler tail recursion'ı optimize edip döngüye çevirebilir — bu sayede stack overflow riski azalır.

#include <iostream>
using namespace std;

// Normal recursion — çarpma işlemi recursive çağrıdan SONRA yapılıyor
int faktoriyel_normal(int n) {
    if (n <= 1) return 1;
    return n * faktoriyel_normal(n - 1);  // Çağrı dönünce çarpma var
}

// Tail recursion — sonuç parametre olarak taşınıyor
int faktoriyel_tail(int n, int sonuc = 1) {
    if (n <= 1) return sonuc;
    return faktoriyel_tail(n - 1, n * sonuc);  // Son iş: recursive çağrı
}

int main() {
    cout << faktoriyel_normal(5) << endl;  // 120
    cout << faktoriyel_tail(5) << endl;    // 120

    return 0;
}

Normal versiyonda faktoriyel_normal(5) dönüş değerini 5 * ile çarpmak zorunda — yani çağrı döndükten sonra yapılacak iş var. Stack frame'i tutmak gerekir.

Tail versiyonda faktoriyel_tail(4, 5) çağrısı yapılıyor ve başka iş yok. Derleyici bunu optimize edebilir: "Yeni bir stack frame açmama gerek yok, mevcut frame'i yeniden kullan."

💡 İpucu: C++ standardı tail call optimization'ı garanti etmez ama GCC ve Clang -O2 veya üstü optimizasyon seviyelerinde genellikle uygular. Performans kritik kodda buna güvenmek yerine iteratif çözüm tercih et.

Recursion vs Iteration — Ne Zaman Hangisi?

Her recursive çözümün iteratif (döngü tabanlı) bir karşılığı vardır. Soru şu: hangisi daha uygun?

Faktöriyel Karşılaştırması

#include <iostream>
using namespace std;

// Recursive
long long faktoriyel_recursive(int n) {
    if (n <= 1) return 1;
    return n * faktoriyel_recursive(n - 1);
}

// Iterative
long long faktoriyel_iterative(int n) {
    long long sonuc = 1;
    for (int i = 2; i <= n; i++) {
        sonuc *= i;
    }
    return sonuc;
}

int main() {
    cout << faktoriyel_recursive(10) << endl;  // 3628800
    cout << faktoriyel_iterative(10) << endl;  // 3628800

    return 0;
}

İteratif versiyon stack overflow riski taşımaz ve genellikle daha hızlıdır.

Fibonacci — Memoization ile İyileştirme

Recursive Fibonacci'nin performans sorunu memoization ile çözülebilir:

#include <iostream>
#include <unordered_map>
using namespace std;

unordered_map<int, long long> cache;

long long fibonacci_memo(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;

    // Cache'de varsa doğrudan döndür
    auto it = cache.find(n);
    if (it != cache.end()) {
        return it->second;
    }

    // Hesapla ve cache'e kaydet
    long long sonuc = fibonacci_memo(n - 1) + fibonacci_memo(n - 2);
    cache[n] = sonuc;
    return sonuc;
}

int main() {
    cout << fibonacci_memo(50) << endl;  // 12586269025
    // Naif recursion ile bu hesaplama saatler sürerdi!

    return 0;
}

Karar Tablosu

Daha Fazla Örnek

Bir Sayının Basamaklarını Toplama

#include <iostream>
using namespace std;

int basamakToplami(int n) {
    n = (n < 0) ? -n : n;  // Negatifse pozitif yap
    if (n < 10) return n;  // Tek basamak — base case
    return (n % 10) + basamakToplami(n / 10);
}

int main() {
    cout << basamakToplami(12345) << endl;  // 1+2+3+4+5 = 15
    cout << basamakToplami(999) << endl;    // 9+9+9 = 27

    return 0;
}

Üs Alma (Power)

#include <iostream>
using namespace std;

// Naif: O(n) — n kez çarpma
double us(double taban, int n) {
    if (n == 0) return 1;
    if (n < 0) return 1.0 / us(taban, -n);
    return taban * us(taban, n - 1);
}

// Hızlı: O(log n) — böl ve yönet
double hizliUs(double taban, int n) {
    if (n == 0) return 1;
    if (n < 0) return 1.0 / hizliUs(taban, -n);

    if (n % 2 == 0) {
        double yarim = hizliUs(taban, n / 2);
        return yarim * yarim;
    }
    return taban * hizliUs(taban, n - 1);
}

int main() {
    cout << us(2, 10) << endl;      // 1024
    cout << hizliUs(2, 10) << endl;  // 1024

    return 0;
}

hizliUs fonksiyonu "x^10 = (x^5)^2" mantığıyla çalışır. Her adımda problemi yarıya indirir — bu yüzden O(log n) karmaşıklığına sahiptir.

Yaygın Recursion Hataları

1. Base Case Unutmak

// YANLIŞ — sonsuza gider
int topla(int n) {
    return n + topla(n - 1);  // Base case yok!
}

2. Base Case'e Yaklaşmamak

// YANLIŞ — n hiç küçülmüyor
int topla(int n) {
    if (n == 0) return 0;
    return n + topla(n);  // n-1 olmalıydı!
}

3. Yanlış Base Case

// YANLIŞ — negatif sayılar için base case'e ulaşılamaz
int faktoriyel(int n) {
    if (n == 0) return 1;  // n < 0 olursa?
    return n * faktoriyel(n - 1);
}
// faktoriyel(-1) → sonsuz recursion!

// DOĞRU
int faktoriyel(int n) {
    if (n <= 1) return 1;  // 0 ve negatifler güvende
    return n * faktoriyel(n - 1);
}

Özet

• Recursion bir fonksiyonun kendini çağırmasıdır — her çağrı problemi küçültmeli ve bir base case'e ulaşmalı

• Base case olmadan recursion sonsuz döngüye girer ve stack overflow ile çöker

• Faktöriyel ve Fibonacci klasik recursion örnekleridir — Fibonacci'nin naif versiyonu üstel karmaşıklığa sahiptir

• Tail recursion recursive çağrıyı fonksiyonun son işi olarak yapar — derleyici optimize edebilir

• Recursion ağaç yapıları ve divide-and-conquer için doğaldır; iteration basit tekrar ve performans kritik durumlar için tercih edilir

• Memoization, tekrarlanan hesaplamaları cache'leyerek recursive çözümlerin performansını dramatik şekilde artırır