Wikipedia

Rekursi: Perbedaan antara revisi

Jelajahi riwayat secara interaktif
← Revisi sebelumnya
Konten dihapus Konten ditambahkan
VisualTeks wiki
Sulhan (bicara | kontrib)
663 suntingan
Expand the article using en:recursion rev. 2012-02-11 at 01:42:54, unchecked, will be check for typo and readability again later.
Zɛphyɻ (bicara | kontrib)
316 suntingan
sudah ada referensi
 
(40 revisi perantara oleh 15 pengguna tidak ditampilkan)
Baris 1:
{{Other uses}}
{{No footnotes|date=February 2010}}
 
[[ImageBerkas:Droste.jpg|thumbjmpl|Suatu bentuk rekursifrekursi yang dikenal dengan ''[[Efek Droste]]''. Wanita dalam gambar ini memegang suatu objek yang memiliki gambar kecil-nya yang memegang objek yang samaidentik, yang juga memiliki gambar kecil dirinya sendiri yang memegang objek yang samaidentik, dan seterusnya.]]
 
'''RekursifRekursi''' adalah proses pengulangan itemsesuatu dengan cara [[kesamaan-diri]].
Sebagai contohnya, saat dua cermin berada paralel antara satu dengan yang lain, gambar yang tertangkap adalah suatu bentuk rekursifrekursi tak-terbatas.
Istilah ini memiliki makna beragam bergantung kepada ragam disiplin mulai dari [[linguistik]] sampai [[logika]].
Penggunaan paling umum dari rekursifrekursi yaitu dalam [[matematika]] dan [[ilmu komputer]], dimana iayang mengacu kepada suatu metodametode 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 yang manadengan beberapa instansi bisa merujuk kepadake instansi lainnya, tapitetapi dengan suatu cara dimanasehingga tidak ada perulangan atau keterkaitan tak-terbatas dapat terjadi.
Istilah ini juga digunakan secara umum untuk menjelaskan suatu proses pengulangan objek dengan cara yang samakesamaan-diri.
 
== Definisi formal dari rekursifrekursi ==
 
[[FileBerkas:Screenshot Recursion via vlc.png|thumbjmpl|RekursifRekursi dalam program perekaman layar, dimanadengan suatu jendela paling kecil mengandung foto keseluruhan layar.]]
 
Dalam [[matematika]] dan [[ilmu komputer]], kelas dari objek atau metode memperlihatkan perilaku rekursif bila mereka dapat didefinisikan oleh dua properti berikut:
 
# SuatuSebuah kasus (atau beberapa kasus) dasar sederhana, dan
# Sejumlah aturan yang mengurangi kasus-kasus lainnya sampai ke kasus dasarnya.
 
Sebagai contoh, berikut ini adalah definisi rekursif dari leluhur seseorang:
* [[Orang tua]] seseorang adalah [[leluhur]] seseorang (''kasus dasar'').
* Orang tua dari suatu leluhur juga merupakan leluhur-nya (''langkah rekursifrekursi'').
 
[[Bilangan Fibonacci]] adalah contoh klasik dari rekursifrekursi:
 
* Fib(0) adalah 0 [kasus dasar]
Baris 30:
 
Banyak aksioma matematika berdasarkan aturan-aturan rekursif.
Sebagai contohnya, definisodefinisi formal dari [[bilangan asli]] dalampada [[teoriAksioma himpunanPeano]] berbunyidapat dideskripsikan sebagai: ''10 adalah bilangan asli, dan setiap bilangan asli memiliki sebuah suksesor, yang juga merupakan bilangan asli.''
Dengan kasus dasar ini dan aturan rekursif, seseorang dapat membuat himpunan dari semua bilangan asli.
 
Gambaran humornya berbunyi: ''"Untuk memahami rekursifrekursi, pertama anda harus memahami rekursifrekursi."''
Atau mungkin yang lebih akurat, dari [[Andrew Plotkin]]: ''"Jika anda telah mengetahui apa itu rekursifrekursi, cukup ingat jawabannya. Kalau tidak, cari orang yang berdiri paling dekat dengan [[Douglas Hofstadter]] dariselain anda; lalu tanya dia rekursifrekursi itu apa."''
 
