Jabarkan Rekursi fungsional dari Rekursi

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.

Pembuktian yang mengikutkan definisi rekursif

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.