Pengenalan Rekursi

Rekursi adalah teknik pemrograman ketika sebuah fungsi memanggil dirinya sendiri untuk menyelesaikan masalah. Alih-alih menggunakan perulangan, fungsi rekursif memecah masalah kompleks menjadi submasalah yang lebih kecil dan serupa hingga mencapai kasus sederhana yang dapat diselesaikan secara langsung.

Setiap fungsi rekursif harus memiliki dua komponen penting. Kasus dasar adalah kondisi yang menghentikan rekursi. Tanpanya, fungsi akan memanggil dirinya sendiri tanpa henti. Langkah rekursif adalah bagian saat fungsi memanggil dirinya sendiri dengan parameter yang diubah, sehingga setiap pemanggilan semakin mendekati kasus dasar.

Berikut contoh hitung mundur sederhana yang menunjukkan rekursi:

void countdown(int n) {
    if (n <= 0) {           // Kasus dasar: berhenti saat n mencapai 0
        std::cout << "Done!" << std::endl;
        return;
    }
    
    std::cout << n << std::endl;
    countdown(n - 1);       // Langkah rekursif: panggil dengan n-1
}

Saat kamu memanggil countdown(3), fungsi ini menampilkan 3, lalu memanggil countdown(2), yang menampilkan 2, lalu memanggil countdown(1), dan seterusnya hingga mencapai kasus dasar. Setiap pemanggilan fungsi menunggu pemanggilan berikutnya selesai sebelum berakhir, sehingga membentuk rantai pemanggilan yang akhirnya berurutan kembali hingga pemanggil awal.