Rekursi: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Wagino Bot (bicara | kontrib) k →Bibliografi: minor cosmetic change |
sudah ada referensi |
||
| (17 revisi perantara oleh 9 pengguna tidak ditampilkan) | |||
Baris 1:
{{Other uses}}
[[
'''Rekursi''' adalah proses pengulangan sesuatu dengan cara [[kesamaan-diri]].
Baris 8 ⟶ 7:
Istilah ini memiliki makna beragam bergantung kepada ragam disiplin mulai dari [[linguistik]] sampai [[logika]].
Penggunaan paling umum dari rekursi yaitu dalam [[matematika]] dan [[ilmu komputer]], yang mengacu kepada suatu metode mendefinisikan [[fungsi (matematika)|fungsi]] yang mana fungsi tersebut menggunakan definisinya sendiri.
Secara spesifik hal ini mendefinisikan suatu instansi tak-terbatas (nilai fungsi), menggunakan ekpresi terbatas dengan beberapa instansi bisa merujuk ke instansi lainnya,
Istilah ini juga digunakan secara umum untuk menjelaskan suatu proses pengulangan objek dengan cara kesamaan-diri.
== Definisi formal dari rekursi ==
[[
Dalam [[matematika]] dan [[ilmu komputer]], kelas dari objek atau metode memperlihatkan perilaku rekursif bila mereka dapat didefinisikan oleh dua properti berikut:
Baris 49 ⟶ 48:
Analoginya mungkin sebuah prosedur adalah seperti resep yang tertulis; menjalankan sebuah prosedur adalah seperti menyiapkan makanan.
Rekursi berhubungan dengan,
Misalnya, suatu resep bisa mengacu pada memasak sayuran, yang merupakan prosedur yang kemudian membutuhkan memanaskan air, dan seterusnya.
Namun, prosedur rekursif adalah spesial dengan (paling tidak) salah satu langkahnya memanggil instansi baru dari prosedur yang sama, seperti suatu resep [[gandum hitam]] menggunakan beberapa sisa adonan dari resep yang sama yang telah dibuat.
Baris 89 ⟶ 88:
}}</ref>
Rekursi dalam linguistik membolehkan 'diskrit tak-terbatas' dengan menanamkan frasa dalam tipe frasa yang sama dalam suatu struktur
Tanpa rekursi, bahasa tidak memiliki 'diskrit tak-terbatas' dan tidak dapat menanamkan kalimat menjadi tak-terbatas (dengan suatu efek '[[Boneka Matryoshka|Sarang boneka Rusia]]').
Everett membantah bahwa bahasa harus memiliki diskrit tak-terbatas, dan menegaskan bahwa bahasa Piraha—yang diklaimnya tidak memiliki rekursi—pada kenyataannya terbatas.
Dia menyamakannya dengan permainan terbatas [[catur]], yang memiliki sejumlah pergerakan terbatas
=== Humor rekursif ===
Baris 120 ⟶ 119:
== Rekursi dalam matematika ==
[[
=== Himpunan yang didefinisikan secara rekursif ===
Baris 132 ⟶ 131:
:0 ada dalam <math>\mathbb{N}</math>
:jika ''n'' ada dalam <math>\mathbb{N}</math>, maka
:Himpunan dari bilangan asli adalah himpunan terkecil yang memenuhi dua properti sebelumnya.
Baris 148 ⟶ 147:
=== Rekursi fungsional ===
Sebuah [[fungsi (matematika)|fungsi]] bisa didefinisikan sebagai bagian dari dirinya sendiri. Contoh yang terkenal adalah urutan [[bilangan Fibonacci]]: ''F''(''n'') = ''F''(''n''
Supaya definisi tersebut dapat berguna, ia harus mengarah pada nilai yang terdefinisi secara tak-rekursif, dalam kasus ini ''F''(0) = 0 dan ''F''(1) = 1.
Baris 166 ⟶ 165:
Metode umum dari penyederhanaan adalah dengan membagi suatu permasalah menjadi beberapa sub-permasalahan dengan tipe yang sama.
Sebagai sebuah teknik dalam [[pemrograman komputer]], hal ini disebut dengan ''[[divide and conquer]]'' dan merupakan kunci dari perancangan berbagai
''Divide and conquer'' menyediakan pendekatan atas-bawah dalam pemecahan masalah, dengan permasalahan diselesaikan dengan menyelesaikan instansi yang lebih kecil.
Pendekatan sebaliknya yaitu [[pemrograman dinamis]].
Baris 173 ⟶ 172:
Contoh klasik dari rekursi adalah definisi dari fungsi [[faktorial]], diberikan dalam kode C:
<
unsigned int factorial(unsigned int n)
{
if (n == 0) {
Baris 182 ⟶ 181:
}
}
</syntaxhighlight>
Fungsi tersebut memanggil dirinya sendiri secara rekursif terhadap versi input yang lebih kecil (n-1) dan mengkalikan hasil dari pemanggilan rekursif dengan n, sampai pada [[kasus dasar]], sama analoginya dengan definisi matematika dari faktorial.
Baris 194 ⟶ 193:
Beberapa relasi perulangan tertentu dapat "diselesaikan" untuk mendapatkan definisi bukan-rekursif.
Penggunaan rekursi dalam suatu
Kelebihan utamanya adalah biasanya kesederhanaan.
Kekurangan utamanya adalah terkadang
== Rekursi dalam Seni ==
[[File:First matryoshka museum doll open.jpg|thumb|Boneka rekursif: kumpulan orisinil dari '[[Matryoshka doll]]s' yang dibuat oleh [[Vasily Zvyozdochkin|Zvyozdochkin]] dan [[Sergey Malyutin|Malyutin]], pada 1892]]
[[File:Polittico stefaneschi, verso.jpg|thumb|left| Wajah depan [[Stefaneschi Triptych]] karya [[Giotto]], 1320, secara rekursif berisi gambar dirinya sendiri (dipegang oleh figur yang berlutut di panel tengah).]]
Boneka Matryoshka adalah contoh artistik fisik dari konsep rekursif.<ref>{{cite web |last1=Tang |first1=Daisy |title=Recursion |url=http://www.cpp.edu/~ftang/courses/CS240/lectures/recursion.htm |access-date=24 September 2015 |quote=More examples of recursion: Russian Matryoshka dolls. Each doll is made of solid wood or is hollow and contains another Matryoshka doll inside it.}}</ref>
Rekursi telah digunakan dalam lukisan sejak [[Stefaneschi Triptych]] karya [[Giotto]], yang dibuat pada tahun 1320. Panel tengahnya berisi figur Kardinal Stefaneschi yang sedang berlutut, mengangkat triptych itu sendiri sebagai persembahan.<ref>{{cite web |title=Giotto di Bondone and assistants: Stefaneschi triptych |url=http://mv.vatican.va/3_EN/pages/PIN/PIN_Sala02_03.html |publisher=The Vatican |access-date=16 September 2015}}</ref><ref>{{Cite book |title=Physical (A)Causality: Determinism, Randomness and Uncaused Events |url=https://books.google.com/books?id=gxBMDwAAQBAJ&pg=PA12 |first=Karl |last=Svozil |year=2018 |publisher=Springer |pages=12| isbn=9783319708157 }}</ref> Praktik ini secara umum dikenal sebagai efek Droste, sebuah contoh teknik Mise en abyme.
M. C. Escher's Print Gallery (1956) adalah sebuah cetakan yang menggambarkan sebuah kota yang terdistorsi yang berisi sebuah galeri yang secara berulang-ulang berisi gambar tersebut, dan seterusnya secara ''<span lang="la" dir="ltr">ad infinitum</span>''(tak terhingga).<ref>{{cite web |last1=Cooper |first1=Jonathan |title=Art and Mathematics |url=https://unwrappingart.com/art/art-and-mathematics/ |access-date=5 July 2020 |date=5 September 2007}}</ref>
== Teorema rekursi ==
Baris 240 ⟶ 250:
{{col-begin}}
{{col-break}}
* [[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]]
{{col-end}}
== Bibliografi ==
* {{cite journal|first=Edsger W.|last=Dijkstra|authorlink=Edsger W. Dijkstra|title=Recursive Programming|journal=Numerische Mathematik|volume=2|issue=1|year=1960|pages=
* {{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 }}
* {{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.
== Lihat juga ==
Baris 291 ⟶ 301:
<references/>
== Pranala
{{Wiktionary|recursion|recursivity}}
* {{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
* {{en}} [http://amitksaha.files.wordpress.com/2009/05/recursion-primer.pdf A Primer on Recursion]- mengandung petunjuk untuk rekursi dalam Bahasa Formal, Linguistik, Matematika dan Ilmu Komputer
* {{en}} [http://research.swtch.com/2010/03/zip-files-all-way-down.html Zip Files All The Way Down]
Baris 300 ⟶ 310:
{{Fraktal}}
{{Logika matematika}}
[[Kategori:Logika Matematika]]▼
[[Kategori:Teori Komputasi]]▼
[[Kategori:Idiom Pemrograman]]▼
[[Kategori:Rekursi| ]]
[[Kategori:Referensi-diri]]
| |||