Rekursi: Perbedaan antara revisi

[[ImageBerkas:Droste.jpg|thumbjmpl|Suatu bentuk rekursi yang dikenal dengan ''[[Efek Droste]]''. Wanita dalam gambar ini memegang suatu objek yang memiliki gambar kecil-nya yang memegang objek yang identik, yang juga memiliki gambar kecil dirinya sendiri yang memegang objek yang identik, dan seterusnya.]]

Secara spesifik hal ini mendefinisikan suatu instansi tak-terbatas (nilai fungsi), menggunakan ekpresi terbatas dengan beberapa instansi bisa merujuk ke instansi lainnya, tapitetapi dengan suatu cara sehingga tidak ada perulangan atau keterkaitan tak-terbatas dapat terjadi.

[[FileBerkas:Screenshot Recursion via vlc.png|thumbjmpl|Rekursi dalam program perekaman layar, dengan suatu jendela paling kecil mengandung foto keseluruhan layar.]]

# SuatuSebuah kasus (atau beberapa kasus) dasar sederhana, dan

Sebuah prosedur yaitu kumpulan langkah-langkah yang akan dilakukan berdasarkan sekumpulan aturan.

Rekursi berhubungan dengan, tapitetapi tidak sama, suatu referensi dalam spesifikasi prosedur sampai pada eksekusi beberapa prosedur lainnya.

Jika titik yang ditemui adalah suatu jalan keluar, berhenti.

Dalam semua kasus, mengeksekusi prosedur membutuhkan pencatatan teliti semua titik percabangan yang telah dieksplorasi, dan cabang-cabang mana yang telah dicoba..

Sebagai contoh, dua kalimat sederhana -- "''Dorothy bertemu dengan Penyihir Jahat dari Barat di Munchkin Land''" dan "''Saudara perempuan Penyihir Jahat dibunuh di Munchkin Land''" -- dapat—dapat disisipkan dalam kalimat ketiga, "''Dorothy menyiram Penyihir Jahat dengan seember air''", untuk mendapatkan kalimat rekursif: "''Dorothy, yang bertemu dengan Penyihir Jahat dari Barat di Munchkin Land tempat saudara perempuannya dibunuh, menyiramnya dengan seember air.''"

Ide bahwa rekursi adalah suatu properti esensi dari bahasa manusia (seperti yang Chomsky ajukan) dibantah oleh [[linguis]] [[Daniel Everett]] dalam karyanya ''Cultural Constraint on Grammar and Cognition in Pirahã: Another Look at the Design Features of Human Language'', yang di sana beliaudia berhipotesis bahwa faktor kultur membuat rekursi tidak dibutuhkan dalam perkembangan [[Bahasa Piraha]].

Konsep ini, yang menantang ide Chomsky bahwa rekursi hanyalahsatu-satunya sifat yang membedakan komunikasi manusia dan hewan, sekarang sedang diperdebatkan.

Rekursi dalam linguistik membolehkan 'diskrit tak-terbatas' dengan menanamkan frasa dalam tipe frasa yang sama dalam suatu struktur hirarkihierarki.

Everett membantah bahwa bahasa harus memiliki diskrit tak-terbatas, dan menegaskan bahwa bahasa Piraha - yangPiraha—yang diklaimnya tidak memiliki rekursi - padarekursi—pada kenyataannya terbatas.

Dia menyamakannya dengan permainan terbatas [[catur]], yang memiliki sejumlah pergerakan terbatas tapitetapi sangat produktif, dengan gerakan-gerakan baru diciptakan lewat sejarah.

}}</ref>

[[FileBerkas:Sierpinski triangle.svg|rightka|thumbjmpl|250px|[[Segitiga Sierpinski]]—sebuah rekursi terbatas dari segitiga membentuk suatu [[jeruji]] geometris.]]

:jika ''n'' ada dalam <math>\mathbb{N}</math>, maka ''n'' + 1 ada dalam <math>\mathbb{N}</math>

Sebuah [[fungsi (matematika)|fungsi]] bisa didefinisikan sebagai bagian dari dirinya sendiri. Contoh yang terkenal adalah urutan [[bilangan Fibonacci]]: ''F''(''n'') = ''F''(''n'' &minus;− 1) + ''F''(''n'' &minus;− 2).

Supaya definisi tersebut dapat berguna, ia harus menggunakanmengarah pada nilai yang terdefinisi secara tak-rekursif, dalam kasus ini ''F''(0) = 0 dan ''F''(1) = 1.

Fungsi rekursif terkenal yaitu [[fungsi Ackermann]] yang, tidakmana—tidak seperti urutan Fibonacci, tidakFibonacci—tidak dapat dengan mudah diekspresikan tanpa rekursi.

