Rekursi

Rekursif adalah proses pengulangan item dengan cara kesamaan-diri. Sebagai contohnya, saat dua cermin berada paralel antara satu dengan yang lain, gambar yang tertangkap adalah suatu bentuk rekursif tak-terbatas. Istilah ini memiliki makna beragam bergantung kepada ragam disiplin mulai dari linguistik sampai logika. Penggunaan paling umum dari rekursif yaitu dalam matematika dan ilmu komputer, dimana ia mengacu kepada suatu metoda mendefinisikan fungsi yang mana fungsi tersebut menggunakan definisinya sendiri. Secara spesifik hal ini mendefinisikan suatu instansi tak-terbatas (nilai fungsi), menggunakan ekpresi terbatas yang mana beberapa instansi bisa merujuk kepada instansi lainnya, tapi dengan suatu cara dimana tidak ada perulangan atau keterkaitan tak-terbatas dapat terjadi. Istilah ini juga digunakan secara umum untuk menjelaskan suatu proses pengulangan objek dengan cara yang sama.

Suatu bentuk rekursif yang dikenal dengan Efek Droste. Wanita dalam gambar ini memegang suatu objek yang memiliki gambar kecil-nya yang memegang objek yang sama, yang juga memiliki gambar kecil dirinya sendiri yang memegang objek yang sama, dan seterusnya.

Definisi formal dari rekursif

Rekursif dalam program perekaman layar, dimana 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:

1. Suatu kasus (atau beberapa kasus) dasar sederhana, dan
2. 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 rekursif).

Bilangan Fibonacci adalah contoh klasik dari rekursif:

• 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, definiso formal dari bilangan asli dalam teori himpunan berbunyi: 1 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 rekursif, pertama anda harus memahami rekursif." Atau mungkin yang lebih akurat, dari Andrew Plotkin: "Jika anda telah mengetahui apa itu rekursif, cukup ingat jawabannya. Kalau tidak, cari orang yang berdiri paling dekat dengan Douglas Hofstadter dari anda; lalu tanya dia rekursif itu apa."

Objek matematis yang didefinisikan secara rekursif termasuk fungsi, himpunan, dan khususnya fraktal.

Rekursif dalam bahasa

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.

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. Konsep ini, yang menantang ide Chomsky bahwa rekursif hanyalah sifat yang membedakan komunikasi manusia dan hewan, sekarang sedang diperdebatkan. Andrew Nevins, David Pesetsky dan Cilene Rodrigues berdebat melawan proposal tersebut. 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)

Rekursif dalam linguistik membolehkan 'diskrit tak-terbatas' dengan menanamkan frase dalam tipe frase yang sama dalm struktur hirarki. 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 - adalah faktanya terbatas. Dia menyamakannya dengan permainan terbatas catur, yang memiliki sejumlah pergerakan terbatas tapi sangat produktir, 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; dua contoh berikut bisa ditemukan dalam suatu glosarium:

Rekursi

Lihat "Rekursi".

Rekursi

Jika anda masih tidak mengerti, lihat "Rekursi".

Sebuah variasi ditemukan dalam indeks pada halaman 269 dari beberapa edisi buku Kernighan dan Ritchie "The C Programming Language"; dimana isi indeks secara rekursif mengacu kepada dirinya sendiri:

rekursi 86, 139, 141, 182, 202, 269

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 "Did you mean: Recursion."

Akronim rekursif juga dapat sebagai contoh dari humor rekursif. PHP, contohnya, singkatan dari "PHP Hypertext Preprocessor" dan WINE, contohnya, singkatan dari "Wine Is Not an Emulator."

Rekursi dalam matematika

Berkas:Sierpinski Triangle.svg

Segitiga Sierpinski—sebuah rekursi terbatas dari segitiga membentuk suatu jeruji geometris.

Set-set yang didefinisikan secara rekursif

Artikel utama: Definisi rekursif

Contoh: bilangan asli

Contoh kanonikal dari set yang didefinisikan secara rekursif yaitu diberikan oleh bilangan asli:

1 ada dalam $\mathbb {N}$

jika n ada dalam $\mathbb {N}$, maka n + 1 ada dalam $\mathbb {N}$

Set dari bilangan asli adalah set terkecil yang memenuhi dua properti sebelumnya.

Contoh: set dari proprosisi benar terjangkau

Contoh menarik lainnya adalah set dari semua proposisi "benar terjangkau" dalam suatu sistem aksioma.

• Jika suatu proposisi adalah sebuah aksiom, maka ia adalah suatu 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.

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. Lihat juga Teorema ketaklengkapan Godel.

Rekursi fungsional

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

Pembuktian mengikutkan definisi rekursif

Menerapkan teknik standar dari pembuktian dengan kasus untuk mendefinisikan secara rekursif suatu set 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 Dinamis adalah suatu pendekatan terhadap optimisasi yang menempatkan ulang suatu permasalahan multiperiode atau tahapan dalam bentuk rekursif. Hasil kunci dari pemrograman dinamis adalah persamaan Bellman, yang menulikan nilai dari permasalahan optimisasi pada waktu awal (atau langkah awal) daripada nilainya pada waktu kemudian (atau langkah selanjutnya).

Rekursi dalam ilmu komputer

Artikel utama: Rekursi (ilmu komputer)

Metoda umum dari penyederhanaan adalah dengan membagi suatu permasalah menjadi sub-permasalahan dengan tipe yang sama. Sebagai sebuah teknik pemrograman komputer, hal ini disebut divide and conquer dan merupakan kunci dari perancangan berbagai algoritma penting. Divide and conquer menyediakan pendekatan atas-bawah dalam pemecahan masalah, dimana permasalah diselesaikan dengan menyelesaikan instan yang lebih kecil. Pendekatan sebaliknya yaitu pemrograman dinamis. Pendekatan ini menyelesaikannya secara bawah-atas, dimana permasalahan diselesaikan dengan menyelesaikan instan 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 <= 1) 
    return 1;
  else
    return n * factorial(n-1);
}

Fungsi tersebut memanggilnya 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 makan sederhana, bahkan versi terkecil dari dirinya. Solusi dari permasalahan kemudian dirancang dengan menggabungkan solusi-solusi yang didapat dari versi sederhana dari permasalahan. Saah satu contoh aplikasi rekursi yaitu dalam parsing untuk bahasa pemrograman. Keuntungan utama dari rekursi adalah set tak-terbatas dari kalimat yang memungkinkan, perancangan atau data lainnya dapat didefinisikan, diurai atau dihasilkan dengan suatu program komputer 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 algoritma memiliki kelebihan dan kekurangan. Kelebihan utamanya adalah biasanya kesederhanaan. Kekurangan utamanya adalah terkadang algoritma tersebut membutuhkan memori yang sangat banyak jika kedalaman rekursi sangat besar.

Teorema rekursi

Dalam teori set, ini adalah teorema yang menjamin bahwa fungsi yang terdefinisi secara rekursif itu ada. Diberikan suatu set X, sebuah elemen a dari X dan sebuah fungsi $f:X\rightarrow X$, teorema menyatakan bahwa ada fungsi unik $F:\mathbb {N} \rightarrow X$ (dimana $\mathbb {N}$ menunjukkan set dari bilangan asli termasuk nol) sehingga

$F(0)=a$

$F(n+1)=f(F(n))$

untuk setiap bilangan asli n.

Pembuktian keunikan

Ambil dua fungsi $F:\mathbb {N} \rightarrow X$ dan $G:\mathbb {N} \rightarrow X$ sehingga:

$F(0)=a$

$G(0)=a$

$F(n+1)=f(F(n))$

$G(n+1)=f(G(n))$

dimana a adalah sebuah elemen dari X.

Ia dapat dibuktikan dengan induksi matematika bahwa $F(n)=G(n)$ untuk semua bilangan asli n:

Kasus dasar: $F(0)=a=G(0)$ sehingga persamaan memenuhi untuk $n=0$.

