Rekursif dan Contoh Studi Kasus Beserta Opsi Penyelesaiannya Menggunakan Bahasa C

Pada kesempatan kali ini kita akan membahas tentang rekursif. Rekursif merupakan teknik pengulangan yang melibatkan dirinya sendiri. Maksud dari pelibatan dirinya sendiri adalah, pada pemrograman, fungsi akan mengembalikan nilai (return value) yang mana hasil dari nilai kembalian tersebut akan dimasukkan pada fungsi yang sama. Untuk lebih mudah dalam memahami, perhatikan potongan kode program berikut.

int faktorial(int bilangan){
    if(bilangan <= 1){
        return 1;
    } else{
        return bilangan * faktorial(bilangan-1);
    }
}

Fungsi di atas merupakan fungsi untuk mencari nilai dari faktorial dengan menggunakan teknik rekursif. Perhatikan pada badan fungsi yang ditandai huruf tebal. Kita dapat melihat bahwa di dalam badan fungsi faktorial memanggil dirinya sendiri. Itu merupakan konsep dari rekursif. Nah dalam penggunaannya, rekursif banyak dimanfaatkan seperti contoh sebelumnya, yaitu mencari nilai faktorial, kemudian mencari deret bilangan fibbonacci, pemangkatan bilangan, dan masih banyak lagi.

Sebelum masuk pada studi kasus, ada baiknya kita bahas cara kerja dari rekursif pada potongan kode program faktorial di atas. Sebelumnya kita harus tahu terlebih dahulu apa itu faktorial. Faktorial merupakan perkalian mundur dari bilangan tertentu sampai dengan 1. Misalkan kita ingin mencari nilai faktorial dari bilangan 5, maka akan dilakukan proses perkalian mundur: 5 x 4 x 3 x 2 x 1 = 120. Jika dijabarkan akan melalui tahapan sebagai berikut:

1. Bilangan 5 akan menjadi parameter dari fungsi faktorial.
2. Bilangan, dalam hal ini 5, akan dicek dengan kondisional if jika kurang dari atau sama dengan 1, maka akan mengembalikan nilai 1. Artinya, pada kondisi ini fungsi rekursif akan berakhir dan mengembalikan nilai 1, yang nantinya akan dipakai untuk proses perhitungannya.
3. Selanjutnya jika bilangan (5) tidak kurang dari atau sama dengan 1, maka kembalikan nilai perkalian antara bilangan awal, dalam hal ini 5, dengan rekursif dari bilangan awal dikurangi 1, yaitu 4.
4. Langkah 2 dan 3 akan diulangi sampai nilai bilangan parameter bernilai 1.

Dari proses di atas, dapat kita tulis bahwa faktorial dari 5 adalah:

5 => 5 * faktorial(5-1)
4 => 4 * faktorial(4-1)
3 => 3 * faktorial(3-1)
2 => 2 * faktorial(2-1)
1 => 1

Sehingga perhitungannya menjadi 5 x 4 x 3 x 2 x 1 = 120.

Selanjutnya kita akan membahas penyelesaian dari studi kasus pada pertemuan 11 mata kuliah struktur data dan algoritma yang dapat dilihat di sini. Terdapat 2 buah soal untuk diselesaikan dengan konsep rekursif.

1. Sebuah toples kapasitas 1000 permen. Permen awal ada 2 buah. Setiap detik bertambah 2 kali lipat. Pada detik ke berapa toples tsb penuh? Catatan: dikatakan penuh jika mendekati 1000 dan kurang dari 1000

2. Sebuah toples terdapat 1 buah bakteri. Setiap menit, bakteri tersebut berkembang 2 kali lipat. Toples tersebut akan penuh dalam waktu 1 jam (60 menit). Pada menit ke berapa toples tersebut 1/4 penuh?

Kita akan membuat sebuah program yang dapat menyelesaikan kedua persoalan di atas sekaligus. Namun, sebelum itu kita bahas soalnya satu persatu terlebih dahulu. Pada nomor 1 dapat kita simulasikan perhitungan manualnya sebagai berikut:

2 4 8 16 32 64 128 256 512 1024 --> jumlah permen

1 2 3 4 5 6 7 8 9 10 --> detik

Kita dapat melihat bahwa pada detik ke 9 toples dianggap penuh karena telah mencapai 512 buah permen. Perlu diingat bahwa syarat toples dikatakan penuh adalah yang mendekati 1000 dan tidak lebih dari 1000. Pada detik ke 10 tidak dihitung karena jumlah permen melebihi 1000, yaitu sebanyak 1024 buah. Dari sini kita dapat melihat konsep deret bilangannya. Yang ditanyakan adalah pada detik keberapa toples akan penuh dan dari hasil simulasi kita didapatkan detik ke 9 lah yang tepat.

