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)
Bagaimana cara kerja fungsi rekursif ini? Sederhananya, selama
nilai b bukan 1, fungsi akan terus memanggil perintaha + 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
Perhatikan bahwa sebelum melakukan penambahan program melakukan
pemanggilan fungsi rekursif terlebih dahulu sampai fungsi rekursif
mengembalikan nilai pasti (\(2\)). Setelah menghilangkan semua pemanggilan
fungsi, penambahan baru dilakukan, mulai dari nilai kembalian dari fungsi yang
paling terakhir. Mari kita lihat contoh fungsi rekursif lainnya, yang digunakan
untuk melakukan perhitungan faktorial:
def faktorial(n):
return n if n == 1 else n * faktorial(n - 1)
Fungsi 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
Dengan melihat kemiripan cara kerja serta kode dari fungsi faktorial dan kali, kita dapat
melihat bagaimana fungsi rekursif memiliki dua ciri khas:
1.
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.
2.
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.
Setiap fungsi rekursif yang ada harus memenuhi kedua persyaratan
di atas untuk memastikan fungsi rekursif dapat berhenti dan memberikan hasil.
Kebenaran dari nilai yang dihasilkan tentu saja memerlukan pembuktian dengan
cara tersendiri. Tetapi sebelum masuk ke analisa dan pembuktian fungsi
rekursif, mari kita lihat kegunaan dan contoh-contoh fungsi rekursif lainnya
lagi.
Fungsi Rekursif dan Iterasi
Pembaca yang jeli akan menyadari bahwa kedua contoh fungsi
rekursif yang diberikan sebelumnya, faktorial dankali, dapat diimplementasikan tanpa menggunakan fungsi rekursif.
Berikut adalah contoh kode untuk perhitungan faktorial tanpa menggunakan
rekursif:
def faktorial_iterasi(n):
hasil = 1
for i in range(1, n + 1):
hasil = hasil * i
return hasil
Dalam menghitung nilai faktorial menggunakan iterasi, kita meningkatkan nilai
hasil terus menerus, sampai mendapatkan jawaban yang tepat. Yang perlu kita
pastikan benar pada fungsi ini adalah berapa kali kita harus
meningkatkan nilai hasil. Jika jumlah peningkatan salah, maka hasil
akhir yang didapatkan juga akan salah.
Pendekatan iteratif berbeda dengan rekursif dalam hal ini: jika
pendekatan rekursif memecah-mecah masalah untuk kemudian menyelesaikan masalah
sedikit demi sedikit, pendekatan iteratif justru langsung mencoba menyelesaikan
masalah, tanpa memecah-mecahkan masalah tersebut menjadi lebih kecil terlebih
dahulu. Untungnya, baik teknik iterasi maupun rekursi sama-sama memiliki
tingkat ekspresi yang sama: segala hal yang dapat diselesaikan dengan itearsi
akan dapat diselesaikan dengan rekursif. Lalu, kapan dan kenapa kita harus
menggunakan rekursif?
Meskipun dapat menyelesaikan masalah yang sama, terdapat
beberapa permasalahan atau solusi yang lebih tepat diselesaikan dengan
menggunakan fungsi rekursif. Salah satu contoh dari masalah ini adalah
penelurusan data di dalam sebuah binary tree. Sebuah binary tree, yang dapat
didefinisikan sebagai sebuah pohon dengan jumlah cabang yang selalu dua, secara
alami adalah struktur data rekursif.
Binary Tree
Sebagai struktur rekursif, tentunya penelusuran binary tree akan
lebih mudah dilakukan secara rekursif dibandingkan iterasi. Hal ini sangat
kontras dengan, misalnya, pencarian karakter di dalam string. Sebagai data yang
disimpan secara linear, pencarian karakter dalam string akan lebih mudah untuk
dilakukan secara iteratif.
Untuk mempermudah ilustrasi, mari kita lakukan perbandingan
antara implementasi rekursif dan iteratif untuk masalah yang lebih cocok
diselesaikan dengan masing-masing pendekatan. Misalnya, implementasi algoritma euclidean untuk menghitung faktor
persekutuan terbesar (FPB) yang lebih cocok untuk diimplementasikan dengan
metode rekursif seperti berikut:
def gcd(x, y):
return x if y == 0 else gcd(y, x % y)
yang jika diimplementasikan dengan menggunakan iterasi adalah
sebagai berikut:
def gcd_iterasi(x, y):
while y != 0:
temp = y
y = x % temp
x = temp
return x
Jika dibandingkan dengan fungsi matematis dari algoritma
euclidean:
\[\begin{split}gcd(x, y) = \begin{cases} x & \text{if } y =
0 \\ gcd(y, remainder(x, y)) & \text{if } y > 0 \end{cases}\end{split}\]
tentunya implementasi secara rekursif lebih sederhana dan mudah
dimengerti dibandingkan dengan secara iterasi.
Sekarang mari kita lihat contoh algoritima yang lebih cocok
diimplementasikan secara iteratif, misalnya linear search. Implementasi standar
linear search secara iteratif adalah sebagai berikut:
def linear_search(lst, search):
for i in range(0, len(lst)):
if lst[i] == search:
print("Nilai ditemukan pada posisi:
" + str(i))
return 0
print("Nilai tidak ditemukan")
return -1
yang jika diimplementasikan secara rekursif akan menjadi:
def linear_search_rec(lst, search, pos):
if len(lst) <= pos:
print("Nilai tidak ditemukan.")
return -1
elif lst[pos] == search:
print("Nilai ditemukan di posisi:
" + str(pos))
return 0
else:
return linear_search_rec(lst, search, pos + 1)
Perhatikan bagaimana diperlukan lebih banyak pengecekan pada
fungsi rekursif, serta tambahan parameter pos yang berguna untuk menyimpan posisi pengujian dan
ditemukannya elemen yang dicari. Jika menggunakan iterasi variabelpos tidak
dibutuhkan lagi karena posisi ini akan didapatkan secara otomatis ketika sedang
menelusuri list. Dengan melihat jumlah argumen dan pengecekan yang harus
dilakukan, dapat dilihat bahwa implementasi linear search menjadi lebih
sederhana dan mudah dengan menggunakan metode iterasi.
Tail Call
Sesuai definisinya, dalam membuat fungsi rekursif pada satu
titik kita akan harus memanggil fungsi itu sendiri. Pemanggilan diri sendiri di
dalam fungsi tentunya memiliki konsekuensi tersendiri, yaitu pengunaan memori.
Dengan memanggil dirinya sendiri, secara otomatis sebuah fungsi akan memerlukan
memori tambahan, untuk menampung seluruh variabel baru serta proses yang harus
dilakukan terhadap nilai-nilai baru tersebut. Penambahan memori ini seringkali
menyebabkan stack overflow ketika terjadi pemanggilan rekursif
yang terlalu banyak.
Untuk menanggulangi kesalahan stack overflow ini, para
pengembang bahasa pemrograman mengimplementasikan apa yang dikenal dengan tail
call optimization. Dalam merancang dan menganalisa algoritma rekursif,
pengertian akan tail call optimization merupakan hal yang sangat penting. Jadi,
apa itu tail call?
Tail call merupakan pemanggilan fungsi sebagai perintah terakhir
di dalam fungsi lain. Sederhananya, ketika kita memanggil sebuah fungsi pada
bagian akhir dari fungsi lain, kita melakukan tail call, seperti pada kode di
bawah:
def fungsi(x):
y = x + 10
return fungsi_lain(y)
Pada kode di atas, pemanggilan fungsi_lain sebagai
kode terakhir yang dieksekusi oleh fungsi dapat dikatakan sebagai tail call. Ingat juga bahwa
pemanggilan tidak harus berada di akhir fungsi secara fisik. Yang penting
adalah bahwa kode terakhir yang dieksekusi adalah pemanggilan fungsi lain:
def tail_call(n):
if n == 0:
return fungsi_1(n + 1)
else:
return fungsi_2(n)
Pada contoh fungsi tail_call di atas, pemanggilan terhadap fungsi_1 maupun fungsi_2 adalah tail
call, meskipun pemanggilan fungsi_1 tidak berada pada akhri fungsi secara fisik. Bandingkan
dengan kode berikut:
def bukan_tail_call(n):
result = fungsi_lain(n % 5)
return result * 10
yang bukan merupakan tail call, karena kode terakhir yang
dieksekusi (result * 10e) adalah sebuah operasi, bukan pemanggilan fungsi. Cara kerja
ini tentunya juga dibawa ke fungsi rekursif, di mana:
def faktorial(n):
if n == 1:
return 1
else:
return n * faktorial(n - 1)
bukan merupakan tail call karena baik return 1 maupun n * faktorial(n - 1) bukanlah pemanggilan fungsi. Ingat bahwa n * faktorial(n - 1) merupakan operator perkalian, bukan pemanggilan
fungsi karena faktorial(n - 1)akan harus mengembalikan hasil terlebih dahulu agar bisa
dikalikan dengan n. Jika ingin membuat fungsi rekursif yang memanfaatkan tail
call, kita harus memastikan kode terakhir yang dieksekusi adalah fungsi lain,
tanpa operasi lanjutan. Misalnya, kita dapat menyimpan hasil kalkulasi sebagai
parameter, seperti berikut:
def faktorial_tc(n, r = 1):
if n <= 1:
return r
else:
return faktorial_tc(n - 1, n * r)
untuk memastikan terdapat tail call di dalam fungsi.
Implementasi algoritma rekursif disarankan untuk mengadopsi tail
call, karena natur dari fungsi rekursif yang memakan banyak memori. Tail call
optimization, jika diimplementasikan oleh bahasa pemrograman, akan mendeteksi
adanya tail call pada sebuah fungsi untuk kemudian dijalankan sebagai
perulangan untuk menghindari penggunaan memori berlebihan.
Bahasa pemrograman yang mendukung tail call optimization
biasanya adalah bahasa pemrograman fungsional seperti Haskell, LISP, Scheme,
dan Erlang. Python, sayangnya, tidak mendukung optimization.
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)
Salah satu informasi yang didapatkan di sini adalah kapan algoritma
berhenti melakukan rekursif, yaitu 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 faktorialterlebih
dahulu:
\[\begin{split}faktorial(n) = \begin{cases} 1 & \text{if } n
= 1 \\ n * faktorial(n - 1) remainder(x, y)) & \text{if } n > 1
\end{cases}\end{split}\]
Melalui fungsi matematika ini, kita dapat mulai melakukan
penurunan untuk fungsi perhitungan langkah fungsi \(faktorial\) untuk
kasus \(n > 1\):
\[\begin{split}f(n) & = 1 + f(n - 1) \\ & = 1 + 1 + f(n
- 2) \\ & = 1 + 1 + 1 + f(n - 3) \\ & ... \\ & = n + f(n -
k)\end{split}\]
Dan tentunya kita dapat mengabaikan penambahan langkah \(n\) di
awal, serta dengan syarat bahwa fungsi berhenti ketika \(n - k = 1\):
\[\begin{split}n - k & = 1 \\ k & = n - 1
\\\end{split}\]
Maka dapat disimpulkan bahwa fungsi faktorial memiliki
kompleksitas \(n - 1\), atau \(O(n)\). Ingat bahwa kunci dari
perhitungan kompleksitas untuk algoritma rekursif terdapat pada fungsi
matematis algoritma dan definisi kapan berhentinya fungsi rekursif tersebut.
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 komentar:
Posting Komentar