Objek matematismatematika yang didefinisikan secara rekursif termasuk [[fungsi (matematika)|fungsi]], [[himpunan (matematika)|himpunan]], dan khususnyaterutama sekali [[fraktal]].
 
== RekursifDefinisi dalam bahasainformal ==
Ahli linguistik [[Noam Chomsky]] memberikan teori bahwa ekstensi tak-terhingga dari setiap [[bahasa alami]] adalah memungkinkan menggunakan perangkat rekursif dengan menanamkan frase dalam kalimat. Maka, seorang yang cerewet akan berkata, ''"Dorothy, yang bertemu dengan Penyihir Barat jahat di Munchkin Land di mana saudara perempuannya yang juga Penyihir dibunuh, menyiramnya dengan seember air."'' Jelas, dua kalimat sederhana-''"Dorothy bertemu Penyihir Jahat dari Munchkin Land barat"'' dan ''"Saudara perempuannya dibunuh di Munchkin Land"''-dapat ditanamkan dalam kalimat ketiga, ''"Dorothy menyiramnya dengan seember air,"'' untuk memperoleh kalimat yang sangat jelas.
 
Rekursi adalah suatu proses dengan salah satu langkah dalam prosedur tersebut menjalankan prosedur itu sendiri.
Ide bahwa rekursif 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'', dimana disana beliau berhipotesis bahwa faktor kultur membuat rekursif tidak dibutuhkan dalam perkembangan [[Bahasa Piraha]].
Prosedur yang melakukan rekursi disebut dengan 'rekursif'.
Konsep ini, yang menantang ide Chomsky bahwa rekursif hanyalah sifat yang membedakan komunikasi manusia dan hewan, sekarang sedang diperdebatkan.
 
Untuk memahami rekursi, seseorang harus mengetahui perbedaan antara sebuah prosedur dan jalannya sebuah prosedur.
Sebuah prosedur yaitu kumpulan langkah-langkah berdasarkan sekumpulan aturan.
Jalannya sebuah prosedur mengikuti aturan-aturan dan melakukan langkah-langkah.
Analoginya mungkin sebuah prosedur adalah seperti resep yang tertulis; menjalankan sebuah prosedur adalah seperti menyiapkan makanan.
 
Rekursi berhubungan dengan, tetapi tidak sama, suatu referensi dalam spesifikasi prosedur sampai pada eksekusi beberapa prosedur lainnya.
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.
Hal ini tentu saja membuat suatu kemungkinan perulangan tanpa berakhir; rekursi hanya dapat digunakan secara tepat dalam definisi jika langkah yang bersangkutan dilewat pada beberapa kasus sehingga prosedur dapat selesai, seperti resep gandum-hitam yang memberitahu anda bagaimana membuat adonan awal seandainya anda belum pernah membuatnya sebelumnya.
Bahkan jika didefinisikan secara tepat, prosedur rekursif tidak mudah dilakukan oleh manusia, karena ia membutuhkan membedakan pemanggilan prosedur yang baru dengan yang lama (yang telah dieksekusi sebagian); hal ini membutuhkan beberapa administrasi sejauh mana berbagai prosedur instan yang berjalan bersamaan telah berjalan.
Karena hal ini definisi rekursif sangat jarang dalam keadaan harian.
Contohnya dapat berupa prosedur untuk menemukan jalan melewati sebuah [[labirin]].
Terus ke depan sampai menemui jalan keluar atau titik percabangan (sebuah titik mati dianggap sebagai sebuah titik percabangan dengan 0 cabang).
Jika titik yang ditemui adalah suatu jalan keluar,berhenti.
Kalau tidak coba setiap cabang bergantian, menggunakan prosedur secara rekursif; jika setiap percobaan gagal karena mencapai titik mati, kembali ke jalur yang menyebabkan titik percabangan dan laporkan kegagalan.
Apakah ini tepat mendefinisikan suatu prosedur pemberhentian bergantung kepada bentuk labirinnya: ia tidak membolehkan perulangan.
Dalam semua kasus, mengeksekusi prosedur membutuhkan pencatatan teliti semua titik percabangan yang telah dieksplorasi, dan cabang-cabang mana yang telah dicoba..
 