Kemudian pada soal kedua, seperti tes yang dilakukan oleh Jerome Poline yang diberikan untuk teman-temannya, yaitu terkait dengan bakteri pada toples yang setiap menit bakteri tersebut berkembang sebanyak 2 kali lipat. Pada waktu 1 jam, toples tersebut penuh dengan bakteri, kemudian ditanyakan pada menit ke berapa toples tersebut akan 1/4 penuh? Sebelumnya kita akan membuat simulasinya terlebih dahulu. Kita ubah waktunya ke dalam bentuk menit agar memudahkan dalam perhitungan, 1 jam = 60 menit. Karena yang ditanyakan berupa bilangan pecahan (1/4 toples), maka untuk kapasitas toples penuh kita anggap 1/1, artinya 1 atau penuh/full.

Perhatikan pada tabel di atas, jawaban yang benar adalah pada menit ke 58, yaitu pada saat 1/4 toples penuh dengan bakteri. Mengapa bisa demikian? Pada soal dijelaskan bahwa bakteri setiap menit akan berkembang menjadi 2 kali lipat, dan pada 1 jam toples akan penuh. Sehingga kita hitung mundur dari informasi ini, menit 60 atau 1 jam kondisi toples penuh, pada menit ke 59 (mundur 1 menit), maka kondisi toples akan 1/2 penuh, hal ini tinggal dibalik saja sebenarnya. Kalau menit bertambah, bakteri tersebut akan berkembang 2 kali lipat, artinya jika kita balik dengan mengurangkan menitnya, maka bakteri akan berkurang 1/2 nya. Sudah paham? Silakan pahami ini terlebih dahulu sebelum lanjut ke pembahasan kode programnya.

Baik, untuk menyelesaikan kedua persoalan di atas dengan menggunakan konsep rekursif akan saya berikan kode programnya sebagai berikut.

#include 
#define max_kapasitas 1000 // konstanta kapasitas maksimal permen
#define max_waktu 60 // konstanta waktu maksimal toples bakteri penuh

typedef struct{ // membuat struct untuk kedua soal, untuk menyimpan informasi total permen, detik penuh permen dan menit penuh bakteri.
    int total, detik, menit;
    float kapasitas;
} struk;

struk permen, bakteri; // membuat variabel dengan ADT yang telah dibuat

// fungsi rekursif untuk menghitung waktu toples penuh dengan permen
int rekursif_permen(int x){
    if(x < max_kapasitas){ // cek apakah x kurang dari max_kapasitas, jika true maka
        permen.detik++;   // tambahkan waktu dalam detik
        permen.total = x; // simpan nilai x sebagai nilai total
        return rekursif_permen(x*2); // memanggil fungsi dirinya sendiri (rekursif) dengan mengkalikan dengan 2
    } else{
        return x; // jika x tidak kurang dari max_kapasitas maka kembalikan nilai x
    }
}

// fungsi rekursif untuk menghitung waktu dalam menit bakteri memenuhi toples
int rekursif_bakteri(int waktu_penuh, float ditanya){ // parameter waktu penuh dan ditanya (1/4 penuh)
    int decrement; // variabel bantuan sebagai pengurang waktu (dalam menit)
    float pembagi; // variabel bantuan sebagai pembagi utk kapasitas toples
    decrement = 1; // nilai awal variabel decrement
    
    if(ditanya != bakteri.kapasitas){ // jika yg ditanyakan tidak sama dengan kondisi kapasitas toples, maka
        int x = 2;
        while(ditanya != bakteri.kapasitas){ // lakukan looping, selama yg ditanyakan tidak sama dengan kondisi kapasitas toples
            pembagi = (float) x; // set nilai pembagi dengan x dan dibentuk ke dalam data float
            bakteri.menit = waktu_penuh - decrement; // waktu (dalam menit) dikurangi terus
            bakteri.kapasitas = (float) 1/pembagi; // kapasitas toples dibagi dengan pembagi
            x = x*2; // nilai dari x dikalikan 2
            decrement = decrement + 1; // nilai dari variabel decrement ditambah 1
        } return rekursif_bakteri(bakteri.menit, ditanya);
    } else{
        return bakteri.menit;
    }
}

int main()
{
    int jumlah_awal_permen = 2;
    rekursif_permen(jumlah_awal_permen);
    printf("1.) Toples akan penuh dengan permen dengan jumlah awalnya %d pada detik ke %d, sebanyak %d buah.\n", jumlah_awal_permen, permen.detik, permen.total);
    
    int waktu_penuh = 60; // dalam menit
    float ditanya = (float) 1/4;
    rekursif_bakteri(waktu_penuh, ditanya);
    printf("2.) Toples akan %0.3f penuh dengan bakteri pada waktu %d menit.\n", ditanya, bakteri.menit);
    return 0;
}

Pembahasan dalam bentuk video dapat disimak.

Demikian bahasan mengenai fungsi rekursif dan juga contoh studi kasus beserta penyelesaiannya. Silakan diamati, akan ada ketidaksesuaian antara soal dan jawaban dalam hal penyelesaian. Silakan temukan dan jadikan bahan diskusi. Terimakasih.