Rekursi adalah teknik di mana sebuah fungsi memanggil dirinya sendiri untuk menyelesaikan sub-masalah yang lebih kecil. Banyak algoritma DSA — tree traversal, merge sort, backtracking, graph DFS — secara natural diekspresikan secara rekursif karena strukturnya yang berulang. Alih-alih menggunakan loop eksplisit, rekursi memecah masalah menjadi instance yang lebih kecil dari dirinya sendiri. Pada Chapter ini kita akan mempelajari konsep dasar rekursi, mekanisme kerja di balik layar, serta contoh klasik: factorial dan countdown.

Aturan: Fungsi yang Memanggil Diri Sendiri #

Secara formal, fungsi f disebut rekursif bila dalam tubuh fungsi terdapat panggilan ke f itu sendiri (rekursi langsung) atau melalui fungsi perantara (rekursi tidak langsung). Struktur umumnya selalu mengandung dua bagian:

  1. Base case: kondisi yang menyebabkan fungsi berhenti memanggil dirinya. Tanpa base case, rekursi berjalan selamanya.
  2. Recursive case: bagian di mana fungsi memanggil dirinya dengan input yang lebih kecil, mendekati base case.

Kedua bagian wajib ada. Tanpa base case → infinite recursion → stack overflow. Tanpa recursive case → fungsi biasa, bukan rekursif.

Mekanisme: Stack Frame per Pemanggilan #

Setiap kali fungsi rekursif dipanggil, compiler mengalokasikan stack frame baru di call stack. Stack frame berisi:

  • Parameter fungsi
  • Variabel lokal
  • Alamat pengembalian (return address)

Stack frame hanya dihancurkan setelah fungsi kembali. Untuk rekursi dalam n tingkat, ada n stack frame aktif bersamaan. Karena ukuran call stack terbatas (biasanya 1-8 MB di Linux), rekursi terlalu dalam menyebabkan stack overflow.

Contoh Klasik: Factorial #

Aturan #

n! = n × (n-1) × (n-2) × ... × 1, dengan 0! = 1 (base case).

Mekanisme #

Definisi rekursif: factorial(n) = n × factorial(n-1) untuk n > 0, factorial(0) = 1.

Kode: Factorial Rekursif #

cpp 
#include <iostream>

long long factorial(int n) {
    if (n <= 1) return 1;             // base case
    return n * factorial(n - 1);      // recursive case
}

