Rekursi: Perbedaan antara revisi

{{No footnotes|date=February 2010}}

 

 

Istilah ini memiliki makna beragam bergantung kepada ragam disiplin mulai dari [[linguistik]] sampai [[logika]].

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.

 

 

 

Dalam [[matematika]] dan [[ilmu komputer]], kelas dari objek atau metode memperlihatkan perilaku rekursif bila mereka dapat didefinisikan oleh dua properti berikut:

# Sejumlah aturan yang mengurangi kasus-kasus lainnya sampai ke kasus dasarnya.

 

* [[Orang tua]] seseorang adalah [[leluhur]] seseorang (''kasus dasar'').

 

 

* Fib(0) adalah 0 [kasus dasar]

 

Banyak aksioma matematika berdasarkan aturan-aturan rekursif.

Dengan kasus dasar ini dan aturan rekursif, seseorang dapat membuat himpunan dari semua bilangan asli.

 

 

 

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.

 

Andrew Nevins, David Pesetsky dan Cilene Rodrigues berdebat melawan proposal tersebut.

<ref>{{cite journal

| pages = 671–681

}}</ref>

 

Tanpa rekursi, bahasa tidak memiliki 'diskrit tak-terbatas' dan tidak dapat menanamkan kalimat menjadi tak-terbatas (dengan suatu efek '[[Boneka Matryoshka|Sarang boneka Rusia]]').

 

 

 

Jalannya sebuah prosedur mengikuti aturan-aturan dan melakukan langkah-langkah.

 

Misalnya, suatu resep bisa mengacu pada memasak sayuran, yang merupakan prosedur yang kemudian membutuhkan memanaskan air, dan seterusnya.

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

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.

Ia tidak ada di edisi pertama dari "The C Programming Language".

 

 

 

== Rekursi dalam matematika ==

[[Image:Sierpinski Triangle.svg|right|thumb|250px|[[Segitiga Sierpinski]]—sebuah rekursi terbatas dari segitiga membentuk suatu [[jeruji]] geometris.]]

 

{{Main|Definisi rekursif}}

 

==== Contoh: 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>

 

 

 

Lihat juga [[Teorema ketaklengkapan Godel]].

 

=== Rekursi fungsional ===

 

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.

 

 

 

=== Optimisasi rekursif ===

 

[[Pemrograman Dinamis]] adalah suatu pendekatan terhadap [[optimisasi (matematika)|optimisasi]] yang menempatkan ulang suatu permasalahan multiperiode atau tahapan dalam bentuk rekursif.

 

== Rekursi dalam ilmu komputer ==

{{Main|Rekursi (ilmu komputer)}}

 

Pendekatan sebaliknya yaitu [[pemrograman dinamis]].

 

Contoh klasik dari rekursi adalah definisi dari fungsi [[faktorial]], diberikan dalam kode C:

</source>

 

 

Solusi dari permasalahan kemudian dirancang dengan menggabungkan solusi-solusi yang didapat dari versi sederhana dari permasalahan.

 

[[Relasi perulangan]] adalah persamaan-persamaan untuk menentukan satu atau lebih urutan-urutan secara rekursif.

== Teorema rekursi ==

 

:<math>F(0) = a</math>

:<math>F(n + 1) = f(F(n))</math>

{{col-begin}}

{{col-break}}

*[[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>

*[[Fungsi Ackermann]]

{{col-end}}

*{{cite book | author = Kernighan, B.; Ritchie, D. | title=The C programming Language | publisher=Prentice Hall | year = 1988 | isbn = 0-13-110362-8 }}

*{{cite book | author=Stokey, Nancy,; Robert Lucas; Edward Prescott | title=Recursive Methods in Economic Dynamics | publisher=Harvard University Press | year=1989 | isbn=0674750969}}

 

== Lihat juga ==

 

<div style="-moz-column-count:4; column-count:4;">

* [[Corecursion]]

* [[Fixed point combinator]]

* [[Mise en abyme]]

<!--

Including [[Recursion]] in this list will not display correctly, and

-->

* [[Reentrant (subroutine)]]

* [[Strange loop]]

* [[Tail recursion]]

*[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.]

 

 

[[ar:استدعاء ذاتي]]