Kitap 01 · Programlamanın TemelleriSayfa 42 / 56

Özyineleme

İngilizcesi: Recursion
Türkçe karşılığı: rekürsiyon
Okunuşu: rikörjın ya da rikörşın

Günlük kullanımda iki ad da yaygın.

Güncellendi 29 Eylül 20262 dk okuma

Kısaca

Özyineleme, bir fonksiyonun sorunu, basit bir temel duruma ulaşana dek aynı sorunun daha küçük sürümleri için kendisini çağırarak çözdüğü tekniktir.

Özyineleme nedir?

Özyineleme, bir fonksiyonun kendi kendini çağırmasıdır. Her çağrı asıl sorunun daha küçük ya da daha basit bir parçası üzerinde çalışır ve sonuçlar birleştirilerek nihai yanıt oluşturulur. Kendi küçük kopyaları cinsinden tanımlanan sorunlara doğal olarak uyar.

Her özyinelemeli fonksiyonun iki parçası olmalıdır. Temel durum (base case), fonksiyonun kendini tekrar çağırmadan doğrudan yanıtlayabildiği basit bir durumdur. Özyinelemeli durum ise sorunu parçalar ve her seferinde temel duruma biraz daha yaklaşarak fonksiyonu yeniden çağırır. Temel durum olmazsa fonksiyon, program çökene dek kendini çağırmaya devam eder.

Rus matruşka bebekleri özyineleme için yaygın bir benzetmedir: en küçük bebeğe ulaşmak için bir bebeği açarsınız, sonra içindeki bebeğe de aynısını yaparsınız; açacak bir şey kalmayana dek. Yazılımda özyineleme, diskteki klasörler, DOM ya da iç içe JSON gibi ağaç biçimli verileri gezmek için ve birleştirme sıralaması (merge sort) ile hızlı sıralama (quicksort) gibi algoritmalarda yaygın olarak kullanılır.

Özyineleme sıklıkla, adımları for ve while gibi döngülerle tekrarlayan yinelemeyle (iteration) karşılaştırılır. Özyinelemeli yazılan her şey bir döngüyle de yazılabilir ve döngüler genellikle bellek açısından daha verimlidir; çünkü her özyinelemeli çağrı çağrı yığınında (call stack) yer kaplar. Özyineleme çok derine inerse program yığın taşması (stack overflow) hatasıyla başarısız olabilir.

Bir bakışta

Her çağrı daha küçük bir çağrıyı bekler. Temel durum inişi durdurur, sonuçlar da geri dönüş yolunda çarpılır.

Önemli noktalar

Özyinelemeli bir fonksiyon, sorunun daha küçük bir sürümü için kendini çağırır.
Özyinelemeyi durduran bir temel durum içermelidir.
Her çağrı çağrı yığınında yer kaplar; çok derin özyineleme yığın taşmasına yol açabilir.
Ağaçlara, iç içe verilere ve böl ve yönet (divide-and-conquer) algoritmalarına çok uygundur.

Örnek

Faktöriyeli özyinelemeyle hesaplamakjavascript

// Factorial: 5! = 5 * 4 * 3 * 2 * 1
function factorial(n) {
  if (n <= 1) return 1;        // base case: stop here
  return n * factorial(n - 1); // recursive case: a smaller problem
}

console.log(factorial(5)); // 120

Sık sorulan sorular

Özyinelemede temel durum (base case) nedir?

Temel durum, özyinelemeli bir fonksiyonun kendini tekrar çağırmak yerine sonucu doğrudan döndürdüğü koşuldur. Özyinelemenin sonsuza dek sürmesini engelleyen şey budur.

Özyineleme ile yineleme (iteration) arasındaki fark nedir?

Özyineleme, bir fonksiyonun kendini çağırmasıyla sorunu çözer; yineleme ise adımları bir döngüyle tekrarlar. İkisi de aynı sorunları çözebilir; özyineleme iç içe yapılar için çoğu zaman daha açıktır, döngüler ise genellikle daha az bellek kullanır.

Özyinelemede yığın taşmasına (stack overflow) ne yol açar?

Her fonksiyon çağrısı, bitene kadar çağrı yığınında tutulur. Özyinelemenin temel durumu yoksa ya da çok derine iniyorsa yığında yer kalmaz ve program, JavaScript'te RangeError: Maximum call stack size exceeded gibi bir hata verir.

İlgili sayfalar

Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin