Hal yang harus diperhatikan ketika membuat fungsi rekursifadalah bahwafungsi tersebut harus memiliki “base case” (kondisi basis), atau disebut juga sebagai “stopping rule” (aturan untuk berhenti), yang membuat fungsi rekursif tersebut memiliki jumlah rekurens (pemanggilan terhadap dirinya sendiri) yang terbatas/berhingga.
Jika base case tidak dapat dicapai oleh sebuah fungsi rekursif, maka fungsi tersebut tidak akan berhenti, yang dapat menyebabkan stack overflow atau penggunaan memori yang berlebihan.
 

Pembahasan

Secara sederhana, kita dapat mengartikan fungsi rekursifsebagaifungsi yang memanggil dirinya sendiri. Sampai berapa kali dipanggil, tentu harus didefinisikan pada sebuah kondisi basis (base case) yang jelas.

Dua elemen utama dari fungsi rekursif adalah:

• base case, atau stopping rule, yang membuat fungsi berhenti dan mengembalikan nilai tertentu.
• recursive step, atau langkah rekursif, di mana fungsi tersebut memanggil dirinya sendiri dengan parameter fungsi yang berubah dalam setiap kali pemanggilan dan secara bertahap mengarah ke base case.

Salah satu contoh yang dapat diambil adalah fungsi faktorial. Dalam notasi matematis, untuk n bilangan bulat tak-negatif, n faktorial yang disimbolkan dengan n! didefinisikan sebagai relasi rekurens:

(Definisi di atas sudah mencakup kasus khusus untuk 0!.)

Karena kita memiliki definisi relasi rekurens tersebut, maka implementasi fungsi faktorial(n) dalam pemrograman merupakan translasi langsung dari notasi fungsional n! tersebut.
Dari definisi tersebut, base case atau stopping rule yang berlaku adalah ketika n = 0, dan recursive step memiliki bagian yang mengarahkan n menuju base case, yaitu (n – 1).

Dengan pseudocode, algoritma fungsi rekursif faktorial(n) dapat dirancang sebagai berikut.

function faktorial(n):
   if n = 0 then
       return 1
   end if
   return n * factorial(n - 1)

Catatan: Validasi nilai n dilakukan di luar fungsi tersebut.

Dalam bahasa pemrograman Python, kita dapat mengimplementasikannya dengan:

def faktorial(n):
   return n if n == 0 else n * faktorial(n - 1)

Misalkan n = 4, tracing terhadap faktorial(4) adalah sebagai berikut.

faktorial(4)
 ⇒ 4 * faktorial(3)
 ⇒ 4 * (3 * faktorial(2))
 ⇒ 4 * (3 * (2 * faktorial(1)))
 ⇒ 4 * (3 * (2 * (1 * faktorial(0))))
 ⇒ 4 * (3 * (2 * (1 * 1)))
 ⇒ 4 * (3 * (2 * 1))
 ⇒ 4 * (3 * 2)
 ⇒ 4 * 6
 ⇒ 24

Dapat kita amati bahwa fungsi faktorial(n) berhenti memanggil dirinya sendiri ketika parameternya mencapai nilai 0, yang merupakan nilai pada base case/ stopping rule.