== Rekursi dalam bahasa ==
 
Ahli linguistik [[Noam Chomsky]] memberikan teori bahwa ekstensi tak-terhingga dari setiap [[bahasa alami]] adalah memungkinkan menggunakan perangkat rekursif dengan menanamkan klausa dalam kalimat
(Aspects of the Theory of Syntax. 1965).
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 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 dia berhipotesis bahwa faktor kultur membuat rekursi tidak dibutuhkan dalam perkembangan [[Bahasa Piraha]].
Konsep ini, yang menantang ide Chomsky bahwa rekursi satu-satunya sifat yang membedakan komunikasi manusia dan hewan, sekarang sedang diperdebatkan.
Andrew Nevins, David Pesetsky dan Cilene Rodrigues berdebat melawan proposal tersebut.
<ref>{{cite journal
Baris 61 ⟶ 87:
| pages = 671–681
}}</ref>
Bukti tak-langsung bahwa ide Everett salah datang dari kerja neurolinguistik dimana tampak bahwa semuah manusia diberkahi dengan struktur neurobiologis yang sangat sama untuk mengatur semua dan hanya bahasa rekursif. Untuk tinjauan, lihat Kaan et al. (2002)
 
RekursifRekursi dalam linguistik membolehkan 'diskrit tak-terbatas' dengan menanamkan frasefrasa dalam tipe frasefrasa yang sama dalmdalam suatu struktur hirarkihierarki.
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 - yangPiraha—yang diklaimnya tidak memiliki rekursi - adalahrekursi—pada faktanyakenyataannya terbatas.
Dia menyamakannya dengan permainan terbatas [[catur]], yang memiliki sejumlah pergerakan terbatas tapitetapi sangat produktirproduktif, dengan gerakan-gerakan baru diciptakan lewat sejarah.
 
=== Rekursif dalam bahasa sederhana ===
 
Rekursif adalah proses dimana salah satu langkah dalam prosedur menjalankan prosedur itu sendiri.
Prosedur yang melakukan rekursif disebut dengan 'rekursi'.
 
Untuk memahami rekursif, seseorang harus mengetahui perbedaan antara sebuah prosedur dan jalannya sebuah prosedur.
Sebuah prosedur yaitu kumpulah langkah-langkah yang akan dilakukan berdasarkan suatu kumpulan aturan.
Jalannya sebuah prosedur mengikuti aturan-aturan dan melakukan langkah-langkah.
Analoginya mungkin sebuah prosedur adalah seperti buku resep dimana di dalamnya terdapat langkah-langkap yang memungkinkan, sementara jalannya sebuah prosedur adalah menyiapkan makanan.
 
