Sebutkan Hal yang perlu diperhatikan ketika membuat fungsi rekursi, saat melakukan pengkodean?

Sebutkan Hal yang perlu diperhatikan ketika membuat fungsi rekursi, saat melakukan pengkodean?

Hal yang harus diperhatikan ketika membuat fungsi rekursif adalah bahwa fungsi 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 rekursif sebagai fungsi 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)

Baca Juga :  Complete the sentences with a form of the verb in parentheses. Three hundred and fifty years ago, people (1. make) /made/ their own clothes. They (2. have, not) _____ machines for making clothes. There (3. be, not) _____ any clothing factories. People (4. tear) _____ homemade clothes that were sewn by hand. Today, very few people (5. make) _____ their own clothes. Clothing (6. come) _____ ready-made from factories. People (7. buy) _____ almost all their clothes from stores. The modern clothing industry (8. be) _____ international. As a result, people from different countries often (9. wear) _____ similar clothes. For example, people in many different countries throughout the world (10. wear) _____ jeans and t-shirts. However, some regional differences in clothing still (11. exist) _____ for instance, people of the Arabian deserts (12. wear) _____ loose, flowing lobes to protect themselves from the heat of the sun. In parts of Northern Europe, fur hats (13. be) _____ common in the winter. In the future, there (14. be, probably) _____ fewer and fewer differences in clothing. People throughout the world (15. wear) _____ clothes from the same factories. (16. We all, dress) _____ in the future? TV shows and movies about the future often (17. show) _____ everybody in a uniform of some kind. What (18. you, think) _____? Number 12

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.

 

Pelajari lebih lanjut

Pelajari lebih lanjut di Google News

ilmuantekno.com