Dart Recursion (Özyineleme)

Recursion, bir fonksiyonun kendi kendini çağırması ile çalışan bir problem çözme tekniğidir.

Temel Kavram

void geriSay(int n) {
  if (n <= 0) {
    print("Bitti!");
    return;
  }
  print(n);
  geriSay(n - 1); // fonksiyon kendini çağırıyor
}

void main() {
  geriSay(5);
}

Çıktı:

5 4 3 2 1 Bitti!

Her recursive (özyinelemeli) fonksiyonun iki temel parçası olmalıdır:

Base case (taban durumu): Fonksiyonun kendini çağırmayı durdurduğu koşul. Yukarıdaki örnekte n <= 0 durumu budur. Recursive case (özyinelemeli durum): Fonksiyonun kendini, problemi biraz daha "küçültülmüş" bir haliyle tekrar çağırdığı kısım. Yukarıda geriSay(n - 1) budur.

Base case olmadan ne olur?

void sonsuzGeriSay(int n) {
  print(n);
  sonsuzGeriSay(n - 1); // base case yok — asla durmaz!
}

Bu fonksiyon, base case olmadığı için sonsuza kadar kendini çağırmaya devam eder. Pratikte bu, Stack Overflow hatasıyla sonuçlanır — çünkü her fonksiyon çağrısı, bellekte bir "çağrı yığını" (call stack) katmanı oluşturur ve bu yığın sonsuza kadar büyüyemez, bir noktada bellek sınırına ulaşılır ve program çöker.

Klasik Örnek: Faktöriyel

Faktöriyel (n!), recursion'ı öğretmek için en sık kullanılan matematiksel örnektir: 5! = 5 4 3 2 1 = 120

int faktoriyel(int n) {
  if (n <= 1) return 1; // base case
  return n * faktoriyel(n - 1); // recursive case
}

void main() {
  print(faktoriyel(5)); // 120
}

Bu nasıl çalışıyor, adım adım görelim:

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))) = 5 (4 (3 2)) = 5 (4 6) = 5 24 = 120

Fonksiyon, önce en küçük probleme (faktoriyel(1)) inene kadar kendini çağırır, sonra o sonuçlar geri "yukarı doğru" katlanarak nihai sonuca ulaşır. Bu, recursion'ın karakteristik özelliğidir — problem, kendine benzer ama daha küçük alt problemlere bölünür.

Recursion vs Döngü (Iteration) — Aynı İşi Yapmanın İki Yolu

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

// Iterative (döngü ile) versiyon
int faktoriyelIterative(int n) {
  int sonuc = 1;
  for (int i = 2; i <= n; i++) {
    sonuc *= i;
  }
  return sonuc;
}

void main() {
  print(faktoriyelRecursive(5)); // 120
  print(faktoriyelIterative(5)); // 120 — aynı sonuç
}

Hangisi daha iyi? Bu duruma göre değişir:

Recursion, problemi doğal olarak kendine benzer alt problemlere bölen durumlarda (ağaç yapıları, iç içe geçmiş veri, matematiksel tanımı zaten recursive olan problemler — faktöriyel, Fibonacci gibi) genelde daha okunabilir ve zarif bir çözüm sunar. Döngü (iteration), genelde daha performanslıdır — çünkü her recursive çağrı, bellekte ekstra bir "çağrı yığını" katmanı oluşturur (fonksiyon çağırma maliyeti + bellek kullanımı), döngüde ise böyle bir ek yük yoktur.

Pratik tavsiye: Basit, doğrusal problemlerde (bir listeyi toplama, sayma gibi) döngü kullan. Problem doğası gereği "kendine benzer parçalara bölünüyorsa" (ağaç dolaşma, böl-ve-fethet algoritmaları gibi) recursion çok daha temiz bir çözüm sunar.

Başka Bir Klasik Örnek: Fibonacci Serisi

int fibonacci(int n) {
  if (n <= 1) return n; // base case: fib(0)=0, fib(1)=1
  return fibonacci(n - 1) + fibonacci(n - 2); // recursive case
}

void main() {
  for (int i = 0; i < 8; i++) {
    print(fibonacci(i)); // 0, 1, 1, 2, 3, 5, 8, 13
  }
}

Fibonacci serisinde her sayı, kendinden önceki iki sayının toplamıdır — bu tanım zaten doğal olarak recursive'dir, bu yüzden kod da matematiksel tanıma neredeyse birebir uyuyor. Ama dikkat: bu naif Fibonacci implementasyonu, büyük n değerlerinde çok yavaştır çünkü aynı alt problemleri defalarca tekrar hesaplar (örneğin fibonacci(5), fibonacci(3)'ü birden fazla kez hesaplar). Bu performans sorununu çözmenin yolları (memoization gibi) daha ileri bir konu — şimdilik sadece bu tuzağın var olduğunu bilmen yeterli.

Recursive Fonksiyonlarda Koleksiyonlarla Çalışma

int listeToplami(List<int> liste) {
  if (liste.isEmpty) return 0; // base case: boş liste
  return liste.first + listeToplami(liste.sublist(1)); // ilk eleman + kalanının toplamı
}

void main() {
  print(listeToplami([1, 2, 3, 4, 5])); // 15
}

liste.sublist(1), listenin ilk elemanı hariç geri kalanını yeni bir liste olarak döndürür. Bu örnek, "problemi küçültme" mantığının koleksiyonlarda nasıl işlediğini gösteriyor — her çağrıda liste bir eleman küçülür, ta ki boş listeye (base case) ulaşana kadar.

Bunu pratikte genelde .reduce() veya .fold() gibi metodlarla (Bölüm 11'de göreceğiz) yaparız çünkü onlar hem daha performanslı hem de daha yaygın kullanılan bir yaklaşımdır — ama recursion mantığını anlamak için bu örnek faydalı.

Ne Zaman Recursion Kullanmalı?

İyi kullanım alanları:

Ağaç/graf yapılarında dolaşma (örneğin bir dosya sisteminin tüm alt klasörlerini gezmek) Böl-ve-fethet algoritmaları (binary search, merge sort gibi — Bölüm 13'te veya ileri konularda karşına çıkabilir) Matematiksel olarak doğası gereği recursive tanımlanan problemler

Dikkatli olunması gereken durumlar:

Çok derin recursion (binlerce seviye), stack overflow riski taşır Basit doğrusal problemler için gereksiz karmaşıklık katabilir — döngü yeterliyse döngü kullan

🎯 Bu Dersten Çıkarılması Gerekenler Recursion, bir fonksiyonun kendini çağırmasıdır; her recursive fonksiyonda base case ve recursive case olmalıdır.

Base case olmadan (veya yanlış tanımlandığında) sonsuz özyineleme oluşur ve Stack Overflow hatası alınır.

Recursion, problemi kendine benzer küçük alt problemlere bölen durumlarda okunabilirlik açısından üstündür.

Döngü (iteration), genelde daha performanslıdır; basit doğrusal problemlerde tercih edilmelidir.

Naif recursive çözümler (örn. Fibonacci) bazı durumlarda tekrarlı hesaplamalar yüzünden verimsiz olabilir.