Özyineleme, aslında kelime olarak incelense bile anlamı ortaya çıkacaktır. Öz – Yineleme yani kendi kendini – yenileme ÅŸeklinde ayrı bir ÅŸekilde yazıldığında anlaşılacaktır.
Özyineleme (Yinelge – Recursion), en genel manasıyla bir yapının (kendi kendine) yinelenmesi olayıdır. Genel anlamda kullanımı daha çok matematik ve bilgisayar biliminde yapılmaktadır. Bu yapılara “Yinelgen” yapılar ismi verilmektedir. Yinelgen bir yapı eÄŸer kendine gönderme yapma (atfıta bulunma) özelliÄŸiyle yinelgen ise bu tür yapılara “Özgöndergeli” veya “Kendine-Göndergeli” yapılar denir.
Özyineleme (Yinelge – Recursion) için ortaya çıkan bir problemi çözmek için, bir yöntemin kendisini çağırdığı bir programlama tekniÄŸi ÅŸeklinde bir açıklamada yapabiliriz. Ayrıca kendisi için gerçekleÅŸtirilen bir çaÄŸrının belirli konudaki bir problemi çözmesi olarak da tanımlanabilir.
Özyineleme (Yinelge – Recursion), nesnenin kendisini içermesi veya kendi kendisi tarafından tanımlanmasıdır.
Özyineleme (Yinelge – Recursion), doÄŸru bir ÅŸekilde kullanıldığı zaman ortada bulunan problemlere zarif çözümler sunabilen bir programlama tekniÄŸidir.
Kullanımı, programlama kodunu ve okunabilirliğini bazı durumlar için basit hale dönüştürür. Bu programlama teknikleri ekseriyetle kodun okunulabilirliğini artırır.
Özyineleme – Örnek
Aşağıda bir Fibonacci sayı dizisinin bazı elemanlarını görüyorsunuz.
- Fibonacci Dizisi; Her sayının kendinden öncekiyle toplanması sonucu oluşan bir sayı dizisidir.
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
Verilen bir Fibonacci dizisinin her elemanı iki önceki elemanın toplamından meydana gelmektedir. Birinci ve ikinci elemanlar tanım gereği 1 değerini alırken, diğer elemanların diziliş kuralı aşağıda verilmiştir:
Tanıma göre n’inci elemanın hesaplanması için aşağıdaki özyineleme metodunu kullanırız:
Bu örnek bir çözümün uygulanması için özyineleme metotunun nasıl kullanılacağını gösteriyor. Diğer taraftan, özyineleme ile programlama yaparken sezgisel olmalısınız, çünkü programın verimliği ve hızını etkileyen pek çok faktör vardır.
Doğal Sayılar
Gerçek manada incelendiği zaman matematikte yalnızca göndermeler değil, kümeler dahil çok sayıda kavramın yinelgen olarak tanımı yapılabilir. Örneğin doğal sayılar kümesi aşağıdaki iki özelliği sağlayan en küçük kümedir:
- 0 bir doğal sayıdır.
- n bir doğal sayı ise n+1 bir doğal sayıdır.
Tümevarım
Yaygın bir matematiksel kanıt türü olan tümevarım genellikle yinelgeye baş vurur.
Örneğin Osman soyundan gelenlerin insan olduğu iki temel varsayım ile ispatlanabilir.
Varsayım 1: Osman insandır.
Varsayım 2: İnsanın çocuğu insandır.
İddia: x, Osman soyundan geliyor ise insandır.
İspat:
Varsayım 1 : Temel durum: x, Osman ise insandır
Varsayım 2 : Tümevarım adımı: {\displaystyle x}’in ebeveyni Osman ise temel durum ve Varsayım 2’ye göre kendisi de insandır.
x, Osman soyundan geliyor fakat {\displaystyle x}’in ebeveyni Osman deÄŸilse, {\displaystyle x}’in ebeveyni Osman soyundan geliyordur ve İddiaya göre ebeveyni insandır.
Bu durumda Varsayım 2’ye göre x de insandır.
Kendi kendine atıfta bulunan bu ispat biçimi, temel durum dışında ki her durum için bir önceki durumun doğru olduğunu kabul etmektedir.
ÖrneÄŸin {\displaystyle Osman}’ın torunu {\displaystyle Osman}’ın çocuÄŸu insan olduÄŸu için insandır. {\displaystyle Osman}’ın çocuÄŸu ise Osman insan olduÄŸu için insandır.
Herhangi bir nesilden bu ÅŸekilde geriye gidilebilir.
Bilgisayar programlarında yinelgen yapılar
İşlev Tanımlama
Matematikte açıklanan duruma benzer biçimde, işlevlerin yinelgen olarak tanımı yapılabilir.
ÖrneÄŸin iÅŸlevsel bir programlama dili olan Common Lisp’te faktöriyel iÅŸlevi aÅŸağıdaki gibi tanımlanabilir:
(defun fak(n) (if (<= n 1) 1 (* n (fak (- n 1))))) Ya da daha yaygın olarak kullanılan C dilinde;
int fak(int n) { if (n<=1) return 1; return n*fak(n-1); }
Church tezine göre hesaplanabilir bütün işlevler, yinelgen işlevler ile ifade edilebilir.
Veri Türleri
Bazı programlama dilleri, yinelgen veri türlerine izin verir. AÅŸağıdaki betik parçası, Ocaml’de doÄŸal sayı veri tipini tanımlamaktadır:
type dogal = SIFIR | SONRAKI of dogal
Kaynak :Â
Wikipedia
By Kaynuka