Rekursi: Konsep dan Penerapannya

Oleh Samuel Wirajaya (website)

Co-founder, Acutis Academy. Software Engineer eks-FAANG, penggemar UNIX & Linux.

Apa itu fungsi rekursif?

Rekursi, konsep yang tampak mistis dalam ilmu komputer, adalah sebuah teknik ampuh di mana sebuah fungsi memanggil dirinya sendiri dalam berjalannya fungsi tersebut. Fungsi yang menggunakan teknik rekursi, kita sebut sebagai fungsi rekursif.

Bayangkan set boneka Rusia yang bersarang: setiap boneka berisi versi yang lebih kecil dari dirinya sendiri. Rekursi bekerja secara serupa, memecah masalah menjadi “sub-masalah” yang lebih kecil dan mirip dengan dirinya sendiri hingga mencapai kasus dasar sederhana yang dapat diselesaikan secara langsung.

Contoh rekursi sederhana

Mari kita ilustrasikan dengan contoh klasik: menghitung faktorial suatu bilangan. Faktorial dari 5 (ditulis sebagai 5!) adalah 5 * 4 * 3 * 2 * 1 = 120. Contoh fungsi untuk menghitung ini akan terlihat seperti ini:

Atau dalam Python:

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

Perhatikan bahwa di baris terakhir fungsi factorial, terjadi pemanggilan kepada fungsi factorial sendiri. Maka dari itu, fungsi factorial adalah fungsi rekursif.

Terdapat dua unsur utama dalam menyusun fungsi rekursif yang baik dan benar.

Kasus Dasar. Dalam kasus dasar (base case), input dari fungsinya sangatlah sederhana atau trivial, sehingga output dari fungsi bisa dengan mudah dihitung. Dalam contoh faktorial di atas, terdapat pengecekan jika n adalah 0. Dalam kasus ini fungsi langsung mengembalikan 1 tanpa melakukan apa-apa yang lain.

Langkah Rekursif. Langkah rekursif mencakup kasus-kasus di luar kasus dasar. Dalam contoh di atas, Jika n bukan 0, laporkan n dikalikan dengan faktorial dari n - 1 sebagai hasil penghitungan. Ini memicu panggilan lain ke fungsi factorial, tetapi dengan input yang lebih kecil, yakni n - 1.

Apa yang terjadi ketika factorial dipanggil?

Reaksi Berantai. Misalkan factorial(5) dipanggil. Maka factorial(5) akan memanggil factorial(4) dan menunggu hasil penghitungannya. factorial(4) pun akan memanggil factorial(3). Kemudian factorial(3) memanggil factorial(2). factorial(2) memanggil factorial(1). factorial(1) pun memanggil factorial(0).

Pembukaan Kembali atau Unwinding. Perhatikan bahwa factorial(0) adalah kasus basis, yang langsung melaporkan nilai 1 kepada pemanggilnya. factorial(1) akan menghitung 1 * 1 = 1 dan melaporkannya kepada pemanggilnya. factorial(2) akan menghitung 2 * 1 = 2 dan melaporkannya kepada pemanggilnya. factorial(3) akan menghitung 3 * 2 = 6 dan melaporkannya kepada pemanggilnya. factorial(4) akan menghitung 4 * 6 = 24 dan melaporkannya kepada pemanggilnya. factorial(5) akan menghitung 5 * 24 = 120 dan melaporkan hasil akhirnya.

Digambarkan secara visual:

| factorial(5)
|
| 5 * | factorial (4)
|     |
|     | 4 * | factorial (3)
|     |     |
|     |     | 3 * | factorial(2)
|     |     |     |
|     |     |     | 2 * | factorial(1)
|     |     |     |     |
|     |     |     |     | 1 * | factorial(0)
|     |     |     |     |     |
|     |     |     |     |     | = 1
|     |     |     |     | = 1
|     |     |     | = 2
|     |     | = 6
|     |
|     | = 24
|
| = 120

Keuntungan dan kerugian rekursi

Menulis fungsi rekursif, walaupun mungkin agak sulit untuk pemula, memiliki beberapa keuntungan, di antaranya adalah:

• Elegan. Rekursi seringkali memberikan solusi yang ringkas, elegan, dan mudah dianalisa secara logis.
• Dekomposisi masalah. Rekursi secara alami memecah masalah kompleks menjadi sub-masalah yang lebih mudah dikelola secara sangat efisien. Karena itu, banyak algoritma sorting (pengurutan data) dan searching (pencarian data) yang menggunakan rekursi.
• Penjelajahan pohon atau tree traversal. Rekursi juga sangat ideal untuk menjelajahi struktur data yang berbentuk seperti pohon (tree), misalnya sistem file, atau database yang disusun secara hirarkis.

Namun dalam penggunaannya, terdapat beberapa kerugian yang terkadang menjadi masalah:

• Stack overflow. Rekursi berlebihan dapat menyebabkan kesalahan stack overflow jika fungsi memanggil dirinya sendiri terlalu banyak kali.
• Beban kinerja. Fungsi rekursif seringkali memiliki beban kinerja komputer yang lebih tinggi dibandingkan solusi non-rekursif karena overhead panggilan fungsi dan perhitungan berulang.

Kapan menggunakan rekursi?

Rekursi paling cocok untuk masalah yang:

• Dapat diuraikan menjadi sub-masalah yang mirip dengan dirinya sendiri.
• Memiliki kasus dasar yang jelas untuk menghentikan rekursi.
• Melibatkan penjelajahan pohon atau struktur data hirarkis.

Dalam kesempatan yang akan datang, saya juga akan memberi contoh-contoh penerapan rekursi lainnya dalam ilmu komputer. Maka stay tuned!

Kesimpulan

Meskipun mungkin tampak kompleks pada pandangan pertama, rekursi adalah alat yang ampuh dalam arsenal ilmuwan komputer. Memahami prinsip dan batasannya memungkinkan solusi yang elegan dan efisien untuk berbagai masalah. Seperti alat apa pun, rekursi harus digunakan dengan bijaksana, mempertimbangkan keunggulan dan potensi kerugiannya.