özyineleme - Recursion

Droste etkisi olarak bilinen görsel bir özyineleme biçimi . Bu görüntüdeki kadın, aynı nesneyi tutarken daha küçük bir görüntüsünü içeren bir nesneyi tutar, bu da aynı nesneyi tutarken daha küçük bir görüntüsünü içerir vb. 1904 Droste kakao tenekesi, Jan Misset tarafından tasarlandı

Özyineleme (sıfat: özyineleme ), bir şey kendisi veya türü açısından tanımlandığında ortaya çıkar. Özyineleme arasında değişen çeşitli disiplinler kullanılan dilbilim için mantık . Özyinelemenin en yaygın uygulaması, tanımlanan bir işlevin kendi tanımı içinde uygulandığı matematik ve bilgisayar bilimleridir . Bu görünüşte sonsuz sayıda örneği (işlev değerleri) tanımlarken, genellikle sonsuz döngü veya sonsuz referans zinciri oluşmayacak şekilde yapılır.

Resmi tanımlar

Ouroboros , kendi kuyruğunu yiyen bir yılan veya ejderhayı betimleyen eski bir sembol.

Matematik ve bilgisayar bilimlerinde, bir nesne veya yöntem sınıfı, iki özellikle tanımlanabildiğinde özyinelemeli davranış sergiler:

  • Basit bir temel durum (veya durumlar) — bir cevap üretmek için özyinelemeyi kullanmayan bir sonlandırma senaryosu
  • Bir özyinelemeli adım - baz durumda doğru tüm ardışık durumları azaltır kurallar kümesi.

Örneğin, aşağıda bir kişinin atasının özyinelemeli bir tanımı verilmiştir . Birinin atası ya:

  • Birinin ebeveyni ( temel durum ) veya
  • Birinin ebeveyninin atası ( yinelemeli adım ).

Fibonacci dizisi yineleme başka klasik bir örneğidir:

Fib(0) = 0 , temel durum 1 olarak,
Fib(1) = 1 temel durum 2 olarak,
Tüm için tamsayı , n > 1 , Fib ( n ) = Fib ( n - 1) + Fib ( n - 2) .

Birçok matematiksel aksiyom, özyinelemeli kurallara dayanır. Örneğin , Peano aksiyomları tarafından doğal sayıların biçimsel tanımı şu şekilde tanımlanabilir: "Sıfır bir doğal sayıdır ve her doğal sayının aynı zamanda bir doğal sayı olan bir ardılı vardır." Bu temel durum ve özyinelemeli kuralla, tüm doğal sayıların kümesi oluşturulabilir.

Yinelemeli olarak tanımlanan diğer matematiksel nesneler arasında faktöriyeller , fonksiyonlar (örneğin, yineleme ilişkileri ), kümeler (örneğin, Cantor üçlü kümesi ) ve fraktallar bulunur .

Özyinelemenin daha çeşitli tanımları vardır; bkz. özyinelemeli mizah .

Resmi olmayan tanım

Fermantasyon yoluyla köpüren yakın zamanda tazelenmiş ekşi hamur : Tarif, aynı tarifin en son yapıldığı zamandan arta kalan bir miktar ekşi hamur gerektirir.

Özyineleme, prosedürün adımlarından biri prosedürün kendisini çağırmayı içerdiğinde bir prosedürün geçtiği süreçtir. Özyinelemeden geçen bir prosedürün 'özyinelemeli' olduğu söylenir.

Özyinelemeyi anlamak için, bir prosedür ile bir prosedürün yürütülmesi arasındaki farkı tanımak gerekir. Bir prosedür, bir dizi kurala dayanan bir dizi adımdır, bir prosedürün yürütülmesi ise aslında kuralları takip etmeyi ve adımları gerçekleştirmeyi içerir.

Özyineleme, başka bir prosedürün yürütülmesine ilişkin bir prosedürün belirtimi dahilindeki bir referansla ilgilidir, ancak bununla aynı şey değildir.

