Recursion

(RECURSION) 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, tapi 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.

Definisi formal dari rekursi

Rekursi dalam program perekaman layar, dengan 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:

Sebuah kasus (atau beberapa kasus) dasar sederhana
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 rekursi).

Bilangan Fibbonaci adalah contoh klasik dari 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 Paenamo 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 Houfstater selain anda; lalu tanya dia rekursi itu apa.”

Objek matematika yang didefinisikan secara rekursif termasuk fungsi, himpunan, dan terutama sekali fraktal.

Contoh-contoh

Beberapa relasi perulangan umum yaitu: