Memahami Rekursi Dengan Rekursi
Rowing the longest distance doesn’t mean you’re lost
Pembuka
Rekursi merupakan salah satu topik yang sering dibahas dalam dunia pemrograman. Rekursi adalah fungsi yang memanggil dirinya sendiri. Pemahaman tentang rekursi haruslah kuat, sebab banyak operasi dalam struktur data yang lebih mudah diselesaikan menggunakan rekursi dibandingkan dengan iterasi (loop).
Rekursi bisa menjadi pedang bermata dua : ketika ia digunakan dengan benar, ia mampu meringkas kode dan memudahkan pemrogram ketika dibaca, namun ketika ia digunakan dengan cara yang salah, ia akan terus-menerus memanggil dirinya sendiri tanpa henti.
Tidak sedikit programmer yang membutuhkan waktu cukup lama serta kesulitan memahami dan mengimplementasikan rekursi. Lewat tulisan ini, saya akan mencoba dan (kita) akan sama-sama belajar untuk memahami konsep rekursi.
Returning Value Function dan Non Returning Value Function
Returning value function adalah sebuah fungsi yang mengembalikan nilai, sedangkan non returning value function adalah sebaliknya (tidak mengembalikan nilai). Non returning value function biasa dikenal sebagai void function.
Saya butuh waktu kurang lebih satu bulan untuk benar-benar memahami apa itu fungsi yang mengembalikan nilai. Kode sederhana di bawah ini akan memperjelas perbedaan returning value function dan void function.
Hasil dari kode di atas sebagai berikut.
Pada gambar di atas, baris pertama merupakan keluaran baris ke-15 pada kode, baris kedua adalah keluaran baris ke-16 pada kode, dan baris ketiga adalah keluaran baris ke-19 pada kode.
Pada kode di atas, kita disuguhkan dengan dua buah fungsi, yaitu returnVal dan nonReturnVal yang keduanya menerima parameter val1 dan val2. Kedua fungsi tersebut menyimpan hasil penjumlahan parameter val1 dan val2 dalam variabel result. Yang membedakan adalah fungsi returnVal me-return variabel result, sedangkan fungsi nonRetrunVal tidak.
Perbedaan antara kedua fungsi tersebut terlihat jelas ketika kita melakukan variable assignment pada variabel c (baris ke-12) dan variabel d (baris ke-13). Variabel c menyimpan/menampung seluruh hasil operasi yang dikerjakan oleh fungsi returnValue, sehingga ketika kita print, maka kita akan mendapatkan hasil 5. Variabel d tidak akan menampung apa-apa, sebab pada fungsi nonRetrunValue, kita tidak mengembalikan (return) hasil operasi yang ditampung oleh variabel result pada fungsi tersebut, sehingga ketika kita print, kita akan mendapatkan hasil None. Perbedaan ini semakin jelas ketika melakukan penambahan (increment) pada variabel c dan variabel d. Ketika kita tambahkan dengan dua pada masing-masing variabel, kita akan dapatkan variabel c bernilai 4, sedangkan kita akan dapatkan error ketika kita mem-print hasil dari d.
Contoh kode sederhana tentang returning value function dengan void function di atas, dapat kita pahami bahwa nilai yang dikembalikan oleh returning value function dapat digunakan kembali, sedangkan seluruh nilai yang ditampung pada void function tidak dapat digunakan kembali, sebab void function tidak mengembalikan nilai apapun.
Studi Kasus Sederhana Dengan Rekursi
Kode yang ditulis menggunakan rekursi lebih mudah untuk dibaca, namun sering kali sulit dipahami. Pada segmen ini, kita akan memahami rekursi dengan studi kasus faktorial.
Faktorial adalah perkalian mundur suatu bilangan positif yang kurang dari sama dengan bilangan positif itu sendiri
Jika kita terjemahkan definisi faktorial di atas, kita akan mendapat rumus umum faktorial sebagai berikut.
Sebagai contoh, kita misalkan nilai n = 5, sehingga kita dapati hasil sebagai berikut.
Jika nilai n adalah 0 atau 0!, maka 0! bernilai 1.
Dari penjelasan di atas, kita bisa menulis ulang definisi faktorial sebagai berikut.
Dari definisi ulang di atas, kita bisa memahami ketika nilai n = 1 atau n = 0, maka nilai n atau nilai yang dikembalikan adalah 1, sedangkan untuk n > 1 maka n akan memanggil dirinya sendiri sampai nilai n bernilai 1. Proses n memanggil dirinya sendiri ini disebut dengan rekursi.
Implementasi penyelesaian faktorial menggunakan pendekatan rekursi dicontohkan pada kode di bawah.
Hasil dari keluaran program di atas adalah sebagai berikut.
Jika ditelaah lebih lanjut, jalannya program di atas sebagai berikut.
Memahami Lebih Dalam Mengenai Rekursi
Mengutip dari bacaan di website MIT (sumber bisa diakses di sini), ketika berhadapan dengan rekursi, ada dua hal yang harus kita perhatikan, yaitu base case dan proses rekursi.
- Base case adalah proses paling sederhana yang dapat dilakukan sepanjang rekursi. Base case biasanya merupakan string kosong, list kosong, integer 0, atau struktur data buatan kosong. Perlu diingat juga, base case suatu rekursi bisa memiliki lebih dari sebuah base case, misalnya penyelesaian deret fibonacci menggunakan rekursi, di mana base case-nya adalah n = 0 atau n = 1. Kita harus cermat ketika mendefinisikan base case. Salah mendefinisikan base case bisa berakibat pada rekursi yang tidak akan berhenti.
- Proses rekursi adalah proses menyederhanakan masalah dari masalah yang besar menjadi sub-masalah yang lebih kecil menggunakan rekursi, kemudian menggabungkan kembali solusi dari sub-masalah menjadi solusi utuh.
Berikut contoh penyelesaian faktorial menggunakan rekursi dalam bentuk call stack.
Rekursi Versus Iterasi
Ketika dihadapkan dengan permasalahan yang membutuhkan pendekatan perulangan sebagai solusi penyelesaian, setidaknya ada dua pendekatan yang bisa kita gunakan : menggunakan iterasi (perulangan biasa) atau menggunakan rekursi. Dari pernyataan ini, timbul pertanyaan : berarti kita tidak perlu menggunakan rekursi ketika menyelesaikan permaslahan yang membutuhkan perulangan?. Pertanyaan atau cara pandang ini lumrah ditemui, terutama bagi yang baru pertama kali belajar tentang perulangan dan rekursi, seperti yang bisa ditemukan di sini.
Menurut saya, beberapa permasalahan justru lebih sulit diselesaikan menggunakan pendekatan iterasi dibandingkan dengan rekursi. Sebagai contoh, meng-insert node baru pada BST lebih mudah menggunakan metode rekursi dibandingkan dengan metode iterasi (sampai saat ini, saya tidak menemukan sumber bagaimana meng-insert node baru pada BST menggunakan metode iterasi).
Studi Kasus Lanjut Dengan Rekursi
Setelah kita memahami bagaimana cara kerja rekursi, apa aja elemen rekursi, dan studi kasus sederhana yang diselesaikan menggunakan rekursi, pada segmen ini, kita akan membahas studi kasus lanjut yang diselesaikan menggunakan rekursi. Studi kasus yang kita pelajari adalah meng-insert Node pada Binary Search Tree. Studi kasus ini akan kita kerjakan berdasarkan faktor yang dilansir oleh MIT pada segmen sebelumnya. Berikut studi kasus yang akan kita pelajari.
- Mendefinisikan base case
Base case pada kasus ketika meng-insert node baru pada Binary Search Tree (BST) adalah ketika root node belum diisi. Base case pada kode di atas ditunjukkan pada baris ke-8 sampai baris ke-9. Base case ini akan memeriksa apakah node kosong atau tidak. Jika node kosong, maka fungsi insert akan mengembalikan (return) node baru. - Proses rekursi
Proses rekursi pada kasus di atas ditunjukkan pada baris ke-10 sampai baris ke-17. Proses rekursi dilakukan ketika node tidak dalam kondisi None. Proses rekursi ini memiliki percabangan untuk membandingkan data pada root (yang merupakan node) dengan key sebagai parameter. Apabila key > dari data pada root, maka node baru akan ditambah di sebelah kanan, dan sebaliknya secara rekursif hingga salah satu pointer node (self.right atau self.left) bernilai None.
Supaya lebih jelas, gambar di bawah dibuat sebagai visualisasi untuk studi kasus di atas.
Terdapat 4 tahap pada gambar di atas dengan penjelasan sebagai berikut.
- Kita ingin meng-insert node baru dengan parameter key = 5. Di sini, kita tahu bahwa nilai key > nilai data pada root, yakni 3. Karena nilai key lebih besar daripada nilai data pada root, maka node baru akan ditambah di sebalah kanan root menggunakan rekursi (memanggil fungsi insert lagi). Nilai kembalian fungsi ini akan disimpan pada variabel root.right. Variabel ini menunjukkan bahwa node baru akan di simpan di sebelah kiri.
- Pada proses rekursi, fungsi insert dipanggil kembali, namun kali ini, argumen root bernilai None, sebab pada tahap 1, argumen root.right bernilai None (Argumen root.right bernilai None pada tahap 1 dikarenakan ketika kita menginistansiasi class Node (baris ke-19 pada kode), secara default properti root.right dan root.left sama-sama bernilai None. Nilai kedua properti tidak berubah sampai tahap 2 pada gambar). Karena pada tahap 2 argumen root bernilai None, maka kondisi if pada baris ke-8 kode dijalankan, dan proses rekursi ini mengembalikan node baru dengan nilai data = 5.
- Nilai kembalian pada tahap 2, yakni Node(5) disimpan pada variabel root.right
- Fungsi mengembalikan root dengan nilai root.right=Node(5)
Penutup
Rekursi merupakan fungsi yang memanggil dirinya sendiri. Kode yang ditulis untuk memecahkan permasalahan menggunakan pendekatan rekursi lebih mudah dibaca dan lebih ringkas. Namun dibalik kemudahan tersebut, tak sedikit pemrogram (programmer) yang kesulitan ketika menyelesaikan masalah menggunakan pendekatan rekursi.
Apakah semua permasalahan bisa diselesaikan menggunakan pendekatan rekursi? Jawabannya tidak juga. Sebab beberapa permasalahan sulit diselesaikan menggunakan pendekatan rekursi karena sulit menemukan base case-nya. Salah mendefinisikan base case dapat berakibat proses rekursi yang tidak ada hentinya.
Akhir kata, belajar merupakan pengalaman spiritual yang tidak bisa dibandingkan antara satu orang dengan orang lain.
