Base Case dan Recursive Case

Setiap fungsi rekursif yang benar memiliki dua bagian wajib: base case yang menghentikan rekursi dan recursive case yang memanggil diri sendiri dengan input lebih kecil. Tanpa salah satunya, fungsi tidak dapat diklasifikasikan sebagai rekursif yang valid. Base case yang hilang menyebabkan rekursi tak terhingga yang berakhir dengan stack overflow — runtime error yang sulit didebug karena pesannya sering tidak menyebut penyebab asli. Pada Chapter ini kita akan membedah kedua komponen ini, melihat contoh negatif (rekursi tanpa base case), serta pola yang sering salah seperti base case yang tidak tercapai karena loncatan input salah.

Anatomy Fungsi Rekursif #

Struktur wajib sebuah fungsi rekursif:

return_type f(input):
    if base_condition(input):
        return base_value      // BASE CASE — berhenti
    else:
        return combine(f(smaller_input))   // RECURSIVE CASE

Tiga elemen kritis:

1. Base condition: tes yang menentukan kapan rekursi berhenti. Harus dapat dicapai dari recursive case dalam langkah terbatas.
2. Base value: nilai yang dikembalikan saat base condition true. Tidak boleh memanggil f lagi.
3. Smaller input: input pada recursive case HARUS lebih dekat ke base condition. Bila tidak, base case tak tercapai.

Base Case yang Hilang: Rekursi Tak Terhingga #

Kode: Factorial Tanpa Base Case ( akan crash) #

#include <iostream>

// BAHAYA: tanpa base case, rekursi tidak pernah berhenti
long long factorial_buggy(int n) {
    return n * factorial_buggy(n - 1);  // tidak ada if (n <= 1)
}

// Versi aman untuk demonstrasi: batasi dengan depth counter
long long factorial_safe(int n, int depth) {
    if (depth > 20) {  // safety net buatan
        std::cout << "[safety net triggered at depth 20]\n";
        return 1;
    }
    return n * factorial_safe(n - 1, depth + 1);
}

int main() {
    long long hasil = factorial_safe(5, 0);
    std::cout << "hasil buggy (dengan safety net): " << hasil << '\n';
    return 0;
}

Output yang Dihasilkan:

[safety net triggered at depth 20]
hasil buggy (dengan safety net): 0

1. Tanpa factorial_buggy dipanggil langsung — akan menyebabkan stack overflow dan program crash. Kita tidak memanggilnya di main.
2. Fungsi factorial_safe: meniru perilaku buggy tetapi dengan safety net buatan pada depth = 20. Setelah 20 panggilan, rekursi berhenti paksa dan mengembalikan 1.
3. Hasil 0: 5 * 4 * 3 * 2 * 1 * 0 * (-1) * ... * (-14) * 1 = 0. Hasil tidak akurat karena rekursi berhenti di tempat yang salah.
4. Pesannya: tanpa base case, fungsi tidak pernah berhenti secara natural. Safety net di sini hanya untuk demonstrasi — kode produksi tidak boleh bergantung pada trik ini.

Base Case yang Tidak Tercapai #

Kode: Input Tidak Mendekati Base Case #

#include <iostream>

// BUG: base case (n == 0), tapi recursive case memanggil factorial(n + 1)
// input tidak pernah mendekati 0
long long factorial_wrong(int n) {
    if (n == 0) return 1;
    return n * factorial_wrong(n + 1);  // n+1, bukan n-1 — JAUH dari 0
}

// Versi aman dengan safety net
long long factorial_wrong_safe(int n, int depth) {
    if (n == 0) return 1;
    if (depth > 10) {
        std::cout << "[safety net at depth " << depth << ", n = " << n << "]\n";
        return 1;
    }
    return n * factorial_wrong_safe(n + 1, depth + 1);
}

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

Output yang Dihasilkan:

[safety net at depth 11, n = 16]
hasil: 54486432000

1. Base case if (n == 0) ada, tetapi recursive case factorial_wrong(n + 1) malah menjauhkan input dari 0. Mulai dari n = 5, urutan pemanggilan: 5, 6, 7, 8, ... tidak pernah menyentuh 0.
2. Hasil tidak akurat: 5 * 6 * 7 * ... * 15 * 1 = 54486432000 (perkalian sampai n = 15, kemudian safety net di n = 16 mengembalikan 1). Tanpa safety net, akan stack overflow.
3. Pelajaran: base case benar + recursive case salah = rekursi tidak berhenti. Selalu pastikan recursive case MENGURANGI jarak ke base case.

Base Case dengan Multiple Conditions #

Beberapa fungsi memerlukan lebih dari satu base case. Contoh klasik: Fibonacci.

Kode: Fibonacci dengan Dua Base Case #

#include <iostream>

long long fib(int n) {
    if (n == 0) return 0;   // base case 1
    if (n == 1) return 1;   // base case 2
    return fib(n - 1) + fib(n - 2);
}

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

Output yang Dihasilkan:

fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(5) = 5
fib(10) = 55

