Saat mulai mempelajari C++, Anda akan menemukan berbagai cara untuk menyelesaikan sebuah masalah. Salah satu teknik yang cukup menarik adalah rekursi. Meskipun awalnya terlihat rumit, konsep rekursi sebenarnya sangat mudah dipahami jika dipelajari langkah demi langkah.

Rekursi sering digunakan untuk menyelesaikan masalah yang memiliki pola berulang, seperti menghitung faktorial, deret Fibonacci, pencarian pada struktur data, hingga algoritma seperti Quick Sort dan Merge Sort.

Pada artikel ini, Anda akan mempelajari apa itu rekursi di C++, bagaimana cara kerjanya, serta contoh program sederhana yang cocok untuk pemula.

Apa Itu Rekursi di C++?

Rekursi adalah teknik pemrograman di mana sebuah fungsi memanggil dirinya sendiri hingga mencapai kondisi tertentu yang disebut base case.

Dengan kata lain, fungsi akan terus berjalan secara berulang sampai syarat penghentian terpenuhi.

Ilustrasi sederhananya:

fungsi()
    ↓
fungsi()
    ↓
fungsi()
    ↓
Base Case
    ↓
Program selesai

Tanpa base case, fungsi akan terus memanggil dirinya sendiri dan menyebabkan program mengalami stack overflow.

Komponen Penting Rekursi

Sebuah fungsi rekursif memiliki dua bagian utama.

1. Base Case

Base case adalah kondisi yang menghentikan proses rekursi.

Contohnya:

if(n == 0)
    return 1;

Jika kondisi ini tercapai, fungsi tidak akan memanggil dirinya sendiri lagi.

2. Recursive Case

Bagian ini berisi pemanggilan fungsi itu sendiri.

return n * faktorial(n - 1);

Di sinilah proses rekursi berlangsung hingga mencapai base case.

Contoh Rekursi Menghitung Faktorial

Program berikut menghitung nilai faktorial menggunakan rekursi.

#include <iostream>

using namespace std;

int faktorial(int n)
{
    if(n == 0)
    {
        return 1;
    }

    return n * faktorial(n - 1);
}

int main()
{
    int angka;

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

    cout << "Faktorial = " << faktorial(angka);

    return 0;
}

Contoh Output

Masukkan angka : 5
Faktorial = 120

Cara Kerja Program Faktorial

Misalnya pengguna memasukkan angka 5.

Proses yang terjadi adalah:

faktorial(5)
↓

5 × faktorial(4)
↓

5 × 4 × faktorial(3)
↓

5 × 4 × 3 × faktorial(2)
↓

5 × 4 × 3 × 2 × faktorial(1)
↓

5 × 4 × 3 × 2 × 1 × faktorial(0)
↓

Base Case

return 1

Kemudian hasilnya dikembalikan secara berurutan hingga menjadi:

5 × 4 × 3 × 2 × 1 = 120

Contoh Rekursi Menghitung Penjumlahan

Misalnya kita ingin menjumlahkan angka dari 1 sampai n.

#include <iostream>

using namespace std;

int jumlah(int n)
{
    if(n == 1)
        return 1;

    return n + jumlah(n - 1);
}

int main()
{
    cout << jumlah(5);

    return 0;
}

Output:

Karena:

1 + 2 + 3 + 4 + 5 = 15

Contoh Rekursi Deret Fibonacci

Rekursi juga sering digunakan untuk menghitung deret Fibonacci.

#include <iostream>

using namespace std;

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

    if(n == 1)
        return 1;

    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main()
{
    int n = 8;

    cout << fibonacci(n);

    return 0;
}

Output:

Deret Fibonacci:

0 1 1 2 3 5 8 13 21

Rekursi vs Perulangan

Banyak pemula bertanya, lebih baik menggunakan rekursi atau perulangan?

Berikut perbandingannya.

Rekursi	Perulangan
Kode lebih ringkas	Lebih cepat dieksekusi
Mudah digunakan pada algoritma tertentu	Lebih hemat memori
Cocok untuk struktur data pohon	Cocok untuk proses sederhana
Menggunakan stack memory	Tidak menggunakan recursive call

Untuk kasus sederhana seperti menghitung angka dari 1 sampai 100, perulangan biasanya lebih efisien.

Namun, untuk algoritma tertentu seperti DFS (Depth First Search), Tree Traversal, atau Quick Sort, rekursi sering menjadi pilihan yang lebih tepat.

Kelebihan Rekursi

Menggunakan rekursi memiliki beberapa keuntungan, di antaranya:

Kode lebih singkat dan mudah dibaca.
Cocok untuk masalah yang memiliki pola berulang.
Mempermudah implementasi algoritma kompleks.
Banyak digunakan pada struktur data seperti tree dan graph.

Kekurangan Rekursi

Selain memiliki kelebihan, rekursi juga memiliki beberapa kekurangan.

Menggunakan lebih banyak memori.
Bisa lebih lambat dibanding perulangan.
Berisiko mengalami stack overflow jika tidak memiliki base case.
Sulit dipahami oleh pemula jika belum memahami alur pemanggilan fungsi.

Kesalahan yang Sering Dilakukan Pemula

Saat belajar rekursi, beberapa kesalahan berikut cukup sering terjadi.

Tidak Membuat Base Case

Contoh yang salah:

int fungsi(int n)
{
    return fungsi(n - 1);
}

Program tersebut tidak memiliki kondisi berhenti sehingga akan terus memanggil dirinya sendiri.

Base Case Tidak Pernah Tercapai

Misalnya:

return fungsi(n + 1);

Nilai n justru semakin besar sehingga base case tidak akan pernah terpenuhi.

Salah Menentukan Nilai Kembalian

Banyak pemula lupa menggunakan return ketika memanggil fungsi rekursif.

Contoh yang benar:

return n * faktorial(n - 1);

Kapan Rekursi Digunakan?

Rekursi banyak digunakan dalam berbagai algoritma, seperti:

Faktorial.
Deret Fibonacci.
Binary Tree.
Depth First Search (DFS).
Quick Sort.
Merge Sort.
Backtracking.
Flood Fill.
Menelusuri folder dan file.

Karena itulah rekursi merupakan salah satu konsep penting yang perlu dikuasai oleh programmer C++.

Tips Belajar Rekursi

Agar lebih mudah memahami rekursi, Anda bisa mencoba beberapa tips berikut.

Pahami terlebih dahulu cara kerja fungsi biasa.
Selalu tentukan base case sebelum menulis recursive call.
Gambarkan alur pemanggilan fungsi di atas kertas.
Mulailah dari contoh sederhana seperti faktorial dan penjumlahan.
Latih kemampuan dengan berbagai soal rekursi.

Semakin sering berlatih, semakin mudah Anda memahami pola kerja rekursi.

Kesimpulan

Rekursi di C++ adalah teknik pemrograman yang memungkinkan sebuah fungsi memanggil dirinya sendiri untuk menyelesaikan suatu masalah. Agar berjalan dengan benar, fungsi rekursif harus memiliki base case sebagai kondisi penghentian.

Walaupun terkadang lebih lambat dibandingkan perulangan, rekursi sangat berguna dalam berbagai algoritma dan struktur data yang kompleks. Oleh karena itu, memahami rekursi akan membantu Anda menjadi programmer C++ yang lebih baik.

Belajar Rekursi di C++ dengan Contoh Sederhana