Bir prosedür bu şekilde tanımlandığında, bu hemen sonsuz bir döngü olasılığını yaratır; özyineleme, yalnızca, prosedürün tamamlanabilmesi için söz konusu adım belirli durumlarda atlanırsa, bir tanımda uygun şekilde kullanılabilir.

Ancak, düzgün bir şekilde tanımlanmış olsa bile, yeniyi eskiden ayırt etmeyi gerektirdiğinden, yinelemeli bir prosedürün insanlar için gerçekleştirilmesi kolay değildir, prosedürün kısmen yerine getirilmesi; bu, prosedürlerin çeşitli eşzamanlı örneklerinin ne kadar ilerlediği konusunda biraz yönetim gerektirir. Bu nedenle, günlük durumlarda özyinelemeli tanımlar çok nadirdir.

dilde

Dilbilimci Noam Chomsky , diğerleri arasında, bir dildeki dilbilgisel tümcelerin sayısı üzerinde bir üst sınırın olmamasının ve dilbilgisel tümce uzunluğu üzerinde bir üst sınırın bulunmamasının (bir dili söylemek için mevcut olan zaman gibi pratik kısıtlamaların ötesinde) olduğunu savundu. ), doğal dilde özyinelemenin sonucu olarak açıklanabilir.

Bu, cümle gibi sözdizimsel bir kategorinin özyinelemeli tanımıyla anlaşılabilir. Bir cümle, fiili takip edenin başka bir cümle olduğu bir yapıya sahip olabilir: Dorothy cadıların tehlikeli olduğunu düşünür , burada cadılar tehlikelidir cümlesi daha büyük olanda geçer. Dolayısıyla bir cümle, özyinelemeli (çok kabaca) bir isim tamlaması, bir fiil ve isteğe bağlı olarak başka bir cümle içeren bir yapıya sahip bir şey olarak tanımlanabilir. Bu gerçekten özyinelemenin matematiksel tanımının özel bir durumudur.

Bu, dilin yaratıcılığını -sınırsız sayıda gramer cümlesi- anlamanın bir yolunu sağlar çünkü cümlelerin keyfi uzunlukta olabileceğini hemen tahmin eder: Dorothy, Toto'nun Teneke Adam'ın bunu söylediğinden şüphelendiğini düşünüyor... . Özyinelemeli olarak tanımlanabilen cümleler dışında birçok yapı vardır ve bu nedenle bir cümlenin bir kategorinin örneklerini diğerinin içine gömebileceği birçok yol vardır. Yıllar boyunca, diller genel olarak bu tür bir analize uygun olduklarını kanıtladılar.

Ancak son zamanlarda, özyinelemenin insan dilinin temel bir özelliği olduğu genel kabul görmüş düşünceye , Pirahã dili hakkındaki iddialarına dayanarak Daniel Everett tarafından karşı çıkıldı . Andrew Nevins, David Pesetsky ve Cilene Rodrigues buna karşı çıkanlar arasında. Edebi öz-göndermenin her halükarda matematiksel veya mantıksal özyinelemeden tür olarak farklı olduğu ileri sürülebilir.

Özyineleme sadece sözdiziminde değil, aynı zamanda doğal dil anlambiliminde de çok önemli bir rol oynar . Örneğin ve sözcüğü , yeni cümleler oluşturmak için cümle anlamlarına uygulanabilen bir işlev olarak yorumlanabilir ve aynı şekilde isim tamlaması anlamları, fiil tamlaması anlamları ve diğerleri için de kullanılabilir. Ayrıca geçişsiz fiiller, geçişli fiiller veya çift geçişli fiiller için de geçerli olabilir. Bunun için uygun şekilde esnek olan ve tipik olarak, argüman olarak bu farklı anlam türlerinden herhangi birini alabilecek şekilde tanımlanan tek bir anlam sağlamak için . Bu, cümleleri birleştirdiği basit bir durum için tanımlayarak ve ardından diğer durumları basit olana göre özyinelemeli olarak tanımlayarak yapılabilir.

