İçeriğe atla

Özyineleme

Karatsuba algoritmasının bir adımının ve bu adımların özyinelemeli olarak oluşturduğu işlem ağacının şematik gösterimi.

Özyineleme ya da yinelge, en genel anlamıyla bir yapının (kendi kendine) 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 (atıfta bulunma) özelliğiyle yinelgen ise bu tür yapılara özgöndergeli ya da kendine-göndergeli yapılar denir.

Matematik ve mantıkta yinelgen yapılar

Yinelgen göndermeler (fonksiyonlar)

Matematiksel göndermeler (fonksiyonlar) yinelgen olarak tanımlanabilir. Örneğin doğal sayılarda tanımlı faktöriyel (çarpansal) göndermesi:

Doğal sayılar

Aslında matematikte sadece göndermeler değil, kümeler dahil birçok kavram yinelgen olarak tanımlananır. Örneğin doğal sayılar kümesi aşağıdaki iki özelliği sağlayan en küçük kümedir:

  1. 0 bir doğal sayıdır.
  2. n bir doğal sayı ise n+1 bir doğal sayıdır.

Tümevarım

Yaygın bir matematiksel kanıt çeşidi olan tümevarım çoğu zaman 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:
Temel durum: x, Osman ise insandır (Varsayım 1).
Tümevarım adımı: 'in ebeveyni Osman ise temel durum ve Varsayım 2'ye göre kendisi de insandır. x, Osman soyundan geliyor fakat 'in ebeveyni Osman değilse, '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 'ın torunu 'ın çocuğu insan olduğu için insandır. 'ı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

Matematiktekine benzer şekilde, işlevler yinelgen olarak 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, 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

Ayrıca doğal ve yapay dillerin sözdizimleri ve dilbilgileri de yinelgen tanımlanabilir.

İlgili Araştırma Makaleleri

<span class="mw-page-title-main">Tam sayı</span> sıfırın sağında bulunan sayılar büyükken solunda bulunan sayılar küçüktür

Tam sayılar, sayılar kümesinde yer alan sıfır (0), pozitif yönde yer alan doğal sayılar ve bunların negatif değerlerinden oluşan negatif sayılardan oluşan sayı kümesidir.

<span class="mw-page-title-main">Doğal sayılar</span> sayma sayıları kümesine 0ın eklenmesiyle oluşan sayılar kümesi

Doğal sayılar, şeklinde sıralanan tam sayılardır ve kimi tanımlamalara göre 0 sayısı da bu kümeye dâhil edilebilir. Aralarında standart ISO 80000-2'nin de bulunduğu bazı tanımlar doğal sayıları 0 ile başlatır ve bu durum negatif olmayan tam sayılar için 0, 1, 2, 3, ... şeklinde bir karşılık bulurken, bazı tanımlamalar 1 ile başlamakta ve bu da pozitif tam sayılar için 1, 2, 3, ... şeklinde bir eşlenik oluşturur. Doğal sayıları sıfır olmadan ele alan metinlerde, sıfırın da dahil edildiği doğal sayılar bazen tam sayılar olarak adlandırılırken diğer bazı metinlerde bu terim, negatif tam sayılar da dahil olmak üzere tam sayılar için kullanılmaktadır. Özellikle ilkokul seviyesindeki eğitimde, doğal sayılar, negatif tam sayıları ve sıfırı dışlamak ve saymanın ayrık yapısını, gerçek sayıların bir karakteristiği olan ölçümün sürekliliğiyle karşıtlık oluşturmak amacıyla sayma sayıları olarak adlandırılabilir.

<span class="mw-page-title-main">Asal sayı</span> sadece iki pozitif tam sayı böleni olan doğal sayılardır

Bir asal sayı, yalnızca 1'den büyük olup kendisinden küçük iki doğal sayının çarpımı olarak ifade edilemeyen bir doğal sayıdır. 1'den büyük ve asal olmayan doğal sayılara bileşik sayı adı verilir. Örneğin, 5 bir asal sayıdır çünkü onu bir çarpım olarak ifade etmenin mümkün olan yolları, 1 × 5 veya 5 × 1, yalnızca 5 sayısını içermektedir. Ancak, 4 bir bileşik sayıdır çünkü bu, her iki sayının da 4'ten küçük olduğu bir çarpım şeklindedir. Asal sayılar, aritmetiğin temel teoreminden ötürü sayı teorisi alanında merkezi öneme sahiptir: 1'den büyük her doğal sayı, ya bir asal sayıdır ya da asal sayıların çarpımı olarak, sıralamalarından bağımsız bir şekilde, benzersiz olarak çarpanlarına ayrılabilir.

