Rekursi
0 ada dalam N displaystyle mathbb N  jika n ada dalam N displaystyle mathbb N , maka n + 1 ada dalam N displaystyle mathbb N  Himpunan dari bilangan asli adalah himpunan terkecil yang memenuhi dua properti sebelumnya.
Contoh menarik lainnya adalah himpunan dari semua proposisi "benar terjangkau" dalam suatu sistem aksioma.
Jika suatu proposisi adalah sebuah aksioma, maka ia adalah suatu proposisi benar terjangkau. Jika suatu proposisi dapat dihasilkan dari proposisi benar terjangkau dengan menggunakan aturan-aturan inferensi, maka ia adalah proposisi benar terjangkau. Himpunan dari proposisi benar-terjangkau adalah himpunan terkecil dari proposisi yang memenuhi kondisi tersebut.
Himpunan ini disebut 'proposisi benar terjangkau' karena dalam pendekatan non-konstruktif terhadap fondasi matematika, himpunan dari proposisi benar bisa lebih besar daripada himpunan yang dibangun secara rekursif dari aksioma-aksioma dan aturan-aturan inferensi. Lihat juga Teorema ketaklengkapan Godel.
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.
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.
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).
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.
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.
Dalam teori himpunan, ini adalah teorema yang menjamin bahwa fungsi yang terdefinisi secara rekursif itu ada. Diberikan suatu himpunan X, sebuah elemen a dari X dan sebuah fungsi f: X  X displaystyle f:Xrightarrow X, teorema menyatakan bahwa ada fungsi unik F: N  X displaystyle F:mathbb N rightarrow X (dengan N displaystyle mathbb N  menunjukkan himpunan dari bilangan asli termasuk nol) sehingga
F (0) = a displaystyle F (0)=a F (n + 1) = f (F (n)) displaystyle F (n+1)=f (F (n))
Ambil dua fungsi F: N  X displaystyle F:mathbb N rightarrow X dan G: N  X displaystyle G:mathbb N rightarrow X sehingga:
F (0) = a displaystyle F (0)=a G (0) = a displaystyle G (0)=a F (n + 1) = f (F (n)) displaystyle F (n+1)=f (F (n)) G (n + 1) = f (G (n)) displaystyle G (n+1)=f (G (n))
Ia dapat dibuktikan dengan induksi matematika bahwa F (n) = G (n) displaystyle F (n)=G (n) untuk semua bilangan asli n:
Kasus dasar: F (0) = a = G (0) displaystyle F (0)=a=G (0) sehingga persamaan memenuhi untuk n = 0 displaystyle n=0.
Lang Induktif: Misalkan F (k) = G (k) displaystyle F (k)=G (k) untuk beberapa k  N displaystyle kin mathbb N . Maka F (k + 1) = f (F (k)) = f (G (k)) = G (k + 1). displaystyle 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) displaystyle F (n)=G (n) untuk semua n  N displaystyle nin mathbb N .
Rasio Golden:  = 1 + (1/) = 1 + (1/(1 + (1/(1 + 1/...)))) displaystyle phi =1+(1/phi)=1+(1/(1+(1/(1+1/...)))) Faktorial: n! = n (n  1)! = n (n  1)  1 displaystyle n!=n (n-1)!=n (n-1)cdots 1 Bilangan Fibonacci: f (n) = f (n  1) + f (n  2) displaystyle f (n)=f (n-1)+f (n-2) Bilangan
Catalan: C 0 = 1 displaystyle C_0=1, C n + 1 = (4 n + 2) C n/(n + 2) displaystyle C_n+1=(4n+2) C_n/(n+2) Perhitungan suku bunga Menara Hanoi Fungsi Ackermann
CS1 maint: Multiple names: authors list (link) CS1 maint: Multiple names: authors list (link)- menjelaskan pengerjaan dari corecursion. CS1 maint: Multiple names: authors list (link) CS1 maint: Multiple names: authors list (link) CS1 maint: Multiple names: authors list (link), bagian pertama dari teori himpunan.
Korekursi Rekursi Course-of-values Ketakterbatasan digital Kombinator titik tetap Perulangan Takterbatas Infinitisme Fungsi Iterasi Mise en abyme Reentrant (subroutine) Referensi-diri Perulangan ganjil Rekursi buntut Formula Tupper Turtles all the way down
Transclusion error: En is only for use in File namespace. Use lang-en or en icon instead.- tutorial oleh Alan Gauld Transclusion error: En is only for use in File namespace. Use lang-en or en icon instead.- mengandung petunjuk untuk rekursi dalam Bahasa Formal, Linguistik, Matematika dan Ilmu Komputer Transclusion error: En is only for use in File namespace. Use lang-en or en icon instead. Transclusion error: En is only for use in File namespace. Use lang-en or en icon instead.