Rekursif (Recursions) Dalam Algoritma Pemrograman C/C++

Rekursif adalah salah satu konsep penting dalam pemrograman, termasuk di C dan C++. Dengan rekursif, sebuah fungsi dapat memanggil dirinya sendiri untuk menyelesaikan masalah yang lebih kecil dan sederhana hingga mencapai hasil akhir. Teknik ini sering digunakan untuk menyelesaikan masalah yang memiliki pola berulang, seperti perhitungan faktorial, deret Fibonacci, dan traversal struktur data seperti pohon atau graf.

Pada artikel ini, kita akan mempelajari:

1. Apa itu rekursif.
2. Cara kerja rekursif.
3. Implementasi rekursif di C/C++ dengan contoh nyata.
4. Kelebihan, kekurangan, dan tips menggunakan rekursif.

Apa Itu Rekursif?

Rekursif adalah proses di mana sebuah fungsi memanggil dirinya sendiri dalam program. Dalam pemrograman, rekursif dapat dibagi menjadi dua bagian utama:

1. Base Case (Kondisi Akhir): Kondisi yang menghentikan rekursi.
2. Recursive Case (Kondisi Rekursif): Bagian fungsi yang memanggil dirinya sendiri dengan masalah yang lebih kecil.

Cara Kerja Rekursif

Ketika sebuah fungsi rekursif dipanggil, ia akan terus memanggil dirinya sendiri hingga mencapai base case. Setelah base case tercapai, fungsi mulai kembali dari pemanggilan terakhir ke yang pertama (dikenal sebagai backtracking).

Contoh Alur Rekursif:
Misalkan kita menghitung faktorial 3 (3!) menggunakan rekursif:

faktorial(3) -> 3 * faktorial(2) -> 2 * faktorial(1) -> 1 (Base Case)

Setelah mencapai base case, hasilnya dihitung sebagai berikut:

1 -> 2 * 1 -> 3 * 2 -> 6

Contoh Implementasi Rekursif di C/C++

1. Faktorial dengan Rekursif

Faktorial dari sebuah bilangan adalah hasil perkalian bilangan itu dengan bilangan-bilangan sebelumnya hingga 1.
Contoh: 5! = 5 * 4 * 3 * 2 * 1 = 120.

Kode Program:

#include <iostream>
using namespace std;

// Fungsi Rekursif untuk Menghitung Faktorial
int faktorial(int n) {
    if (n == 0 || n == 1) { // Base Case
        return 1;
    } else { // Recursive Case
        return n * faktorial(n - 1);
    }
}

int main() {
    int angka;

    cout << "Masukkan angka: ";
    cin >> angka;

    cout << "Faktorial dari " << angka << " adalah: " << faktorial(angka) << endl;
    return 0;
}

Input/Output:

Masukkan angka: 5
Faktorial dari 5 adalah: 120

2. Deret Fibonacci dengan Rekursif

Deret Fibonacci adalah deret angka di mana setiap angka adalah jumlah dari dua angka sebelumnya.
Contoh: 0, 1, 1, 2, 3, 5, 8, ....

Kode Program:

#include <iostream>
using namespace std;

// Fungsi Rekursif untuk Deret Fibonacci
int fibonacci(int n) {
    if (n == 0) { // Base Case
        return 0;
    } else if (n == 1) { // Base Case
        return 1;
    } else { // Recursive Case
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

int main() {
    int jumlah;

    cout << "Masukkan jumlah angka Fibonacci yang ingin ditampilkan: ";
    cin >> jumlah;

    cout << "Deret Fibonacci: ";
    for (int i = 0; i < jumlah; i++) {
        cout << fibonacci(i) << " ";
    }
    cout << endl;
    return 0;
}

Input/Output:

Masukkan jumlah angka Fibonacci yang ingin ditampilkan: 7
Deret Fibonacci: 0 1 1 2 3 5 8

3. Mencari Nilai Maksimum dalam Array

Rekursif juga dapat digunakan untuk mencari nilai maksimum dalam array.

Kode Program:

#include <iostream>
using namespace std;

// Fungsi Rekursif untuk Mencari Maksimum
int cariMaksimum(int array[], int n) {
    if (n == 1) { // Base Case
        return array[0];
    } else { // Recursive Case
        return max(array[n - 1], cariMaksimum(array, n - 1));
    }
}

int main() {
    int array[] = {3, 5, 7, 2, 8};
    int ukuran = sizeof(array) / sizeof(array[0]);

    cout << "Nilai maksimum dalam array: " << cariMaksimum(array, ukuran) << endl;
    return 0;
}

Output:

Nilai maksimum dalam array: 8

Kelebihan dan Kekurangan Rekursif

Kelebihan:

1. Kodenya Sederhana dan Bersih
   Rekursif membuat kode untuk masalah kompleks (seperti traversal pohon atau algoritma pencarian) lebih sederhana.
2. Cocok untuk Pola Berulang
   Masalah seperti faktorial, Fibonacci, dan traversing struktur data cocok menggunakan rekursif.

Kekurangan:

1. Penggunaan Memori Lebih Besar
   Rekursif menggunakan call stack untuk menyimpan setiap pemanggilan fungsi. Ini bisa menyebabkan stack overflow jika terlalu banyak pemanggilan.
2. Kadang Kurang Efisien
   Rekursif dapat mengulang perhitungan yang sama berkali-kali. Contoh: Fibonacci tanpa optimasi.

Tips Menggunakan Rekursif

1. Selalu Definisikan Base Case
   Base case sangat penting untuk menghentikan rekursi agar tidak berjalan tanpa henti.
2. Gunakan Rekursif dengan Bijak
   Jika masalah dapat diselesaikan lebih efisien dengan iterasi (loop), gunakan iterasi.
3. Optimasi dengan Memoisasi
   Untuk rekursif seperti Fibonacci, gunakan memoisasi untuk menghindari perhitungan ulang.

Contoh Memoisasi Fibonacci:

#include <iostream>
#include <vector>
using namespace std;

vector<int> memo(100, -1); // Array untuk menyimpan hasil

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    if (memo[n] != -1) return memo[n]; // Cek apakah sudah dihitung

    memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return memo[n];
}

int main() {
    int n = 10;
    cout << "Fibonacci ke-" << n << ": " << fibonacci(n) << endl;
    return 0;
}

Kesimpulan

Rekursif adalah teknik pemrograman yang sangat powerful untuk menyelesaikan masalah dengan pola berulang. Meskipun rekursif membuat kode lebih sederhana, kamu harus berhati-hati dengan efisiensi dan penggunaan memori. Dengan memahami konsep dasar, implementasi, dan kelebihan-kekurangannya, kamu bisa menggunakan rekursif secara optimal di algoritma pemrograman.