C++ | #20 Rekursi

 

Halo teman-teman!
Kali ini kita akan membahas konsep menarik dalam fungsi, yaitu rekursi. Rekursi sering membuat bingung pemula, tapi kalau dipahami dengan baik, rekursi bisa jadi alat yang sangat berguna.

---

Apa itu Rekursi

Rekursi adalah teknik pemrograman di mana sebuah fungsi memanggil dirinya sendiri.
Biasanya rekursi digunakan untuk menyelesaikan masalah yang bisa dipecah menjadi masalah yang lebih kecil dan serupa.

Contohnya:

• Menghitung faktorial

• Menghitung bilangan Fibonacci

• Traversal struktur data (tree, graph)

• Pemecahan masalah matematika yang berulang

---

Struktur Dasar Rekursi

Sebuah fungsi rekursif memiliki dua bagian penting:

1. Base case → kondisi berhenti, agar fungsi tidak memanggil dirinya tanpa henti.

2. Recursive call → bagian di mana fungsi memanggil dirinya sendiri dengan data yang lebih kecil.

Bentuk umumnya:

tipe_data namaFungsi(parameter) {
    if (kondisi_berhenti) {
        return hasil; // base case
    } else {
        return namaFungsi(parameter_baru); // recursive call
    }
}

---

Contoh 1: Fungsi Faktorial

Faktorial dari sebuah bilangan n didefinisikan sebagai:

• n! = n × (n-1) × (n-2) × ... × 1

• 0! = 1 (base case)

Mari kita coba implementasikan dengan rekursi:

#include <iostream>
using namespace std;

int faktorial(int n) {
    if (n == 0) {
        return 1; // base case
    } else {
        return n * faktorial(n - 1); // recursive call
    }
}

int main() {
    cout << "Faktorial 5 = " << faktorial(5) << endl;
    return 0;
}

Output:

Faktorial 5 = 120

---

Contoh 2: Deret Fibonacci

Deret Fibonacci adalah deret angka di mana setiap angka merupakan hasil penjumlahan dua angka sebelumnya.
Rumus:

• F(0) = 0

• F(1) = 1

• F(n) = F(n-1) + F(n-2)

Implementasi dengan rekursi:

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if (n == 0) return 0; // base case
    if (n == 1) return 1; // base case
    return fibonacci(n - 1) + fibonacci(n - 2); // recursive call
}

int main() {
    for (int i = 0; i < 10; i++) {
        cout << fibonacci(i) << " ";
    }
    cout << endl;
    return 0;
}

Output:

0 1 1 2 3 5 8 13 21 34

---

Rekursi vs Iterasi

Sebenarnya, banyak masalah rekursif bisa diselesaikan dengan perulangan (iterasi).
Contoh faktorial:

Versi iterasi:

int faktorialIterasi(int n) {
    int hasil = 1;
    for (int i = 1; i <= n; i++) {
        hasil *= i;
    }
    return hasil;
}

Versi rekursi lebih ringkas, tapi iterasi sering lebih efisien dalam penggunaan memori dan kecepatan.

---

Risiko Rekursi

Walaupun rekursi itu elegan, ada beberapa hal yang perlu diperhatikan:

1. Stack overflow
   Jika base case tidak jelas atau data terlalu besar, fungsi bisa memanggil dirinya terlalu dalam dan menyebabkan error stack overflow.

2. Kurang efisien
   Beberapa masalah (seperti Fibonacci) sangat lambat jika hanya menggunakan rekursi sederhana, karena banyak perhitungan berulang.

3. Sulit dipahami pemula
   Rekursi butuh logika yang lebih abstrak, sehingga lebih sulit dipahami di awal.

---

Kesimpulan

• Rekursi adalah fungsi yang memanggil dirinya sendiri.

• Harus punya base case agar tidak berjalan tanpa henti.

• Cocok digunakan untuk masalah yang berulang atau berbentuk pecahan dari masalah yang sama.

• Bisa diganti dengan iterasi, tetapi rekursi sering membuat kode lebih sederhana dan elegan.

• Hati-hati dengan performa dan risiko stack overflow.