Rekursif berhubungan dengan, tapi tidak sama, suatu referensi dalam spesifikasi prosedur sampai pada eksekusi beberapa prosedur lainnya.
Misalnya, suatu resep bisa mengacu pada memasak sayuran, yang merupakan prosedur yang kemudian membutuhkan memanaskan air, dan seterusnya.
Namun, prosedur rekursif adalah spesial dimana (paling tidak) salah satu langkahnya memanggil instansi baru dari prosedur yang sama, seperti suatu resep [[sourdough]] menggunakan beberapa sisa adonan dari resep yang sama yang telah dibuat.
Hal ini tentu saja membuat suatu kemungkinan perulangan tanpa berakhir; rekursi hanya dapat digunakan secara tepat dalam definisi jika langkah yang bersangkutan dilewat pada beberapa kasus sehingga prosedur dapat selesai, seperti resep sourdough yang memberitahu anda bagaimana membuat adonan awal seandainya anda belum pernah membuatnya sebelumnya.
Bahkan jika didefinisikan secara tepat, prosedur rekursif tidak mudah dilakukan oleh manusia, karena ia membutuhkan membedakan pemanggilan prosedur yang baru dengan yang lama (yang telah dieksekusi sebagian); hal ini membutuhkan beberapa administrasi sejauh mana berbagai prosedur instan yang berjalan bersamaan telah berjalan.
Karena hal ini definisi rekursif sangat jarang dalam keadaan harian.
Contohnya dapat berupa prosedur untuk menemukan jalan melewati sebuah [[labirin]].
Terus ke depan sampai menemui jalan keluar atau titik percabangan (sebuah titik mati dianggap sebagai sebuah titik pisah dengan 0 cabang).
Jika titik yang ditemui adalah suatu jalan keluar, berhenti.
Kalau tidak coba setiap cabang bergantian, menggunakan prosedur secara rekursif; jika setiap percobaan gagal karena mencapai titik mati, kembali ke jalur yang menyebabkan titik percabangan dan laporkan kegagalan.
Apakah ini tepat mendefinisikan suatu prosedur pemberhentian bergantung kepada bentuknya labirinnya: ia tidak membolehkan perulangan.
Dalam semua kasus, mengeksekusi prosedur membutuhkan pencatatan teliti semua titik percabangan yang telah dieksplorasi, dan cabang-cabang mana yang telah dicoba.
 
=== Humor rekursif ===
 
Rekursi terkadang digunakan secara humor dalam buku ilmu komputer, pemrograman, filsafat, atau matematika;. duaAdalah contohhal berikutyang bisabiasa ditemukanbagi dalambuku-buku suatutersebut untuk memasukan lelucon dalam [[glosarium]]-nya di antara barisan:
 
