İçeriğe atla

Kuyruk özyineleme

Bilgisayar biliminde, kuyruk özyineleme özel bir özyineleme çeşididir.

Tanımı

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

İş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

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

İlgili Araştırma Makaleleri

<span class="mw-page-title-main">C (programlama dili)</span> programlama dili

C, yapısal bir programlama dilidir. Bell Laboratuvarları'nda, Ken Thompson ve Dennis Ritchie tarafından UNIX işletim sistemini geliştirebilmek amacıyla B dilinden türetilmiştir. Geliştirilme tarihi 1972 olmasına rağmen yaygınlaşması Brian Kernighan ve Dennis M. Ritchie tarafından yayımlanan "C Programlama Dili" kitabından sonra hızlanmıştır. Günümüzde neredeyse tüm işletim sistemlerinin yapımında %95'lere varan oranda kullanılmış, hâlen daha sistem, sürücü yazılımı, işletim sistemi modülleri ve hız gereken her yerde kullanılan oldukça yaygın ve sınırları belirsiz oldukça keskin bir dildir. Keskinliği, programcıya sonsuz özgürlüğün yanında çok büyük hatalar yapabilme olanağı sağlamasıdır. Programlamanın gelişim süreciyle beraber programlamanın karmaşıklaşması, gereksinimlerin artması ile uygulama programlarında nesne yönelimliliğin ortaya çıkmasından sonra C programcıları büyük ölçüde nesne yönelimliliği destekleyen C++ diline geçmişlerdir.

Komut kümesi mimarisi, CPU'nun yazılım tarafından nasıl kontrol edileceğini tanımlayan bilgisayar soyut modelinin bir parçasıdır. ISA, işlemcinin ne yapabileceğini ve bunu nasıl yapacağını belirterek donanım ve yazılım arasında bir arayüz gibi davranır.

<span class="mw-page-title-main">Derleyici</span> kaynak kodunu bilgisayarın işleyebileceği koda dönüştüren program

Derleyici, kaynak kodu makine koduna dönüştüren yazılımdır. Bir programlama dilinin derleyicisi, o programlama dili kullanılarak yazılmış olan kodu hedef işlemci mimarisine göre uygun şekilde makine koduna derler ve genellikle çıktı olarak yürütülebilir dosyanın oluşturulmasını sağlar. Bu eyleme derleme denir. Bir başka ifadeyle derleyici, bir tür yazı işleyicidir; girdi olarak yazı alır ve çıktı olarak yazı verir.

<span class="mw-page-title-main">Büyük O gösterimi</span>

Büyük O (Big-Oh) gösterimi matematiksel bir gösterim olup işlevlerin (fonksiyonların) asimptotik davranışlarını tarif etmek için kullanılır. Bir işlevin büyümesinin asimptotik üst sınırını daha basit başka bir işlev cinsinden tanımlanması demektir. İki temel uygulama alanı vardır: matematik alanında genellikle kırpılmış bir sonsuz serinin kalan terimini karakterize etmek için kullanılır; bilgisayar bilimlerinde ise algoritmaların bilgi işlemsel karmaşıklığının çözümlemesi için kullanılır.

RSA, güvenliği tam sayıları çarpanlarına ayırmanın algoritmik zorluğuna dayanan bir tür açık anahtarlı şifreleme yöntemidir. 1978’de Ron Rivest, Adi Shamir ve Leonard Adleman tarafından bulunmuştur. Bir RSA kullanıcısı iki büyük asal sayının çarpımını üretir ve seçtiği diğer bir değerle birlikte ortak anahtar olarak ilan eder. Seçilen asal çarpanları ise saklar. Ortak anahtarı kullanan biri herhangi bir mesajı şifreleyebilir, ancak şu anki yöntemlerle eğer ortak anahtar yeterince büyükse sadece asal çarpanları bilen kişi bu mesajı çözebilir. RSA şifrelemeyi kırmanın çarpanlara ayırma problemini kırmak kadar zor olup olmadığı hala kesinleşmemiş bir problemdir.