Langkah Induktif: Misalkan $F(k)=G(k)$ untuk beberapa $k\in \mathbb {N}$. Maka $F(k+1)=f(F(k))=f(G(k))=G(k+1).$

Karenanya F(k) = G(k) menyiratkan F(k+1) = G(k+1).

Dengan induksi, $F(n)=G(n)$ untuk semua $n\in \mathbb {N}$.

Contoh-contoh

Beberapa relasi perulangan umum yaitu:

• Golden Rasio: φ = 1 + (1/φ)... mengingat bahwa φ = 1 + (1/φ) then ... φ = 1 + (1/(1+(1/1+1/...)
• Faktorial: $n!=n(n-1)!=n(n-1)\cdots 1$
• Bilangan Fibonacci: $f(n)=f(n-1)+f(n-2)$
• Bilangan Catalan: $C_{0}=1$, $C_{n+1}=(4n+2)C_{n}/(n+2)$
• Komputasi senyawa suku bunga
• The Menara Hanoi
• Fungsi Ackermann

Bibliografi

• Johnsonbaugh, Richard (2004). Discrete Mathematics. Prentice Hall. ISBN 0-13-117686-2. 
• Hofstadter, Douglas (1999). Gödel, Escher, Bach: an Eternal Golden Braid. Basic Books. ISBN 0-465-02656-7. 
• Shoenfield, Joseph R. (2000). Recursion Theory. A K Peters Ltd. ISBN 1-56881-149-7. 
• Causey, Robert L. (2001). Logic, Sets, and Recursion. Jones & Bartlett. ISBN 0-7637-1695-2. 
• Cori, Rene; Lascar, Daniel; Pelletier, Donald H. (2001). Recursion Theory, Godel's Theorems, Set Theory, Model Theory. Oxford University Press. ISBN 0-19-850050-5. Pemeliharaan CS1: Banyak nama: authors list (link)
• Barwise, Jon; Moss, Lawrence S. (1996). Vicious Circles. Stanford Univ Center for the Study of Language and Information. ISBN 0-19-850050-5. Pemeliharaan CS1: Banyak nama: authors list (link) - menjelaskan pengerjaan dari corecursion.
• Rosen, Kenneth H. (2002). Discrete Mathematics and Its Applications. McGraw-Hill College. ISBN 0-07-293033-0. 
• Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2001). Introduction to Algorithms. Mit Pr. ISBN 0-262-03293-7. Pemeliharaan CS1: Banyak nama: authors list (link)
• Kernighan, B.; Ritchie, D. (1988). The C programming Language. Prentice Hall. ISBN 0-13-110362-8. Pemeliharaan CS1: Banyak nama: authors list (link)
• Stokey, Nancy,; Robert Lucas; Edward Prescott (1989). Recursive Methods in Economic Dynamics. Harvard University Press. ISBN 0674750969. Pemeliharaan CS1: Banyak nama: authors list (link)
• Hungerford (1980). Algebra. Springer. ISBN 978-0387905181. , bagian pertama dari teori set.

Lihat juga

• Church-Turing thesis
• Continuous predicate
• Corecursion
• Course-of-values recursion
• Droste effect
• Fixed point combinator
• Infinite loop
• Infinitism
• Iterated function
• Mise en abyme
• Primitive recursive function
• Reentrant (subroutine)
• Self-reference
• Strange loop
• Tail recursion
• Tupper's self-referential formula
• Turtles all the way down
• Viable System Model

Tautan Luar

• Recursion - tutorial oleh Alan Gauld
• A Primer on Recursion- mengandung petunjuk untuk rekursi dalam Bahasa Formal, Linguistik, Matematika dan Ilmu Komputer
• Zip Files All The Way Down
• Nevins, Andrew and David Pesetsky and Cilene Rodrigues. Evidence and Argumentation: A Reply to Everett (2009). Language 85.3: 671--681 (2009)
• Kaan, E. – Swaab, T. Y. (2002) “The brain circuitry of syntactic comprehension”, Trends in Cognitive Sciences, vol. 6, Issue 8, 350-356.