<ref name=Hunter
:Rekursi, ''lihat Rekursi''.<ref name=Hunter>
>{{cite book
{{cite book
|last=Hunter
|first=David
Baris 103 ⟶ 106:
|pages=494
|url=http://books.google.com/books?id=kuwhTxCVovQC&dq=recursion+joke&source=gbs_navlinks_s
}}</ref>
:'''Rekursi'''
::Lihat "Rekursi".
:'''Rekursi'''
::Jika anda masih tidak mengerti, lihat "Rekursi".
 
Sebuah variasi ditemukan di halaman 269 dalam [[Belakang-buku indeks|indeks]] pada halaman 269 dari beberapa edisi buku Kernighan dan Ritchie "''[[The C Programming Language (book)|The C Programming Language]]"''; dimana isi indeks secara rekursif mengacu kepada dirinya sendiri: ("rekursi 86, 139, 141, 182, 202, 269").
Versi awal dari lelucon ini ada di dalam "Software Tools" oleh Kernighan dan Plauger, dan juga muncul dalam "The UNIX Programming Environment" oleh Kernighan dan Pike.
Ia tidak ada di edisi pertama dari ''The C Programming Language''.
 
Lelucon yang lain adalah "Untuk memahami rekursi, anda harus memahami rekursi."<ref name=Hunter/>
:rekursi 86, 139, 141, 182, 202, '''269'''
Dalam versi bahasa Inggris dari mesin pencari web [[Google]], saat mencari kata untuk rekursi dalam bahasa Inggris "recursion" dilakukan, situs tersebut menyarankan "Did you mean: ''recursion''."
 
[[Akronim berulang]] juga dapat sebagai contoh dari humor rekursif. [[PHP]], contohnya, singkatan dari "PHP Hypertext Preprocessor", [[Wine (perangkat lunak)|WINE]] singkatan dari "Wine Is Not an Emulator", [[Proyek GNU|GNU]] singkatan dari "GNU's not Unix".
Versi terbaru dari lelucon ini ada di dalam "Software Tools" oleh Kernighan dan Plauger, dan juga muncul dalam "The UNIX Programming Environment" oleh Kernighan dan Pike.
Ia tidak ada di edisi pertama dari "The C Programming Language".
 
Lelucon yang sama juga terdapat di alat pencari web [[Google]]: saat mencari kata untuk rekursif dalam bahasa Inggris "rekursion" dilakukan, situs tersebut menyarankan "{{Color|red|Did you mean:}} ''[http://www.google.com/search?q=recursion Recursion]''."
 
[[Akronim rekursif]] juga dapat sebagai contoh dari humor rekursif. [[PHP]], contohnya, singkatan dari "PHP Hypertext Preprocessor" dan [[Wine (software)|WINE]], contohnya, singkatan dari "Wine Is Not an Emulator."
 
== Rekursi dalam matematika ==
 
[[ImageBerkas:Sierpinski Triangletriangle.svg|rightka|thumbjmpl|250px|[[Segitiga Sierpinski]]—sebuah rekursi terbatas dari segitiga membentuk suatu [[jeruji]] geometris.]]
 
=== Set-setHimpunan yang didefinisikan secara rekursif ===
{{Main|Definisi rekursif}}
 
==== Contoh: bilangan asli ====
 
{{see also|Closure (matematika)}}
Contoh kanonikal dari set yang didefinisikan secara rekursif yaitu diberikan oleh [[bilangan asli]]:
 
Contoh kanonikal dari himpunan yang didefinisikan secara rekursif yaitu diberikan oleh [[bilangan asli]]:
:1 ada dalam <math>\mathbb{N}</math>
:jika ''n'' ada dalam <math>\mathbb{N}</math>, maka ''n'' + 1 ada dalam <math>\mathbb{N}</math>
:Set dari bilangan asli adalah set terkecil yang memenuhi dua properti sebelumnya.
 
:0 ada dalam <math>\mathbb{N}</math>
==== Contoh: set dari proprosisi benar terjangkau ====
:jika ''n'' ada dalam <math>\mathbb{N}</math>, maka ''n'' + 1 ada dalam <math>\mathbb{N}</math>
Contoh menarik lainnya adalah set dari semua proposisi "benar terjangkau" dalam suatu [[sistem aksioma]].
:Himpunan dari bilangan asli adalah himpunan terkecil yang memenuhi dua properti sebelumnya.
 
*==== JikaContoh: suatuhimpunan proposisi adalah sebuah aksiom, maka ia adalah suatudari proposisi benar terjangkau. ====
* Jika suatu proposisi dapat dihasilkan dari proposisi benar terjangkau dalam artian aturan-aturan inferensi, maka ia adalah proposisi benar terjangkau.
* Set dari proposisi benar-terjangkau adalah set terkecel dari proposisi yang memenuhi kondisi tersebut.
 
Contoh menarik lainnya adalah himpunan dari semua proposisi "benar terjangkau" dalam suatu [[sistem aksioma]].
Set ini disebut 'proposisi benar terjangkau' karena dalam pendekatan selain-konstruktif ke fondasi matematika, set dari proposisi benar bisa lebih besar daripada set yang dibangun secara rekursif dari aksiom-aksiom dan aturan-aturan inferensi.
 
* Jika suatu proposisi adalah sebuah aksioma, maka ia adalah suatu proposisi benar terjangkau.
* Jika suatu proposisi dapat dihasilkan dari proposisi benar terjangkau dengan menggunakan aturan-aturan inferensi, maka ia adalah proposisi benar terjangkau.
* Himpunan dari proposisi benar-terjangkau adalah himpunan terkecil dari proposisi yang memenuhi kondisi tersebut.
 
Himpunan ini disebut 'proposisi benar terjangkau' karena dalam pendekatan non-konstruktif terhadap fondasi matematika, himpunan dari proposisi benar bisa lebih besar daripada himpunan yang dibangun secara rekursif dari aksioma-aksioma dan aturan-aturan inferensi.
Lihat juga [[Teorema ketaklengkapan Godel]].
 
=== Rekursi fungsional ===
 
Sebuah [[fungsi (matematika)|fungsi]] bisa didefinisikan sebagai bagian dari dirinya sendiri. Contoh yang dikenalterkenal 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 mana, tidakmana—tidak seperti urutan Fibonacci, tidakFibonacci—tidak dapat dengan mudah diekspresikan tanpa rekursi.
 
=== Pembuktian yang mengikutkan definisi rekursif ===
 
Menerapkan teknik standar dari [[pembuktian dengan kasus]] untuk mendefinisikan secara rekursif suatu sethimpunan 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]].
 