Standart ML (SML), çok amaçlı işlevsel programlama dilidir. Çoğunlukla derleyici/yorumlayıcı yazımı ve teorem ispatlama konularında tercih edilir. ML ailesinin diğer fertleri gibi tür çıkarımı yeteneği ile ünlüdür. Ayrıca çok gelişmiş bir modül sistemine sahiptir.

<span class="mw-page-title-main">PageRank</span>

PageRank, Google tarafından geliştirilen ve web sayfalarının önemini belirlemek için kullanılan bir algoritmadır. İnternet üzerindeki bağlantıların analiz edilmesiyle hesaplanan Pagerank değeri Google Arama sonuçlarında sayfaların sıralanması için kullanılan faktörlerden biridir.

Veri yapısı, bilgisayar ortamında verilerin etkin olarak saklanması ve işlenmesi için kullanılan yapı.

<span class="mw-page-title-main">Özyineleme</span>

Özyineleme ya da yinelge, en genel anlamıyla bir yapının yinelenmesidir. Özellikle matematik ve bilgisayar biliminde kullanılır. Bu yapılara yinelgen yapılar denir. Yinelgen bir yapı eğer kendine gönderme yapma özelliğiyle yinelgen ise bu tür yapılara özgöndergeli ya da kendine-göndergeli yapılar denir.

<span class="mw-page-title-main">Birleştirmeli sıralama</span>

Birleşmeli Sıralama, bilgisayar bilimlerinde derecesinde karmaşıklığa sahip bir sıralama algoritmasıdır. Girdi olarak aldığı diziyi en küçük hale gelene kadar ikili gruplara böler ve karşılaştırma yöntemi kullanarak diziyi sıralar.

Sözde kod, bilgisayar bilimleri alanında algoritmalar ve programlar oluşturulurken ve aktarılırken kullanılan, günlük konuşma diline benzer ve belli bir programlama dilinin detaylarından uzak anlatımlardır. Programın yapısının ve çalışma mantığının yüksek seviyeli bir biçimde, gerektiği yerde doğrudan doğal dil cümleleriyle, ama yine de bir program yapısı ve akışı içinde anlatılmasıdır. Böylelikle sözde kodu okuyan ya da yazan birisi, programlama dillerinin sözdizim detaylarına dikkat etmek zorunda kalmadan, programın ve algoritmanın çalışma mantığını düşünebilir.

<span class="mw-page-title-main">Sıralama algoritması</span>

Sıralama algoritması, bilgisayar bilimlerinde ya da matematikte kullanılan, verilen bir listenin elemanlarını belirli bir sıraya sokan algoritmadır. En çok kullanılan sıralama türleri, sayı büyüklüğüne göre sıralama ve alfabetik sıralamadır. Sıralama işleminin verimli yapılması, arama ve birleştirme algoritmaları gibi çalışması için sıralanmış dizilere gereksinim duyan algoritmaların başarımının yüksek olması için önemlidir. Sıralama algoritmaları bilgisayarlarda tutulan verilerin düzenlenmesini ve insan kullanıcı tarafından daha rahat algılanmasını da sağlar.

Doğum günü akını, olasılık kuramındaki doğum günü probleminin ardındaki matematiği kullanan bir kriptografik akındır. Akının amacı bir f işlevine girdi olarak verilen ve 'nin koşulunu sağlamasıdır. Böyle bir ikilisi çakışma olarak adlandırılmaktadır. Çakışma bulma yöntemi, f işlevini gelişigüzel girdilerle hesaplayıp çakışma koşulunun sağlanıp sağlanmadığını incelemektir. Bu yöntem, yukarıda sözü edilen doğum günü probleminden yararlanır. Şöyle ki; bir işlevi eşit olasılıklı farklı sonuç üretiyorsa ve yeterince büyükse koşulunu sağlayan ve değerleri kolayca bulunabilir.

<span class="mw-page-title-main">Gustafson yasası</span>

Gustafson yasası, yeterince büyük bir sorunun verimli bir biçimde koşutlaştırılabileceğini öngören bir bilgisayar mühendisliği yasasıdır. 1988 yılında John L. Gustafson'un geliştirdiği bu kural, bir programın koşutluk derecesine bağlı olarak ne ölçüde hızlandırılabileceğini belirleyen Amdahl yasası ile yakından ilintilidir.

<span class="mw-page-title-main">Dijital İmza Algoritması</span>

Dijital İmza Algoritması dijital imza için bir FIPS standardıdır. Ağustos 1991'de National Institute of Standards and Technology (NIST) tarafından tasarlanmıştır. Dijital imza algoritması, ElGamal İmza Algoritması'nın bir varyantıdır.

<span class="mw-page-title-main">Kriptografik özet fonksiyonu</span>

Kriptografik özet fonksiyonu çeşitli güvenlik özelliklerini sağlayan bir özet fonksiyonudur. Veriyi belirli uzunlukta bir bit dizisine, (kriptografik) özet değerine, dönüştürür. Bu dönüşüm öyle olmalıdır ki verideki herhangi bir değişiklik özet değerini değiştirmelidir. Özetlenecek veri mesaj, özet değeri ise mesaj özeti veya kısaca özet olarak da adlandırılır.

Medyan bir anakütle ya da örneklem veri serisini küçükten büyüğe doğru sıraladığımızda, seriyi ortadan ikiye ayıran değere denir. İstatistiğin bir alt dalı olan betimsel istatistikde medyan bir merkezsel konum ölçüsü kabul edilir.

<span class="mw-page-title-main">Ayrıştırıcı (yazılım)</span>

Ayrıştırıcı, girdi verilerini alır ve girdinin yapısal bir temsilini vererek, süreçte doğru sözdizimini kontrol eden bir veri yapısı oluşturan bir yazılım bileşenidir. Ayrıştırma öncesinde veya sonrasında başka adımlar izlenebilir veya bunlar tek bir adımda birleştirilebilir. Ayrıştırıcı, genelde girilen karakter dizisinden belirteçler oluşturan ayrı bir sözcük tabanlı analiz motorunu takip eder. Ayrıştırıcılar elle programlanabilir veya bir ayrıştırıcı üreteci tarafından otomatik olarak veya yarı otomatik olarak oluşturulabilir. Ayrıştırma, biçimlendirilmiş çıktı üretimlerini tek bir şablonda tamamlama görevi görür. Bunlar, farklı etki alanlarına uygulanabilir, ancak bir derleyicinin girdi ve çıktı aşamaları gibi genellikle bir arada sunulur.

Bilgisayar bilimi, matematik, ekonomi ve biyoinformatikte dinamik programlama karmaşık bir problemi tekrarlanan alt problemlere bölerek, her bir alt problemi yalnız bir kere çözüp daha sonra bu çözümü kaydederek karmaşık problemin çözümünde kullanma yöntemidir. Bir alt problem çözüldükten sonra tekrar çözülmesi gerektiğinde daha önce kaydedilen çözüm kullanılarak zaman kazanılır, ancak alt problemlerin kaydedileceği daha fazla alana gereksinim duyulur. Yani dinamik programlama algoritmaları alandan ödün verilerek zamandan kazanılmasını sağlar. Dinamik programlama algoritmaları optimizasyon problemlerinin çözümünde yaygın olarak kullanılır.

<span class="mw-page-title-main">FIFO algoritması</span>

FIFO algoritmasının mantığı basittir. Bellek yöneticisinin yeni bir sayfaya yer açmak için, hangi sayfayı dışarıda bırakacağını karar veren algoritmalardan biridir. Yönlendiriciye gelen ilk paket, iletilecek ilk pakettir.