Jabarkan Definisi formal dari rekursi dari Rekursi

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

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