=== Optimisasi rekursif ===
 
[[Pemrograman Dinamisdinamis]] adalah suatu pendekatan terhadap [[optimisasi (matematika)|optimisasi]] yang menempatkan ulang suatu permasalahan multiperiode atau tahapan dalam bentuk rekursif.
HasilKunci kuncijawaban dari pemrograman dinamis adalah [[persamaan Bellman]], yang menulikanmenuliskan nilai dari permasalahan optimisasi pada waktu awal (atau langkah awal) daripadaberkenaan dengan nilainya pada waktu kemudian (atau langkah selanjutnya).
 
== Rekursi dalam ilmu komputer ==
{{Main|Rekursi (ilmu komputer)}}
 
MetodaMetode 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 algoritmaalgoritme penting.
'''Divide and conquer''' menyediakan pendekatan atas-bawah dalam pemecahan masalah, dimanadengan permasalahpermasalahan diselesaikan dengan menyelesaikan instaninstansi yang lebih kecil.
Pendekatan sebaliknya yaitu [[pemrograman dinamis]].
Pendekatan ini menyelesaikannya secara bawah-atas, dimanadengan permasalahan diselesaikan dengan menyelesaikan instaninstansi yang lebih besar, sampai ukuran yang diinginkan dicapai.
 
Contoh klasik dari rekursi adalah definisi dari fungsi [[faktorial]], diberikan dalam kode C:
 
<sourcesyntaxhighlight lang="c">
unsigned int factorial(unsigned int n)
{
if (n <== 10) {
return 1;
} else {
return n * factorial(n-1);
}
}
</syntaxhighlight>
</source>
 
Fungsi tersebut memanggilnyamemanggil 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.
 
Rekursi dalam pemrograman komputer dicontohkan saat sebuah fungsi didefinisikan dalam makanbentuk sederhana, bahkan versi terkecil dari dirinya.
Solusi dari permasalahan kemudian dirancang dengan menggabungkan solusi-solusi yang didapat dari versi sederhana dari permasalahan.
SaahSalah satu contoh aplikasi rekursi yaitu dalam ''[[parsing]]'' untuk bahasa pemrograman.
Keuntungan utama dari rekursi adalah setsuatu himpunan tak-terbatas dari kalimat yang memungkinkan, perancangan atau data lainnya dapat didefinisikan, diurai atau dihasilkan dengan suatu program komputer yang terbatas.
 
[[Relasi perulangan]] adalah persamaan-persamaan untuk menentukan satu atau lebih urutan-urutan secara rekursif.
Beberapa relasi perulangan tertentu dapat "diselesaikan" untuk mendapatkan definisi bukan-rekursif.
 
Penggunaan rekursi dalam suatu algoritmaalgoritme memiliki kelebihan dan kekurangan.
Kelebihan utamanya adalah biasanya kesederhanaan.
Kekurangan utamanya adalah terkadang algoritmaalgoritme tersebut membutuhkan memori yang sangat banyak jika kedalaman rekursi sangat besar.
 
== 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 ==
 
Dalam [[teori sethimpunan]], ini adalah teorema yang menjamin bahwa fungsi yang terdefinisi secara rekursif itu ada.
Diberikan suatu sethimpunan ''X'', sebuah elemen ''a'' dari ''X'' dan sebuah fungsi <math>f: X \rightarrow X</math>, teorema menyatakan bahwa ada fungsi unik <math>F: \mathbb{N} \rightarrow X</math> (dimanadengan <math>\mathbb{N}</math> menunjukkan sethimpunan dari bilangan asli termasuk nol) sehingga
:<math>F(0) = a</math>
:<math>F(n + 1) = f(F(n))</math>
Baris 217 ⟶ 229:
:<math>G(n + 1) = f(G(n))</math>
 
