Özyineleme
Vikipedi, özgür ansiklopedi
Özyineleme, en genel anlamıyla bir yapının kendi kendine atıfta bulunmasıdır. Özellikle matematik ve bilgisayar biliminde kullanılır.
Konu başlıkları |
[değiştir] Matematik ve mantıkta özyineleme
[değiştir] İşlev tanımlama
Matematiksel işlevler özyineleme ile tanımlanabilir. Örneğin doğal sayılarda tanımlı faktöriyel işlevi:
Aslında matematikte sadece işlevler değil, kümeler dahil birçok kavram özyineleme ile tanımlananır. Ö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.
[değiştir] Tümevarım ile ispat
Yaygın bir matematiksel ispat çeşidi olan tümevarım çoğu zaman özyinelemeye 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:
- Temel durum: x, Osman ise insandır (Varsayım 1).
- Tümevarım adımı: x'in ebeveyni Osman ise temel durum ve Varsayım 2'ye göre kendisi de insandır. x, Osman soyundan geliyor fakat x'in ebeveyni Osman değilse, 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 şekli, temel durum haricindeki her durum için bir önceki durumun doğru olduğunu kabul etmektedir. Örneğin Osman'ın torunu Osman'ın çocuğu insan olduğu için insandır. Osman'ın çocuğu ise Osman insan olduğu için insandır. Herhangi bir nesilden bu şekilde geriye gidilebilir.
[değiştir] Bilgisayar programlarında özyineleme
[değiştir] İşlev tanımlama
Matematiktekine benzer şekilde, işlevler özyineleme ile tanımlanabilir. Ö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, özyinelemeli işlevler ile ifade edilebilir.
[değiştir] Veri türleri
Bazı programlama dilleri, özyinelemeli veri türlerine izin verir. Aşağıdaki kod parçası, Ocaml'de doğal sayı veri tipini tanımlamaktadır:
type dogal = SIFIR | SONRAKI of dogal
Ayrıca doğal ve yapay dillerin sözdizimleri ve gramerleri de özyinelemeli tanımlanabilir.