Fonksiyon, matematikte değişken sayıları girdi olarak kabul edip bunlardan bir çıktı sayısı oluşmasını sağlayan kurallardır. Fonksiyon, 17. yüzyılda matematiğin kavramlarından biri olmuştur. Fizik, mühendislik, mimarlık ve birçok alanda kullanılmaktadır. Galile, Kepler ve Newton hareketlerin araştırılmasında, zaman ve mesafe arasındaki durumu incelemek için fonksiyonlardan faydalanmıştır. Dört işlemden sonra gelen bir işlem türüdür.

Bileşik sayı, en az iki asal sayının çarpımı olarak yazılabilen pozitif tam sayıdır.

14 = 1 x 14 = 2 x 7.

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

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.

Faktöriyel, matematikte, sağına ünlem işareti konulmuş sayıya verilen isim, daha genel olan Gama fonksiyonunun tam sayılarla sınırlanmış özel bir durumudur. Bu sınırlamanın nedeni gerçek veya reel sayılarda bu hesabın imkansız oluşudur. 1'den başlayarak belirli bir sayma sayısına kadar olan sayıların çarpımına o sayının faktöriyeli denir. Basit bir şekilde faktöriyel, n tane ayrık elemanın kaç farklı şekilde sıralanabileceğidir.

<span class="mw-page-title-main">Matris (matematik)</span>

Matematikte matris veya dizey, dikdörtgen bir sayılar tablosu veya daha genel bir açıklamayla, toplanabilir veya çarpılabilir soyut miktarlar tablosudur. Dizeyler daha çok doğrusal denklemleri tanımlamak, doğrusal dönüşümlerde çarpanların takibi ve iki parametreye bağlı verilerin kaydedilmesi amacıyla kullanılırlar. Dizeylerin toplanabilir, çıkartılabilir, çarpılabilir, bölünebilir ve ayrıştırılabilir olmaları, doğrusal cebir ve dizey kuramının temel kavramı olmalarını sağlamıştır.

<span class="mw-page-title-main">Dizi</span> aynı tip elemanların sıralı listesi (sonlu veya sonsuz)

Dizi, bir sıralı listedir. Bir küme gibi, ögelerden oluşur. Sıralı ögelerin sayısına dizinin uzunluğu denir. Kümenin aksine sıralı ve aynı ögeler dizide farklı konumlarda birkaç kez bulunabilir. Tam olarak bir dizi, tanım kümesi sayılabilen toplam sıralı kümelerden oluşan bir fonksiyon olarak tanımlanabilir. Örneğin doğal sayılar gibi. Diziler bu örnekte olduğu gibi sonlu olabilir. Ya da tüm çift pozitif tam sayılar gibi sonsuz olabilir.

Cisim, halka ve grup gibi soyut bir cebirsel yapıdır. Kabaca, elemanları arasında toplama, çıkarma, çarpma ve bölme yapılabilen ve bu işlemlerde sayılardan alışık olduğumuz temel aritmetik kurallarının geçerli olduğu bir küme olarak tanımlanabilir.

Vektör uzayı veya Yöney uzayı, matematikte ölçeklenebilir ve eklenebilir bir nesnelerin (vektörlerin) uzayına verilen isimdir. Daha resmî bir tanımla, bir vektör uzayı, iki elemanı arasında vektör toplamasının ve skaler denilen sayılarla çarpımın tanımlı olduğu ve bunların bazı aksiyomları sağladığı kümedir. Skalerler, rasyonal veya reel sayılar kümesinden gelebilir, ama herhangi bir cisim üzerinden bir vektör uzayı oluşturmak mümkündür. Vektör uzayları, skalerlerin geldiği cisime göre reel vektör uzayı, kompleks vektör uzayı veya genel bir cisim üzerinden K vektör uzayı şeklinde adlandırılır.