dimanadengan ''a'' adalah sebuah elemen dari ''X''.
 
Ia dapat dibuktikan dengan [[induksi matematika]] bahwa
Baris 238 ⟶ 250:
{{col-begin}}
{{col-break}}
* [[Golden Rasio Golden]]: φ<math>\phi = 1 + (1/φ\phi)... mengingat= bahwa φ = 1 + (1/φ) then ... φ = (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>
*Komputasi senyawaPerhitungan [[suku bunga]]
*The [[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=312–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=HofstadterJohnsonbaugh, Douglas Richard| title=Gödel, Escher, Bach: an Eternal Golden BraidDiscrete Mathematics| publisher=Basic BooksPrentice Hall| year=1999 2004| isbn=0-46513-02656117686-72 }}
* {{cite book | author=ShoenfieldHofstadter, Joseph R. Douglas| title=RecursionGödel, TheoryEscher, |Bach: publisher=Aan KEternal PetersGolden LtdBraid|publisher=Basic Books| year=2000 1999| isbn=10-56881465-14902656-7 }}
* {{cite book | author=CauseyShoenfield, RobertJoseph LR. | title=Logic, Sets, and Recursion Theory|url=https://archive.org/details/recursiontheory0000shoe| publisher=JonesA &K BartlettPeters Ltd| year=2001 2000| isbn=01-763756881-1695149-27 }}
* {{cite book | author=CoriCausey, Rene;Robert Lascar, Daniel; Pelletier, Donald HL. | title=Recursion TheoryLogic, Godel's TheoremsSets, Set Theory, Model Theoryand Recursion|url=https://archive.org/details/logicsetsrecursi0000caus| publisher=OxfordJones University Press& Bartlett| year=2001 | isbn=0-197637-8500501695-52 }}
* {{cite book | author=BarwiseCori, JonRene; MossLascar, LawrenceDaniel; Pelletier, Donald SH. | title=ViciousRecursion CirclesTheory, |Gödel's publisher=StanfordTheorems, UnivSet CenterTheory, forModel theTheory|publisher=Oxford Study of Language and InformationUniversity Press| year=1996 2001| isbn=0-19-850050-5 }} - menjelaskan pengerjaan dari [[corecursion]].
* {{cite book | author=RosenBarwise, KennethJon; H.Moss, |Lawrence S.|title=DiscreteVicious MathematicsCircles|publisher=Stanford andUniv ItsCenter Applicationsfor |the publisher=McGraw-HillStudy Collegeof |Language and Information|year=2002 1996| isbn=0-0719-293033850050-05 }} - menjelaskan pengerjaan dari [[corecursion]].
* {{cite book | author=CormenRosen, ThomasKenneth H., Charles E. Leiserson, Ronald L. Rivest, Clifford Stein | title=IntroductionDiscrete toMathematics Algorithmsand |Its Applications|publisher=Mit PrMcGraw-Hill College| year=2001 2002| isbn=0-26207-03293293033-70 }}
* {{cite book | author =Cormen, KernighanThomas H., BCharles E.; RitchieLeiserson, DRonald L. |Rivest, Clifford Stein|title=TheIntroduction C programming Languageto Algorithms| publisher=Prentice HallMit Pr| year = 1988 2001| isbn = 0-13262-11036203293-87 }}
* {{cite book |author author=Stokey, NancyKernighan,; Robert LucasB.; Edward PrescottRitchie, D.| title=RecursiveThe MethodsC in Economic Dynamicsprogramming Language| publisher=HarvardPrentice UniversityHall|year Press= 1988|isbn year=1989 |0-13-110362-8 isbn=0674750969}}
* {{cite book | author=HungerfordStokey, Nancy,; Robert Lucas; Edward Prescott|title=AlgebraRecursive |Methods in Economic Dynamics|publisher=SpringerHarvard University Press|year=19801989|isbn=9780-0387905181674-75096-9}}, bagian pertama dari teori set.
* {{cite book|author=Hungerford|title=Algebra|publisher=Springer|year=1980|isbn=978-0-387-90518-1}}, bagian pertama dari teori himpunan.
 
== Lihat juga ==
 
<div style="-moz-column-count:43; column-count:43;">
* [[Church-Turing thesisKorekursi]]
* [[ContinuousRekursi predicateCourse-of-values]]
* [[CorecursionKetakterbatasan digital]]
* [[Course-of-valuesKombinator recursiontitik tetap]]
* [[DrostePerulangan effectTakterbatas]]
* [[Fixed point combinatorInfinitisme]]
* [[InfiniteFungsi loopIterasi]]
* [[Infinitism]]
* [[Iterated function]]
* [[Mise en abyme]]
* [[Primitive recursive function]]
<!--
Including [[Recursion]] in this list will not display correctly, and
Baris 280 ⟶ 290:
-->
* [[Reentrant (subroutine)]]
* [[SelfReferensi-referencediri]]
* [[StrangePerulangan loopganjil]]
* [[TailRekursi recursionbuntut]]
* [[Formula Tupper's self-referential formula]]
* [[Turtles all the way down]]
* [[Viable System Model]]
</div>
 
Baris 292 ⟶ 301:
<references/>
 
== TautanPranala Luarluar ==
 
{{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]
* {{en}} [http://www.ucl.ac.uk/psychlangsci/staff/linguistics-staff/nevins-publications/npr09b Nevins, Andrew and David Pesetsky and Cilene Rodrigues. Evidence and Argumentation: A Reply to Everett (2009). Language 85.3: 671--681 (2009)]
*[http://faculty.washington.edu/losterho/kaan_and_swaab.pdf Kaan, E. – Swaab, T. Y. (2002) “The brain circuitry of syntactic comprehension”, Trends in Cognitive Sciences, vol. 6, Issue 8, 350-356.]
 
{{Fraktal}}
[[Category:Mathematical logic]]
{{Logika matematika}}
[[Category:Theory of computation]]
[[Category:Programming idioms]]
[[Category:Recursion| ]]
[[Category:Self-reference]]
 
[[Kategori:Rekursi| ]]
[[ar:استدعاء ذاتي]]
[[Kategori:Logika matematika]]
[[bg:Рекурсия]]
[[Kategori:Teori komputasi]]
[[bn:পুনরাবৃত্তি (রিকার্শন)]]
[[Kategori:Idioma pemrograman]]
[[ca:Recursivitat]]
[[Kategori:Referensi-diri]]
[[cs:Rekurze]]
[[da:Rekursiv]]
[[de:Rekursion]]
[[el:Αναδρομή]]
[[en:Recursion]]
[[es:Recursión]]
[[eo:Rikuro]]
[[fr:Récursivité]]
[[hi:पुनर्गमनवाद]]
[[hr:Rekurzija]]
[[io:Rekurso]]
[[ia:Recursion]]
[[is:Endurkvæmt fall]]
[[he:רקורסיה]]
[[lt:Rekursija]]
[[hu:Rekurzió]]
[[nl:Recursie]]
[[ja:再帰]]
[[nn:Rekursjon]]
[[no:Rekursjon]]
[[pl:Rekurencja]]
[[pt:Recursividade]]
[[ro:Recursivitate]]
[[rue:Рекурзія]]
[[ru:Рекурсия]]
[[sa:पुनर्गमनवाद]]
[[simple:Recursion]]
[[sk:Rekurzia (matematika)]]
[[sl:Rekurzija]]
[[sr:Рекурзија]]
[[sh:Rekurzija]]
[[fi:Rekursio]]
[[sv:Rekursion]]
[[ta:சுழல்]]
[[th:การเรียกซ้ำ]]
[[tg:Рекурсия]]
[[tr:Özyineleme]]
[[uk:Рекурсія]]
[[ur:Recursion]]
[[zh:递归]]
Diperoleh dari "https://wiki-indonesia.club/wiki/Rekursi"