int main() {
    for (int n : {0, 1, 5, 10}) {
        std::cout << "factorial(" << n << ") = " << factorial(n) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text 
factorial(0) = 1
factorial(1) = 1
factorial(5) = 120
factorial(10) = 3628800
  1. Baris if (n <= 1) return 1;: base case. n = 0 dan n = 1 sama-sama mengembalikan 1. Tanpa baris ini, fungsi akan memanggil factorial(-1), factorial(-2), … hingga stack overflow.
  2. Baris return n * factorial(n - 1);: recursive case. Sub-masalah factorial(n-1) diselesaikan dulu, hasilnya dikalikan n. Karena n-1 < n, sub-masalah mendekati base case.
  3. Urutan pemanggilan untuk n = 5: 5 * factorial(4) = 5 * 4 * factorial(3) = ... = 5 * 4 * 3 * 2 * 1 = 120.
  4. Tipe long long: factorial(20) = 2.43 × 10^18 hampir habis di long long. Untuk n > 20, gunakan BigInt atau library modular arithmetic.

Contoh: Countdown #

Aturan #

Cetak angka dari n ke 1 secara menurun, kemudian cetak "selesai".

Kode: Countdown Rekursif #

cpp 
#include <iostream>

void countdown(int n) {
    if (n == 0) {
        std::cout << "selesai\n";
        return;
    }
    std::cout << n << ' ';
    countdown(n - 1);
}

int main() {
    countdown(5);
    return 0;
}

Output yang Dihasilkan:

text 
5 4 3 2 1 selesai
  1. Baris if (n == 0): base case. Cetak "selesai" dan berhenti.
  2. Baris std::cout << n << ' ';: cetak n sebelum memanggil rekursif. Karena urutan ini, output dari terbesar ke terkecil.
  3. Baris countdown(n - 1);: recursive case dengan input n-1. Mendekati base case n = 0.
  4. Tipe kembalian void: fungsi rekursif tidak harus mengembalikan nilai; bisa melakukan efek samping seperti cetak.

Varian: Countdown Naik (Naik Setelah Rekursi) #

Bila kita tukar urutan: panggil rekursif dulu, lalu cetak, kita dapat urutan naik.

Kode: Countdown Naik #

cpp 
#include <iostream>

void count_up(int n) {
    if (n == 0) return;
    count_up(n - 1);
    std::cout << n << ' ';
}

int main() {
    count_up(5);
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
1 2 3 4 5
  1. Baris count_up(n - 1);: panggilan rekursif terjadi SEBELUM cetak. Ini berarti cetak baru terjadi saat rekursi “kembali” (unwinding).
  2. Urutan eksekusi: count_up(5) → count_up(4) → … → count_up(0) (return). Lalu cetak dimulai: 1 2 3 4 5.
  3. Pola umum: operasi sebelum panggilan rekursif dieksekusi pada saat “turun”; operasi setelah panggilan rekursif dieksekusi pada saat “naik”. Ini dasar dari pre-order dan post-order traversal pada tree.

Karakteristik Masalah yang Cocok untuk Rekursi #

Rekursi cocok untuk masalah dengan struktur berikut:

  1. Sub-masalah identik: masalah besar dapat dipecah menjadi versi lebih kecil dari dirinya sendiri.
  2. Base case jelas: ada kondisi terminasi yang well-defined.
  3. Kombinasi hasil: solusi sub-masalah dapat dikombinasikan menjadi solusi masalah besar.
  4. Struktur self-similar: tree, graph, fraktal, eksplorasi state.

Contoh: factorial (sub-masalah = n-1), Fibonacci (dua sub-masalah), merge sort (dua sub-array), tree DFS (sub-tree).

Verifikasi: Trace Rekursi #

Mari kita trace factorial(4) untuk memahami alur call stack.

Kode: Trace dengan Indentasi #

cpp 
#include <iostream>
#include <string>

long long factorial_traced(int n, int depth) {
    std::string indent(depth * 2, ' ');
    std::cout << indent << "masuk factorial(" << n << ")\n";

    if (n <= 1) {
        std::cout << indent << "base case, return 1\n";
        return 1;
    }
    long long sub = factorial_traced(n - 1, depth + 1);
    long long result = n * sub;
    std::cout << indent << "kembali: " << n << " * " << sub
              << " = " << result << '\n';
    return result;
}

int main() {
    long long hasil = factorial_traced(4, 0);
    std::cout << "hasil akhir: " << hasil << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
masuk factorial(4)
  masuk factorial(3)
    masuk factorial(2)
      masuk factorial(1)
      base case, return 1
    kembali: 2 * 1 = 2
  kembali: 3 * 2 = 6
kembali: 4 * 6 = 24
hasil akhir: 24
  1. Parameter depth: melacak kedalaman rekursi untuk indentasi visual. Setiap panggilan rekursif menambah depth + 1.
  2. Bagian “masuk”: dieksekusi saat turun ke sub-masalah. Indentasi bertambah seiring kedalaman.
  3. Bagian “kembali”: dieksekusi saat naik (unwinding). Indentasi berkurang.
  4. Pola LIFO: factorial(4) selesai paling akhir, padahal dipanggil paling awal. Struktur Last-In-First-Out sesuai sifat stack.

Ringkasan #

  • Rekursi adalah fungsi yang memanggil dirinya sendiri untuk menyelesaikan sub-masalah.
  • Dua bagian wajib: base case (terminasi) dan recursive case (sub-masalah lebih kecil).
  • Setiap panggilan rekursif membuat stack frame baru di call stack; rekursi terlalu dalam menyebabkan stack overflow.
  • Urutan operasi: sebelum panggilan rekursif = “turun”; setelah panggilan rekursif = “naik”.
  • Rekursi cocok untuk masalah dengan struktur self-similar: tree, fraktal, backtracking, divide-and-conquer.
  • Untuk masalah sederhana (factorial, countdown), iterasi biasanya lebih efisien — gunakan rekursi saat kejelasan kode lebih penting daripada sedikit overhead.