Rekursif
Salah satu konsep paling dasar dalam ilmu komputer dan pemrograman adalah pengunaan fungsi sebagai abstraksi untuk kode-kode yang digunakan berulang kali. Kedekatan ilmu komputer dengan matematika juga menyebabkan konsep-konsep fungsi pada matematika seringkali dijumpai. Salah satu konsep fungsi pada matematika yang ditemui pada ilmu komputer adalah fungsi rekursif: sebuah fungsi yang memanggil dirinya sendiri.Kode berikut memperlihatkan contoh fungsi rekursif, untuk menghitung hasil kali dari dua bilangan:
def kali(a, b):
return a if b == 1 else a + kali(a, b - 1)
b
bukan 1
, fungsi akan terus memanggil perintah a + kali(a, b - 1)
, yang tiap tahapnya memanggil dirinya sendiri sambil mengurangi nilai b
. Mari kita coba panggil fungsi kali
dan uraikan langkah pemanggilannya:
kali(2, 4)
-> 2 + kali(2, 3)
-> 2 + (2 + kali(2, 2))
-> 2 + (2 + (2 + kali(2, 1)))
-> 2 + (2 + (2 + 2))
-> 2 + (2 + 4)
-> 2 + 6
-> 8
def faktorial(n):
return n if n == 1 else n * faktorial(n - 1)
faktorial
memiliki cara kerja yang sama dengan fungsi kali
. Mari kita panggil dan lihat langkah pemanggilannya:
faktorial(5)
-> 5 * faktorial(4)
-> 5 * (4 * faktorial(3))
-> 5 * (4 * (3 * faktorial(2)))
-> 5 * (4 * (3 * (2 * faktorial(1))))
-> 5 * (4 * (3 * (2 * 1)))
-> 5 * (4 * (3 * 2))
-> 5 * (4 * 6)
-> 5 * 24
-> 120
faktorial
dan kali
, kita dapat melihat bagaimana fungsi rekursif memiliki dua ciri khas:- Fungsi rekursif selalu memiliki kondisi yang menyatakan kapan fungsi tersebut berhenti. Kondisi ini harus dapat dibuktikan akan tercapai, karena jika tidak tercapai maka kita tidak dapat membuktikan bahwa fungsi akan berhenti, yang berarti algoritma kita tidak benar.
- Fungsi rekursif selalu memanggil dirinya sendiri sambil mengurangi atau memecahkan data masukan setiap panggilannya. Hal ini penting diingat, karena tujuan utama dari rekursif ialah memecahkan masalah dengan mengurangi masalah tersebut menjadi masalah-masalah kecil.
Analisis Algoritma Rekursif¶
Melakukan analisis untuk algoritma rekursif pada dasarnya sama dengan melakukan analisis terhadap algoritma imparatif lain. Perbedaan utama pada algoritma rekursif ialah kita tidak dapat secara langsung melihat berapa kali bagian rekursif dari algoritma akan dijalankan. Pada algoritma yang menggunakan perulangan for misalnya, kita dapat langsung menghitung jumlah perulangan untuk menghitung total langkah yang dibutuhkan. Dalam algoritma rekursif, jumlah perulangan tidak secara eksplisit bisa didapatkan karena informasi yang kita miliki adalah kapan algoritma berhenti, bukan berapa kali kode dieksekusi.Misalnya, algoritma perhitungan faktorial yang telah dibahas sebelumnya:
def faktorial(n):
return n if n == 1 else n * faktorial(n - 1)
n == 1
. Informasi lain yang kita miliki adalah berkurangnya jumlah data pada setiap pemanggilan faktorial
. Bagaimana kita melakukan analisis algoritma ini? Cara termudahnya adalah dengan menggambarkan fungsi matematika dari faktorial terlebih dahulu:faktorial(n)={1n∗faktorial(n−1)remainder(x,y))if n=1if n>1
Maka dapat disimpulkan bahwa fungsi faktorial memiliki kompleksitas
Kesimpulan
Fungsi rekursif merupakan fungsi yang memanggil dirinya sendiri. Terdapat dua komponen penting dalam fungsi rekursif, yaitu kondisi kapan berhentinya fungsi dan pengurangan atau pembagian data ketika fungsi memanggil dirinya sendiri. Optimasi fungsi rekursif dapat dilakukan dengan menggunakan teknik tail call, meskipun teknik ini tidak selalu diimplementasikan oleh semua bahasa pemrograman.Selain sebagai fungsi, konsep rekursif juga terkadang digunakan untuk struktur data seperti binary tree atau list.
0 Comments
EmoticonEmoticon