Bir özyinelemeli gramer özyinelemeli içeren resmi bir dilbilgisi olan üretim kuralları .

özyinelemeli mizah

Özyinelemeli bir Wikipedia sayfası

Özyineleme bazen bilgisayar bilimi, programlama, felsefe veya matematik ders kitaplarında, genel olarak , varsayılan yinelemeli adımın bir temel duruma yaklaşmadığı, bunun yerine sonsuz bir gerilemeye yol açtığı dairesel bir tanım veya öz referans vererek mizahi bir şekilde kullanılır. . Bu tür kitapların sözlüğe aşağıdaki satırlar boyunca bir fıkra eklemesi alışılmadık bir durum değildir:

Özyineleme, bkz. Özyineleme .

Brian Kernighan ve Dennis Ritchie'nin The C Programming Language kitabının bazı basımlarının dizininde 269. sayfada bir varyasyon bulunur ; dizin girişi yinelemeli olarak kendisine başvurur ("özyineleme 86, 139, 141, 182, 202, 269"). Bu şakanın ilk versiyonları Laurent Siklóssy'nin Let's talk Lisp'te (1 Aralık 1975'te Prentice Hall PTR tarafından yayınlanmıştır, telif hakkı tarihi 1976'dır ) ve Kernighan ve Plauger'ın Software Tools'da (Addison-Wesley Professional tarafından 0000'de yayınlanmıştır) bulunabilir. 11 Ocak 1976). Şaka aynı zamanda Kernighan ve Pike tarafından hazırlanan UNIX Programlama Ortamı'nda da yer almaktadır . The C Programming Language'ın ilk baskısında yer almıyordu . Şaka, İşlevsel programlama folklorunun bir parçasıdır ve yukarıda belirtilen kitapların yayınlanmasından önce işlevsel programlama topluluğunda zaten yaygındı.

Bir başka şaka da şudur: "Özyinelemeyi anlamak için özyinelemeyi anlamalısınız." Google web arama motorunun İngilizce sürümünde, "özyineleme" için bir arama yapıldığında, site "Şunu mu demek istediniz: özyineleme ." Alternatif bir biçim, Andrew Plotkin'den şudur : "Özyinelemenin ne olduğunu zaten biliyorsanız, sadece cevabı hatırlayın. Aksi takdirde, Douglas Hofstadter'a sizden daha yakın olan birini bulun ve ona özyinelemenin ne olduğunu sorun."

Özyinelemeli kısaltmalar , özyinelemeli mizahın diğer örnekleridir. Örneğin PHP , "PHP Hypertext Preprocessor", WINE , "WINE Is Not an Emulator" anlamına gelir. GNU , "GNU Unix değil" anlamına gelir ve SPARQL , "SPARQL Protokolü ve RDF Sorgu Dili" anlamına gelir.

Matematikte

Sierpinski üçgeni -a fraktal oluşturan üçgenlerin Özyinelemeyi sınırlı

Özyinelemeli tanımlı kümeler

Örnek: doğal sayılar

Özyinelemeli olarak tanımlanmış bir kümenin kurallı örneği, doğal sayılarla verilir :

0 var
Eğer , n olup , daha sonra , n + 1 'de olduğu
Doğal sayılar kümesi, önceki iki özelliği sağlayan en küçük kümedir.

Matematiksel mantıkta, Peano aksiyomları (veya Peano varsayımları veya Dedekind-Peano aksiyomları), 19. yüzyılda Alman matematikçi Richard Dedekind ve İtalyan matematikçi Giuseppe Peano tarafından sunulan doğal sayılar için aksiyomlardır . Peano Aksiyomları, özyinelemeli bir ardıl işlevine atıfta bulunan doğal sayıları ve özyinelemeli işlevler olarak toplama ve çarpmayı tanımlar.

Örnek: Kanıt prosedürü

Bir başka ilginç örnek, bir aksiyomatik sistemdeki tüm "kanıtlanabilir" önermelerin kümesidir, bunlar aşağıdaki gibi tümevarımsal (veya özyinelemeli) olarak tanımlanan bir ispat prosedürü açısından tanımlanır:

  • Bir önerme bir aksiyomsa, kanıtlanabilir bir önermedir.
  • Bir önerme, gerçek ulaşılabilir önermelerden çıkarım kuralları aracılığıyla türetilebiliyorsa, o önerme kanıtlanabilir bir önermedir.
  • İspatlanabilir önermeler kümesi, bu koşulları sağlayan en küçük önermeler kümesidir.

Sonlu alt bölme kuralları

Sonlu alt bölme kuralları, fraktal benzeri görüntüler oluşturmak için kullanılabilen geometrik bir özyineleme biçimidir. Bir alt bölme kuralı, sonlu sayıda etiketle etiketlenmiş bir çokgenler koleksiyonuyla başlar ve ardından her çokgen, yalnızca orijinal çokgenin etiketlerine bağlı olacak şekilde daha küçük etiketli çokgenlere bölünür. Bu süreç yinelenebilir. Cantor kümesini oluşturmak için standart "orta üçte birler" tekniği , barycentric altbölüm gibi bir alt bölme kuralıdır .

fonksiyonel özyineleme

Bir fonksiyon , kendisi açısından özyinelemeli olarak tanımlanabilir. Tanıdık bir örnek Fibonacci sayı dizisidir: F ( n ) = F ( n − 1) + F ( n − 2). Böyle bir tanımın faydalı olması için, özyinelemeli olmayan değerlere indirgenebilir olması gerekir: bu durumda F (0) = 0 ve F (1) = 1.

Ünlü bir özyinelemeli işlev, Fibonacci dizisinden farklı olarak özyineleme olmadan ifade edilemeyen Ackermann işlevidir .

Özyinelemeli tanımları içeren kanıtlar

Önceki bölümlerde olduğu gibi, vakalara göre standart ispat tekniğini yinelemeli olarak tanımlanmış kümelere veya fonksiyonlara uygulamak, yapısal tümevarım verir - matematiksel mantık ve bilgisayar biliminde ispat türetmek için yaygın olarak kullanılan matematiksel tümevarımın güçlü bir genellemesi .

özyinelemeli optimizasyon

Dinamik programlama , çok dönemli veya çok adımlı bir optimizasyon problemini özyinelemeli biçimde yeniden ifade eden bir optimizasyon yaklaşımıdır . Dinamik programlamadaki kilit sonuç , optimizasyon probleminin değerini daha erken bir zamanda (veya daha önceki adımda) sonraki bir zamanda (veya daha sonraki adımda) değeri açısından yazan Bellman denklemidir .

özyineleme teoremi

Gelen set teorisi , bu yinelemeli tanımlanmış fonksiyonlar var olduğunu garanti altına alan bir teoremi olduğunu. Verilen bir dizi X , bir element a ait X ve bir işlev f : XX , özel bir işlevi olduğunu teoremi durumları ( şekilde sıfır dahil olmak üzere, doğal sayılar kümesini ifade eder)

herhangi bir doğal sayı için n .

Benzersizlik kanıtı

İki işlevi alın ve şöyle:

burada a , X'in bir öğesidir .

Bu ispat edilebilir tümevarım bu F ( N ) = G ( n ) doğal sayılar için n :

Temel Durum : F (0) = a = G (0) yani eşitlik n = 0 için geçerlidir .
Endüktif Adım : Bazıları için F ( k ) = G ( k ) olduğunu varsayalım . O zaman F ( k + 1) = f ( F ( k )) = f ( G ( k )) = G ( k + 1) .
Bu nedenle F ( k ) = G ( K ) ima F ( k + 1) = G ( k + 1) .

Tümevarım yoluyla, tümü için F ( n ) = G ( n ) .

bilgisayar biliminde

Basitleştirmenin yaygın bir yöntemi, bir problemi aynı türden alt problemlere bölmektir. Bir bilgisayar programlama tekniği olarak buna böl ve yönet denir ve birçok önemli algoritmanın tasarımının anahtarıdır. Böl ve yönet, problemlerin daha küçük ve daha küçük örnekleri çözerek çözüldüğü problem çözmede yukarıdan aşağıya bir yaklaşım olarak hizmet eder. Aksine bir yaklaşım dinamik programlamadır . Bu yaklaşım, istenen boyuta ulaşılana kadar problemlerin daha büyük ve daha büyük örnekleri çözerek çözüldüğü aşağıdan yukarıya bir yaklaşım olarak hizmet eder.

Klasik bir özyineleme örneği, burada C kodunda verilen faktöriyel fonksiyonun tanımıdır :

unsigned int factorial(unsigned int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

İşlev, girdinin daha küçük bir versiyonunda kendini yinelemeli olarak (n - 1)çağırır ve yinelemeli çağrının sonucunu , faktöriyelin matematiksel tanımına benzer şekilde n, temel duruma ulaşana kadar ile çarpar .

Bilgisayar programlamasında yineleme, bir işlev kendisinin daha basit, genellikle daha küçük sürümleri açısından tanımlandığında örneklenir. Daha sonra problemin daha basit versiyonlarından elde edilen çözümler birleştirilerek problemin çözümü tasarlanır. Özyinelemenin bir örnek uygulaması, programlama dilleri için ayrıştırıcılardır . Özyinelemenin en büyük avantajı, sonsuz sayıda olası tümce, tasarım veya diğer verilerin sonlu bir bilgisayar programı tarafından tanımlanabilmesi, ayrıştırılabilmesi veya üretilebilmesidir.

Yineleme ilişkileri , bir veya daha fazla diziyi yinelemeli olarak tanımlayan denklemlerdir. Bazı özel yineleme ilişkileri türleri, yinelemeli olmayan bir tanım elde etmek için "çözülebilir" (örneğin, kapalı biçimli bir ifade ).

Bir algoritmada özyineleme kullanımının hem avantajları hem de dezavantajları vardır. Ana avantaj, genellikle talimatların basitliğidir. Ana dezavantaj, özyinelemeli algoritmaların bellek kullanımının çok hızlı büyüyebilmesi ve daha büyük örnekler için pratik olmamasıdır.

biyolojide

Özyinelemeli süreçlerle yaratılmış gibi görünen şekiller bazen bitkilerde ve hayvanlarda, örneğin büyük bir parçanın iki veya daha fazla benzer küçük parçaya ayrıldığı dallanma yapılarında ortaya çıkar. Bir örnek Romanesco brokolidir .

Sanatta

Rekürsif bebek: orijinal seti Matruşka bebekleri tarafından Zvyozdochkin ve Malyutin 1892
Ön yüzü Giotto sitesindeki Stefaneschi Triptych , 1320, yinelemeli (merkezi panelde diz çökmüş Şekil tarafından düzenlenen), tek başına bir görüntüsünü içerir.

Rus Bebeği veya Matruşka bebeği , özyinelemeli kavramın fiziksel bir sanatsal örneğidir.

Özyineleme beri resimlerinde kullanılmış olan Giotto 'ın Stefaneschi Triptych 1320 yılında yapılan, Onun orta panel bir teklif olarak triptik kendisi tutarak, Kardinal Stefaneschi ait diz çökmüş figürü içeriyor.

MC Escher bireyin Baskı Galeri (1956) bir galeri içeren bir çarpık kent tasvir bir baskı olduğunu yinelemeli resmini içerir ve böylece sonsuza .

Ayrıca bakınız

Referanslar

bibliyografya

Dış bağlantılar