Rekursi

Definisi informal

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..

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.
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 fungsional

Sebuah fungsi bisa didefinisikan sebagai bagian dari dirinya sendiri. Contoh yang terkenal adalah urutan bilangan Fibonacci: F(n) = F(n − 1) + F(n − 2).
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.
Fungsi rekursif terkenal yaitu fungsi Ackermann yang mana—tidak seperti urutan Fibonacci—tidak dapat dengan mudah diekspresikan tanpa rekursi.

Pembuktian yang mengikutkan definisi rekursif

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 secara luas digunakan untuk menurunkan pembuktian dalam logika matematika dan ilmu komputer.

Optimisasi rekursif

Pemrograman dinamis adalah suatu pendekatan terhadap optimisasi yang menempatkan ulang suatu permasalahan multiperiode atau tahapan dalam bentuk rekursif.
Kunci jawaban dari pemrograman dinamis adalah persamaan Bellman, yang menuliskan nilai dari permasalahan optimisasi pada waktu awal (atau langkah awal) berkenaan dengan nilainya pada waktu kemudian (atau langkah selanjutnya).

Rekursi dalam ilmu komputer

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 algoritme penting.
Divide and conquer menyediakan pendekatan atas-bawah dalam pemecahan masalah, dengan permasalahan diselesaikan dengan menyelesaikan instansi yang lebih kecil.
Pendekatan sebaliknya yaitu pemrograman dinamis.
Pendekatan ini menyelesaikannya secara bawah-atas, dengan permasalahan diselesaikan dengan menyelesaikan instansi yang lebih besar, sampai ukuran yang diinginkan dicapai.
Contoh klasik dari rekursi adalah definisi dari fungsi faktorial, diberikan dalam kode C:
unsigned int factorial(unsigned int n){
  if (n == 0) {
    return 1;
  } else {
    return n * factorial(n-1);
  }}
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.
Rekursi dalam pemrograman komputer dicontohkan saat sebuah fungsi didefinisikan dalam bentuk sederhana, bahkan versi terkecil dari dirinya.
Solusi dari permasalahan kemudian dirancang dengan menggabungkan solusi-solusi yang didapat dari versi sederhana dari permasalahan.
Salah satu contoh aplikasi rekursi yaitu dalam parsing untuk bahasa pemrograman.
Keuntungan utama dari rekursi adalah suatu 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 algoritme memiliki kelebihan dan kekurangan.
Kelebihan utamanya adalah biasanya kesederhanaan.
Kekurangan utamanya adalah terkadang algoritme tersebut membutuhkan memori yang sangat banyak jika kedalaman rekursi sangat besar.