<span class="mw-page-title-main">Cebirsel sayılar</span>

Cebirsel sayılar, rasyonel katsayıları olan tek değişkenli sıfırdan farklı bir polinomun kökü olarak ifade edilebilen sayılardır. Mesela, altın oran, , cebirsel bir sayı örneğidir çünkü x2x − 1 polinomunun bir köküdür. Bu durumda, söz konusu polinomun değerinin sıfıra eşitlendiği x değeridir. Diğer bir örnek olarak, biçimindeki karmaşık sayı, x4 + 4 polinomunun bir kökü olduğundan dolayı cebirsel sayı olarak kabul edilir.

Matematikte Cauchy çarpımı, ve gibi iki dizinin

<span class="mw-page-title-main">Riemann zeta işlevi</span>

Matematikte Riemann zeta işlevi , Alman matematikçi Bernhard Riemann tarafından 1859'da bulunmuş olan ve asal sayıların dağılımıyla olan ilişkisinden ötürü sayı kuramında önemli yeri bulunan seçkin bir işlevdir. İşlev; fizik, olasılık kuramı ve uygulamalı istatistikte de kullanılmaktadır.

<span class="mw-page-title-main">Hilbert uzayı</span>

Matematikte Hilbert uzayı, sonlu boyutlu Öklit uzayında uygulanabilen lineer cebir yöntemlerinin genelleştirilebildiği ve sonsuz boyutlu da olabilen bir vektör uzayıdır. Daha kesin olarak, bir Hilbert uzayı, uzayın tam metrik uzay olmasını sağlayan bir uzaklık fonksiyonu üreten bir iç çarpımla donatılmış bir vektör uzayıdır. Bir Hilbert uzayı, bir Banach uzayının özel bir durumudur. Matematik, fizik ve mühendislikte sıkça kullanılmaktadır. Kuantum mekaniğiyle uyumludur. Adını David Hilbert'ten almaktadır.

<span class="mw-page-title-main">Öklid uzayı</span> Öklid geometrisinin yüksek boyutlu vektör uzaylarına genelleştirilmesi

Matematikte Öklid uzayı, Öklid geometrisinin üç boyutlu uzayıdır ve bu kavramlar, çok boyutlu olarak genelleştirilir. “Öklid” terimi bu uzayları, Öklid geometrisi olmayan eğimli uzaydan ve Einstein'nın genel görelilik kuramından ayırt eder. Bu adı Yunan matematikçi Öklid'den dolayı almıştır.

<span class="mw-page-title-main">Parametre</span> belirli bir sistemi tanımlamak veya sınıflandırmak için yardımcı olabilecek herhangi bir özellik

Parametre belirli bir sistemi tanımlamak veya sınıflandırmak için yardımcı olabilecek herhangi bir özellik. Parametre, sistemi tanımlarken veya performansını, durumunu değerlendirirken yararlı veya kritik olan bir sistem unsurudur.

<span class="mw-page-title-main">Rastgele yürüyüş</span>

Rastgele yürüyüş (ya da rassal yürüyüş) matematiksel bir nesne olup, bir stokastik veya rastgele süreç olarak bilinir. Bu süreç, herhangi bir matematiksel uzayda –örneğin tamsayılar uzayı–atılan rastgele adımların toplamından oluşan patikayı tanımlamaya yöneliktir. Örneğin, bir molekülün sıvı veya gaz içerisinde izlediği yol, hayvanların yem arayışında takip ettiği patika, değişkenlik gösteren hisse fiyatları ve de bir borsa oyuncusunun finansal durumu rastgele yürüyüş modelleri ile tahmin edilebilir; ancak gerçekte tamamen rastlantısal olmama ihtimalleri de vardır. Bu örneklerin de gösterdiği gibi, rastgele yürüyüş modelinin birçok bilim dalında uygulama alanı mevcuttur; ekoloji, psikoloji, bilgisayar bilimleri, fizik, kimya, biyoloji ve ekonomi bunlara örnektir.

Süperfaktöriyel, sembolü ‼ olan özel tanımlı bir matematiksel fonksiyondur. Matematikte, süperfaktöriyelin birden fazla tanımı vardır.