Rekursi
Rekursi adalah proses pengulangan sesuatu dengan cara kesamaan-diri. 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, yang mengacu kepada suatu metode mendefinisikan 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, tetapi dengan suatu cara sehingga tidak ada perulangan atau
keterkaitan tak-terbatas dapat terjadi. Istilah ini juga digunakan secara umum untuk menjelaskan suatu proses pengulangan objek dengan cara kesamaan-diri.
Dalam matematika dan ilmu komputer, kelas dari objek atau metode memperlihatkan perilaku rekursif bila mereka dapat didefinisikan oleh dua properti berikut:
Sebuah kasus (atau beberapa kasus) dasar sederhana Sejumlah aturan yang mengurangi kasus-kasus lainnya sampai ke kasus dasarnya.
Orang tua seseorang adalah leluhur seseorang (kasus dasar). Orang tua dari suatu leluhur juga merupakan leluhur-nya (langkah rekursi).
Fib (0) adalah 0 [kasus dasar] Fib (1) adalah 1 [kasus dasar] Untuk semua integer n > 1: Fib (n) adalah (Fib (n-1) + Fib (n-2)) [definisi rekursif]
Banyak aksioma matematika berdasarkan aturan-aturan rekursif. Sebagai contohnya, definisi formal dari bilangan asli pada Aksioma Peano dapat dideskripsikan sebagai: 0 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 rekursi, pertama anda harus memahami rekursi." Atau mungkin yang lebih akurat, dari Andrew Plotkin: "Jika anda telah mengetahui apa itu rekursi, cukup ingat jawabannya. Kalau tidak, cari orang yang berdiri paling dekat dengan Douglas Hofstadter selain anda; lalu tanya dia rekursi itu apa."
Rekursi adalah suatu proses dengan salah satu langkah dalam prosedur tersebut menjalankan prosedur itu sendiri. Prosedur yang melakukan rekursi disebut dengan 'rekursif'.
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..
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.
Rekursi dalam linguistik membolehkan 'diskrit tak-terbatas' dengan menanamkan frasa dalam tipe frasa yang sama dalam suatu struktur hierarki. Tanpa rekursi, bahasa tidak memiliki 'diskrit tak-terbatas' dan tidak dapat menanamkan kalimat menjadi tak-terbatas (dengan suatu efek '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 tetapi sangat produktif, dengan gerakan-gerakan baru diciptakan lewat sejarah.
Rekursi terkadang digunakan secara humor dalam buku ilmu komputer, pemrograman, filsafat, atau matematika. Adalah hal yang biasa bagi buku-buku tersebut untuk memasukan lelucon dalam glosarium-nya di antara barisan:
Sebuah variasi ditemukan di halaman 269 dalam indeks dari beberapa edisi buku Kernighan dan Ritchie The C Programming Language; 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." 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 singkatan dari "Wine Is Not an Emulator", GNU singkatan dari "GNU's not Unix".