1. Base case n == 0 dan n == 1: dua nilai terminasi karena fib(n) = fib(n-1) + fib(n-2) memerlukan dua nilai awal.
2. Recursive case fib(n-1) + fib(n-2): dua panggilan rekursif. Kedua input lebih kecil dari n, jadi keduanya mendekati base case.
3. Hasil: sesuai definisi Fibonacci standar. fib(10) = 55.
4. Catatan: implementasi ini eksponensial O(2^n) — akan kita bedah di Chapter rekursi bercabang.

Recursive Case: Memanggil dengan Input Lebih Kecil #

Aturan #

Pada recursive case, parameter yang dilewatkan ke panggilan rekursif harus lebih dekat ke base case. Cara paling umum:

1. Kurangi dengan konstanta: f(n - 1), f(n - 2). Cocok untuk masalah linier.
2. Bagi dua: f(lo, mid), f(mid+1, hi). Cocok untuk divide-and-conquer.
3. Reduksi struktur: f(s.tail()), f(s.substr(1)). Cocok untuk string/list.

Kode: Pangkat Rekursif (Pemangkatan Berulang) #

#include <iostream>

long long power(int base, int exp) {
    if (exp == 0) return 1;          // base case
    return base * power(base, exp - 1);  // recursive case
}

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

Output yang Dihasilkan:

2^0 = 1
2^1 = 2
2^5 = 32
2^10 = 1024

1. Base case exp == 0: base^0 = 1 untuk base apa pun (kecuali 0^0 yang kontroversial).
2. Recursive case base * power(base, exp - 1): kurangi exp dengan 1. Setiap panggilan mendekati exp = 0.
3. Kompleksitas: O(n) panggilan rekursif untuk exp = n. Bisa dioptimalkan ke O(log n) dengan fast exponentiation.

Recursive Case Berbasis Struktur (Array) #

Kode: Sum Array Rekursif #

#include <iostream>
#include <vector>

long long sum_rec(const std::vector<int>& a, size_t i) {
    if (i == a.size()) return 0;  // base case
    return a[i] + sum_rec(a, i + 1);  // recursive case
}

int main() {
    std::vector<int> a = {1, 2, 3, 4, 5};
    std::cout << "sum = " << sum_rec(a, 0) << '\n';
    return 0;
}

Output yang Dihasilkan:

sum = 15

1. Parameter size_t i: indeks yang sedang diproses. Pemanggil awal melewatkan 0.
2. Base case i == a.size(): semua elemen telah diproses. Kembalikan 0 (identitas penjumlahan).
3. Recursive case a[i] + sum_rec(a, i + 1): tambahkan elemen saat ini dengan sum sisanya.
4. Kompleksitas: O(n) waktu, O(n) ruang untuk stack frame. Iterasi for loop lebih efisien di sini.

Pola Umum Base Case #

Pola umum untuk berbagai kelas masalah:

Verifikasi: Apakah Base Case Dapat Dicapai? #

Sebelum menulis fungsi rekursif, lakukan checklist:

1. Apakah ada base case? Bila tidak, tambahkan.
2. Apakah recursive case mengurangi jarak ke base case? Bila tidak (misal n + 1), perbaiki.
3. Apakah semua jalur eksekusi mencapai base case? Bila ada jalur yang memanggil tanpa reduksi, infinite loop.
4. Apakah base case menangani semua input awal? Misal factorial(-5) dengan base case n == 0 tidak akan tercapai. Tambahkan validasi atau ubah ke n <= 1.

Kode: Validasi Input pada Factorial #

#include <iostream>
#include <stdexcept>

long long factorial_safe(int n) {
    if (n < 0) {
        throw std::invalid_argument("factorial tidak terdefinisi untuk n < 0");
    }
    if (n <= 1) return 1;          // base case setelah validasi
    return n * factorial_safe(n - 1);
}

int main() {
    try {
        std::cout << "factorial(5) = " << factorial_safe(5) << '\n';
        std::cout << "factorial(-3) = " << factorial_safe(-3) << '\n';
    } catch (const std::exception& e) {
        std::cout << "error: " << e.what() << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

factorial(5) = 120
error: factorial tidak terdefinisi untuk n < 0

1. Baris if (n < 0) throw ...: validasi input sebelum rekursi. Mencegah base case n <= 1 tercapai dari jalur negatif.
2. Tanpa validasi, factorial_safe(-3) akan memanggil factorial_safe(-4), factorial_safe(-5), … hingga overflow.
3. Pelajaran: base case yang benar untuk input valid bisa salah untuk input tak valid. Selalu validasi terlebih dahulu.

Ringkasan #

• Setiap fungsi rekursif wajib memiliki base case (terminasi) dan recursive case (memanggil diri sendiri dengan input lebih kecil).
• Base case yang hilang → infinite recursion → stack overflow.
• Base case yang benar tetapi recursive case salah arah (misal n + 1) → base case tidak tercapai.
• Beberapa fungsi butuh multiple base case (misal Fibonacci dengan n == 0 dan n == 1).
• Recursive case mengurangi jarak ke base case: numerik (n - 1), array (i + 1), struktur (sub-tree, substr).
• Selalu validasi input sebelum rekursi untuk mencegah kasus tak terduga yang membuat base case tak tercapai.