Rekursi

Dalam C++ Rekursi  adalah teknik di mana sebuah fungsi memanggil dirinya sendiri untuk menyelesaikan masalah. Teknik ini sering digunakan untuk memecahkan masalah yang dapat dibagi menjadi sub-masalah yang lebih kecil dan serupa. Misalnya, masalah seperti pencarian dalam struktur data berbentuk pohon atau penyelesaian masalah matematika seperti faktorial atau deret Fibonacci sering diselesaikan menggunakan rekursi.

Contoh Dasar Rekursi dalam C++

Berikut adalah beberapa contoh untuk menunjukkan cara kerja rekursi dalam C++.

1. Faktorial

Faktorial dari sebuah bilangan bulat non-negatif $n$ adalah produk dari semua bilangan bulat positif kurang dari atau sama dengan $n$. Misalnya, faktorial dari 5 (ditulis sebagai 5!) adalah $5 \times 4 \times 3 \times 2 \times 1$.

#include <iostream>
using namaspace std;

int factorial(int n) {
    if (n <= 1)  // Kasus dasar: faktorial dari 0 atau 1 adalah 1
        return 1;
    else
        return n * factorial(n - 1);  // Panggilan rekursif
}

int main() {
    int number = 5;
    cout << "Faktorial dari " << number << " adalah " << factorial(number) << endl;
    return 0;
}

2. Deret Fibonacci

Deret Fibonacci adalah deret di mana setiap bilangan adalah jumlah dari dua bilangan sebelumnya, dimulai dari 0 dan 1. Jadi, deretnya adalah 0, 1, 1, 2, 3, 5, 8, 13, dan seterusnya.

#include <iostream>
using namaespace std;

int fibonacci(int n) {
    if (n <= 1)  // Kasus dasar: deret Fibonacci dari 0 adalah 0, dan dari 1 adalah 1
        return n;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);  // Panggilan rekursif
}

int main() {
    int number = 10;
    cout << "Fibonacci dari " << number << " adalah " << fibonacci(number) << endl;
    return 0;
}

3. Pencarian Binari

Pencarian binari adalah metode efisien untuk mencari elemen dalam array yang terurut. Algoritma ini membagi array menjadi dua bagian secara berulang-ulang sampai elemen yang dicari ditemukan atau sampai array tidak bisa dibagi lagi.

#include <iostream>
using namespace std;

int binarySearch(int arr[], int left, int right, int target) {
    if (left > right)
        return -1;  // Elemen tidak ditemukan
    
    int mid = left + (right - left) / 2;
    
    if (arr[mid] == target)
        return mid;  // Elemen ditemukan
    else if (arr[mid] > target)
        return binarySearch(arr, left, mid - 1, target);  // Pencarian di sebelah kiri
    else
        return binarySearch(arr, mid + 1, right, target);  // Pencarian di sebelah kanan
}

int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 10;
    int result = binarySearch(arr, 0, n - 1, target);
    
    if (result != -1)
        cout << "Elemen ditemukan di indeks " << result << endl;
    else
        cout << "Elemen tidak ditemukan" << endl;
    
    return 0;
}

Pentingnya Kasus Dasar

Dalam setiap fungsi rekursif, penting untuk memiliki kasus dasar (base case) yang menghentikan rekursi. Tanpa kasus dasar, fungsi akan terus memanggil dirinya sendiri tanpa henti, yang dapat menyebabkan stack overflow dan crash program.

Berikut adalah beberapa contoh penerapan prinsip rekursi dalam kehidupan sehari-hari:

1. Resep Masakan (Pembuatan Makanan dengan Bahan Bertumpuk)

Masalah: Menghasilkan hidangan yang memerlukan beberapa langkah pengolahan dengan bahan yang harus diproses secara berulang. Misalnya, membuat lasagna yang memerlukan beberapa lapisan saus dan pasta.

Contoh Rekursi:

• Langkah 1: Siapkan bahan dasar (saus, daging, keju).
• Langkah 2: Tambahkan lapisan saus, pasta, dan keju.
• Langkah 3: Untuk setiap lapisan, panggil kembali langkah 2 hingga bahan habis.
• Kasus Dasar: Jika semua bahan sudah habis, susun lasagna dan panggang.

2. Pembersihan Rumah (Pembersihan Berulang)

Masalah: Pembersihan rumah yang membutuhkan pembersihan berbagai area dengan metode yang sama.

Contoh Rekursi:

• Langkah 1: Pilih satu area untuk dibersihkan (misalnya, satu ruangan).
• Langkah 2: Bersihkan area tersebut (sapu, lap, vakum).
• Langkah 3: Setelah selesai, pilih area berikutnya dan ulangi langkah 2 hingga semua area dibersihkan.
• Kasus Dasar: Jika semua ruangan sudah dibersihkan, proses selesai.

3. Pengurutan Tugas (To-Do List)

Masalah: Mengelola dan menyelesaikan daftar tugas yang harus diselesaikan.

Contoh Rekursi:

• Langkah 1: Pilih satu tugas dari daftar.
• Langkah 2: Selesaikan tugas tersebut atau bagilah menjadi sub-tugas lebih kecil.
• Langkah 3: Untuk setiap sub-tugas, ulangi langkah 1 dan 2 hingga sub-tugas selesai.
• Kasus Dasar: Jika tidak ada lagi sub-tugas yang tersisa, tugas selesai.

4. Pembuatan Keputusan (Mengambil Keputusan Berlapis)

Masalah: Mengambil keputusan yang melibatkan beberapa langkah yang bergantung pada keputusan sebelumnya.

Contoh Rekursi:

• Langkah 1: Buat keputusan pertama berdasarkan kondisi saat ini.
• Langkah 2: Jika keputusan tersebut mempengaruhi langkah berikutnya, panggil kembali langkah 1 dengan kondisi baru.
• Langkah 3: Terus ulangi hingga semua keputusan selesai diambil.
• Kasus Dasar: Jika semua keputusan sudah dibuat, proses selesai.

5. Penyelesaian Masalah (Menangani Permasalahan Berlapis)

Masalah: Menangani masalah besar dengan memecahnya menjadi masalah-masalah kecil.

Contoh Rekursi:

• Langkah 1: Identifikasi masalah utama yang harus diselesaikan.
• Langkah 2: Pecah masalah tersebut menjadi sub-masalah yang lebih kecil.
• Langkah 3: Untuk setiap sub-masalah, terapkan langkah-langkah penyelesaian hingga mencapai solusi.
• Kasus Dasar: Jika tidak ada sub-masalah yang tersisa, masalah utama selesai.

Implementasi Rekursi dalam C++: Contoh Masalah Faktorial

Untuk memberikan gambaran yang lebih jelas tentang bagaimana rekursi bekerja, mari kita lihat contoh implementasi fungsi faktorial menggunakan C++.

#include <iostream>

using namespace std;

// Fungsi rekursif untuk menghitung faktorial dari n
int factorial(int n) {
    if (n <= 1) // Kasus dasar
        return 1;
    else
        return n * factorial(n - 1); // Panggilan rekursif
}

int main() {
    int number = 5;
    cout << "Faktorial dari " << number << " adalah " << factorial(number) << endl;
    return 0;
}

Penjelasan:

• Kasus Dasar: Jika n kurang dari atau sama dengan 1, faktorialnya adalah 1.
• Panggilan Rekursif: Untuk nilai n yang lebih besar dari 1, fungsi factorial memanggil dirinya sendiri dengan parameter n - 1.