Rekursi: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
k r2.7.3) (bot Menambah: ml:സ്വാവർത്തനം |
Sinkronisasi dengan en:Recursion rev. 2013-01-25 17:16:34. |
||
Baris 7:
Sebagai contohnya, saat dua cermin berada paralel antara satu dengan yang lain, gambar yang tertangkap adalah suatu bentuk rekursi tak-terbatas.
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]],
Secara spesifik hal ini mendefinisikan suatu instansi tak-terbatas (nilai fungsi), menggunakan ekpresi terbatas yang
Istilah ini juga digunakan secara umum untuk menjelaskan suatu proses pengulangan objek dengan cara kesamaan-diri.
== Definisi formal dari rekursi ==
[[File:Screenshot Recursion via vlc.png|thumb|Rekursi dalam program perekaman layar,
Dalam [[matematika]] dan [[ilmu komputer]], kelas dari objek atau metode memperlihatkan perilaku rekursif bila mereka dapat didefinisikan oleh dua properti berikut:
Baris 41:
=== Definisi informal ===
Rekursi adalah suatu proses
Prosedur yang melakukan rekursi disebut dengan 'rekursif'.
Baris 51:
Rekursi 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
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.
Baris 64:
== 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
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'',
Konsep ini, yang menantang ide Chomsky bahwa rekursi hanyalah sifat yang membedakan komunikasi manusia dan hewan, sekarang sedang diperdebatkan.
Andrew Nevins, David Pesetsky dan Cilene Rodrigues berdebat melawan proposal tersebut.
Baris 108 ⟶ 109:
}}</ref>
Sebuah variasi ditemukan dalam [[Belakang-buku indeks|indeks]] pada halaman 269 dari beberapa edisi buku Kernighan dan Ritchie
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
Lelucon yang lain adalah "Untuk memahami rekursi, anda harus memahami rekursi."<ref name=Hunter/>
Baris 126 ⟶ 127:
==== Contoh: bilangan asli ====
{{see also|Closure (matematika)}}
Contoh kanonikal dari himpunan yang didefinisikan secara rekursif yaitu diberikan oleh [[bilangan asli]]:
Baris 149 ⟶ 152:
Supaya definisi dapat berguna, ia harus menggunakan nilai yang terdefinisi secara tak-rekursif, dalam kasus ini ''F''(0) = 0 dan ''F''(1) = 1.
Fungsi rekursif terkenal yaitu [[fungsi Ackermann]] yang
=== Pembuktian yang mengikutkan definisi rekursif ===
Baris 165 ⟶ 168:
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 algoritma penting.
''Divide and conquer'' menyediakan pendekatan atas-bawah dalam pemecahan masalah,
Pendekatan sebaliknya yaitu [[pemrograman dinamis]].
Pendekatan ini menyelesaikannya secara bawah-atas,
Contoh klasik dari rekursi adalah definisi dari fungsi [[faktorial]], diberikan dalam kode C:
Baris 174 ⟶ 177:
unsigned int factorial(unsigned int n)
{
if (!n
return 1;
} else {
return n * factorial(n-1);
}
}
</source>
Baris 198 ⟶ 202:
Dalam [[teori himpunan]], ini adalah teorema yang menjamin bahwa fungsi yang terdefinisi secara rekursif itu ada.
Diberikan suatu himpunan ''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> (
:<math>F(0) = a</math>
:<math>F(n + 1) = f(F(n))</math>
Baris 216 ⟶ 220:
:<math>G(n + 1) = f(G(n))</math>
Ia dapat dibuktikan dengan [[induksi matematika]] bahwa
Baris 248 ⟶ 252:
== Bibliografi ==
* {{cite journal|first=Edsger W.|last=
*{{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 }}
Baris 264 ⟶ 268:
<div style="-moz-column-count:3; column-count:3;">
* [[
* [[Rekursi Course-of-values]]
* [[Ketakterbatasan digital]]
* [[
* [[Perulangan Takterbatas]]
* [[Infinitisme]]
Baris 278 ⟶ 282:
* [[Reentrant (subroutine)]]
* [[Referensi-diri]]
* [[
* [[
* [[Formula Tupper
* [[Turtles all the way down]]
</div>
| |||