Menerapkan teknik standar dari [[pembuktian dengan kasus]] untuk mendefinisikan secara rekursif suatu himpunan atau fungsi, seperti bagian sebelumnya, menghasilkan [[induksi struktural]], generalisasi ampuh dari [[induksi matematika]] yang secara luas digunakan untuk menurunkan pembuktian dalam [[logika matematika]] dan [[ilmu komputer]].

Sebagai sebuah teknik dalam [[pemrograman komputer]], hal ini disebut dengan ''[[divide and conquer]]'' dan merupakan kunci dari perancangan berbagai algoritmaalgoritme penting.

<sourcesyntaxhighlight lang="c">

unsigned int factorial(unsigned int n)

Penggunaan rekursi dalam suatu algoritmaalgoritme memiliki kelebihan dan kekurangan.

Kekurangan utamanya adalah terkadang algoritmaalgoritme tersebut membutuhkan memori yang sangat banyak jika kedalaman rekursi sangat besar.

* [[Rasio Golden]]: <math>\phi = 1 + (1/\phi) = 1 + (1/(1 + (1/(1 + 1/...))))</math>

* [[Faktorial]]: <math>n! = n (n - 1)! = n (n - 1)\cdots 1</math>

* [[Bilangan Fibonacci]]: <math>f (n) = f (n - 1) + f (n - 2)</math>

* [[Bilangan Catalan]]: <math>C_0=1</math>, <math>C_{n+1} = (4n+2)C_n/(n+2)</math>

* Perhitungan [[suku bunga]]

* [[Menara Hanoi]]

* [[Fungsi Ackermann]]

* {{cite journal|first=Edsger W.|last=Dijkstra|authorlink=Edsger W. Dijkstra|title=Recursive Programming|journal=Numerische Mathematik|volume=2|issue=1|year=1960|pages=312&ndash;318312–318|doi=10.1007/BF01386232}}

* {{cite book | author=Johnsonbaugh, Richard | title=Discrete Mathematics | publisher=Prentice Hall | year=2004 | isbn=0-13-117686-2 }}

* {{cite book | author=Hofstadter, Douglas | title=Gödel, Escher, Bach: an Eternal Golden Braid | publisher=Basic Books | year=1999 | isbn=0-465-02656-7 }}

* {{cite book | author=Shoenfield, Joseph R. | title=Recursion Theory | url=https://archive.org/details/recursiontheory0000shoe|publisher=A K Peters Ltd | year=2000 | isbn=1-56881-149-7 }}

* {{cite book | author=Causey, Robert L. | title=Logic, Sets, and Recursion | url=https://archive.org/details/logicsetsrecursi0000caus|publisher=Jones & Bartlett | year=2001 | isbn=0-7637-1695-2 }}

* {{cite book | author=Cori, Rene; Lascar, Daniel; Pelletier, Donald H. | title=Recursion Theory, Gödel's Theorems, Set Theory, Model Theory | publisher=Oxford University Press | year=2001 | isbn=0-19-850050-5 }}

* {{cite book | author=Barwise, Jon; Moss, Lawrence S. | title=Vicious Circles | publisher=Stanford Univ Center for the Study of Language and Information | year=1996 | isbn=0-19-850050-5 }} - menjelaskan pengerjaan dari [[corecursion]].

* {{cite book | author=Rosen, Kenneth H. | title=Discrete Mathematics and Its Applications | publisher=McGraw-Hill College | year=2002 | isbn=0-07-293033-0 }}

* {{cite book | author=Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, Clifford Stein | title=Introduction to Algorithms | publisher=Mit Pr | year=2001 | isbn=0-262-03293-7 }}

* {{cite book | author = Kernighan, B.; Ritchie, D. | title=The C programming Language | publisher=Prentice Hall | year = 1988 | isbn = 0-13-110362-8 }}

* {{cite book | author=Stokey, Nancy,; Robert Lucas; Edward Prescott | title=Recursive Methods in Economic Dynamics | publisher=Harvard University Press | year=1989 | isbn=0-674-75096-9}}

* {{cite book | author=Hungerford |title=Algebra | publisher=Springer|year=1980|isbn=978-0-387-90518-1}}, bagian pertama dari teori himpunan.

== Pranala Luarluar ==

* {{en}} [http://www.freenetpages.co.uk/hp/alan.gauld/tutrecur.htm Recursion] {{Webarchive|url=https://web.archive.org/web/20050206051223/http://www.freenetpages.co.uk/hp/alan.gauld/tutrecur.htm |date=2005-02-06 }} - tutorial oleh Alan Gauld

{{Logika matematika}}