Rekursi dalam Pemrograman

Pendahuluan

Rekursi adalah teknik pemrograman di mana sebuah fungsi memanggil dirinya sendiri untuk menyelesaikan sebuah masalah yang lebih besar dengan memecahnya menjadi sub-masalah yang lebih kecil. Teknik ini sangat berguna dalam memecahkan masalah yang memiliki sifat rekursif secara alami, seperti pemrosesan struktur data hierarkis (contohnya pohon atau graf), perhitungan matematis rekursif (faktorial, deret Fibonacci), atau algoritma pembagian dan penaklukan (divide and conquer) seperti pencarian biner dan pengurutan cepat (quick sort).

Sintaks Dasar Rekursi

Fungsi rekursif harus memiliki:

1. Base case (kasus dasar): Kondisi di mana fungsi berhenti memanggil dirinya sendiri.
2. Recursive case (kasus rekursif): Kondisi di mana fungsi memanggil dirinya sendiri untuk menyelesaikan sub-masalah.

Contoh Rekursi

1. Faktorial

C++ Implementation:

#include <iostream>
using namespace std;

int factorial(int n) {
    if (n == 0 || n == 1)  // Base case
        return 1;
    return n * factorial(n - 1);  // Recursive case
}

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

Python Implementation:

def factorial(n):
    if n == 0 or n == 1:  # Base case
        return 1
    return n * factorial(n - 1)  # Recursive case

num = 5
print(f"Faktorial dari {num} adalah {factorial(num)}")

2. Deret Fibonacci

C++ Implementation:

#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 case
}

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

Python Implementation:

def fibonacci(n):
    if n == 0:  # Base case
        return 0
    if n == 1:  # Base case
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)  # Recursive case

n = 10
print([fibonacci(i) for i in range(n)])

Kapan Rekursi Lebih Cocok Dibandingkan Perulangan?

Rekursi lebih cocok digunakan pada kasus berikut:

1. Masalah Hierarkis atau Berbasis Pohon
   Rekursi sangat alami untuk masalah yang melibatkan struktur pohon seperti traversal pohon biner (preorder, inorder, postorder).
2. Algoritma Divide and Conquer
   Contoh: Merge Sort, Quick Sort, atau algoritma pencarian biner.
3. Masalah dengan Definisi Rekursif
   Masalah seperti deret Fibonacci atau faktorial yang memiliki definisi matematika rekursif.
4. Backtracking
   Contoh: Problem pemecahan labirin, n-Queens, atau Sudoku.
5. Keindahan Kode
   Rekursi sering menghasilkan kode yang lebih singkat dan mudah dipahami dibandingkan loop dalam masalah tertentu.

Kelemahan Rekursi

Namun, rekursi memiliki kelemahan, seperti:

• Overhead Memori: Setiap pemanggilan fungsi membutuhkan memori untuk stack, sehingga rekursi dalam kedalaman besar dapat menyebabkan stack overflow.
• Efisiensi: Rekursi yang tidak dioptimalkan (contohnya Fibonacci di atas) memiliki kompleksitas waktu yang tinggi dibandingkan implementasi iteratif yang lebih efisien.

Rekursi vs Iterasi

Kesimpulan

Rekursi adalah alat yang sangat kuat dalam pemrograman, terutama untuk masalah dengan struktur rekursif alami. Namun, pemilihan antara rekursi dan iterasi harus mempertimbangkan efisiensi memori, kecepatan, dan kejelasan kode.