Kuyruk özyineleme
 | Bu madde, öksüz maddedir; zira herhangi bir maddeden bu maddeye verilmiş bir bağlantı yoktur. (Eylül 2022) |
 | Bu madde hiçbir kaynak içermemektedir. (Ekim 2016) (Bu şablonun nasıl ve ne zaman kaldırılması gerektiğini öğrenin) |
Bilgisayar biliminde, kuyruk özyineleme özel bir özyineleme çeşididir.
Tanımı
[değiştir | kaynağı değiştir]Bir işlevin döndüreceği değer, doğrudan çağırdığı işlevin döndüreceği değere eşitse buna kuyruk özyineleme denir. Konu özyineleme ile sınırlı olmasa da, özyineleme sırasında işlev çağırma miktarının çokluğu nedeniyle önem kazanır.
Önemi
[değiştir | kaynağı değiştir]İşlev çağırma, dolayısıyla özyineleme göreceli olarak pahalı bir iştir. Bunun sebebi işlevlerin çağrılması ve sonlanması arasında yığından (stack) ve muhtemelen öbekten (heap) yer tüketmesidir. Özyineleme sırasında çağrılan işlev, kendi içinden çağrılan bütün işlevlerin bitmesini beklemektedir. Bu zincir yapı algoritma ve girdiye bağlı olarak çok uzayabilir. Bu durumda eşdeğer döngüsel algoritmadan yavaş olacağı gibi, fazla hafıza tüketimi nedeniyle hesaplama bitmeden sonlandırılabilir.
Eğer özyineleme kuyruk yapısındaysa, derleyici ya da yorumlayıcı çalışma zamanında yığının büyümesini engelleyebilir. Bunun sebebi, artık işlevin yığında yer kaplamasına gerek kalmaması ve kendisini çağıran işleve değer olarak doğrudan kendi çağırdığı işlevin çıktısının döndürülebilmesidir. Bu tarz eniyileme işlemleri her derleyici tarafından gerçekleştirilmese de özellikle yaygın işlevsel dillerin derleyicileri tarafından gerçekleştirilir.
Örnekler
[değiştir | kaynağı değiştir]Faktöriyel işlevi basit olarak Standart ML'de şu şekilde tanımlanabilir:
fun fak 0 = 1 | fak n = n * fak(n - 1)
Özyinelemenin gerçekleştiği n0 durumunda döndürülen değer n*fak(n-1) olduğundan bu kod kuyruk özyineleme yapısında değildir.
Öte yandan ikinci bir işlev (fak2) sayesinde bu kod kolaylıkla kuyruk yapıya çevirilebilir;
fun fak n =
let
fun fak2 0 p = p
| fak2 m p = fak2 (m-1) (p * m)
in
fak2 n 1
end