Analisis Fungsi Rekursif

Fungsi rekursif adalah algoritma yang memanggil dirinya sendiri dengan input yang lebih kecil. Menganalisis kompleksitas rekursif berbeda dari loop karena jumlah operasi total bergantung pada berapa kali fungsi memanggil dirinya sendiri dan berapa pekerjaan yang dilakukan setiap pemanggilan. Pada Chapter ini kita akan memperkenalkan recurrence relation sebagai alat utama, lalu memecahkannya dengan tiga teknik: substitution method, recursion tree, dan (di Chapter master-theorem) Master Theorem.

Apa itu Recurrence Relation #

Recurrence relation adalah persamaan yang mendefinisikan fungsi berdasarkan dirinya sendiri pada input lebih kecil. Bentuk umum untuk analisis rekursif:

T(n) = a · T(n / b) + f(n)

dengan:

• a — jumlah sub-masalah rekursif (berapa kali fungsi memanggil dirinya sendiri).
• n / b — ukuran tiap sub-masalah (biasanya pembagian).
• f(n) — biaya di luar pemanggilan rekursif (combine, divide, atau base case handling).

Recurrence Relation untuk Fungsi Umum #

Teknik 1: Substitution Method #

Substitution method adalah teknik menebak solusi lalu membuktikannya dengan induksi matematis.

Contoh: T(n) = 2T(n/2) + n #

Tebakan: T(n) = O(n log n).

Bukti (sketsa): Asumsikan T(k) ≤ c·k log k untuk semua k < n. Maka:

T(n) = 2T(n/2) + n
     ≤ 2 · c · (n/2) log(n/2) + n
     = c n (log n - 1) + n
     = c n log n - c n + n
     = c n log n - (c - 1) n
     ≤ c n log n        (asalkan c ≥ 1)

Untuk c = 1 (atau lebih besar), pertidaksamaan terpenuhi untuk n yang cukup besar. ∎

Teknik 2: Recursion Tree #

Recursion tree memvisualisasikan pemanggilan rekursif sebagai pohon. Setiap node mewakili satu pemanggilan, dan anak-anaknya mewakili sub-masalah yang dipanggil.

Cara Menghitung Total Kerja #

1. Kerja per level: pada level k terdapat 2^k node, masing-masing bekerja n / 2^k. Total per level: 2^k × (n / 2^k) = n.
2. Jumlah level: pohon berhenti saat n / 2^k = 1, yaitu k = log₂ n.
3. Kerja total: n × log₂ n = n log n.

Kode: Visualisasi Recursion Tree untuk Merge Sort #

#include <iostream>
#include <vector>

int kedalaman = 0;
long long kerjaPerLevel[64] = {0};

void mergeSortTree(int n, int level) {
    if (n <= 1) {
        ++kerjaPerLevel[level];
        return;
    }
    kerjaPerLevel[level] += n;        // kerja combine O(n)
    mergeSortTree(n / 2, level + 1);
    mergeSortTree(n / 2, level + 1);
}

int main() {
    int n = 16;
    mergeSortTree(n, 0);

    int maxLevel = 0;
    while (maxLevel < 64 && kerjaPerLevel[maxLevel] > 0) ++maxLevel;

    long long total = 0;
    std::cout << "Level\tKerja\n";
    for (int i = 0; i < maxLevel; ++i) {
        std::cout << i << '\t' << kerjaPerLevel[i] << '\n';
        total += kerjaPerLevel[i];
    }
    std::cout << "Total kerja = " << total
              << " (n log n = " << 1LL * n * maxLevel << ")\n";
    return 0;
}

Output yang Dihasilkan:

Level	Kerja
0	16
1	16
2	16
3	16
4	16
Total kerja = 80 (n log n = 80)

Bedah Kode Baris-per-Baris #

1. Baris int kedalaman = 0; dan kerjaPerLevel[64]: variabel global untuk menyimpan akumulasi kerja pada setiap level. Kita batasi hingga 64 level (cukup untuk n hingga 2^64).
2. Baris if (n <= 1) { ++kerjaPerLevel[level]; return; }: base case. Kita menghitung 1 unit kerja untuk base case agar level terakhir tercatat.
3. Baris kerjaPerLevel[level] += n;: menyimulasikan biaya combine pada level saat ini. Pada level 0, kerjanya n = 16; pada level 1, dua sub-masalah masing-masing n/2 = 8, total 2 × 8 = 16; dan seterusnya.
4. Pemanggilan mergeSortTree(n/2, level+1) (dua kali): mensimulasikan dua sub-masalah rekursif yang masing-masing berukuran n/2.
5. Output: setiap level berkontribusi 16 (yaitu n) kerja, dan terdapat 5 level (log₂ 16 + 1 = 5). Total kerja 5 × 16 = 80 = n log n. Inilah inti argumen recursion tree.

Rekursi Linear vs Rekursi Bercabang #

Rekursi linear (satu pemanggilan rekursif per level) menghasilkan kedalaman n tetapi lebar 1, sehingga total operasi O(n). Rekursi bercabang (beberapa pemanggilan rekursif per level) menghasilkan pohon dengan lebar 2^level, sehingga total operasi bergantung pada kedalaman dan lebar.

Analisis Fibonacci Naif #

Fibonacci naif adalah contoh nyata bagaimana rekursi yang tidak hati-hati dapat menyebabkan kompleksitas eksponensial.

Mekanisme Fibonacci Naif #

Rumus F(n) = F(n-1) + F(n-2) menyebabkan F(n-2) dihitung dua kali: sekali sebagai bagian dari F(n-1), dan sekali secara langsung. Pola ini berulang pada setiap level, menghasilkan pohon rekursif dengan ~2ⁿ node.

Kode Program #

#include <iostream>

long long panggilan = 0;

int fib(int n) {
    ++panggilan;
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

int main() {
    for (int n : {5, 10, 15, 20, 25}) {
        panggilan = 0;
        int hasil = fib(n);
        std::cout << "fib(" << n << ") = " << hasil
                  << " | panggilan rekursif = " << panggilan << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

fib(5) = 5 | panggilan rekursif = 15
fib(10) = 55 | panggilan rekursif = 177
fib(15) = 610 | panggilan rekursif = 1973
fib(20) = 6765 | panggilan rekursif = 21891
fib(25) = 75025 | panggilan rekursif = 242785

Bedah Kode Baris-per-Baris #

1. Baris long long panggilan = 0;: variabel global yang menghitung jumlah pemanggilan rekursif. long long untuk menghindari overflow.
2. Baris if (n <= 1) return n;: base case. F(0) = 0, F(1) = 1.
3. Baris return fib(n-1) + fib(n-2);: dua pemanggilan rekursif. Inilah sumber ledakan eksponensial.
4. Output: jumlah panggilan tumbuh sangat cepat. Untuk n = 25, terdapat 242.785 panggilan rekursif. Pola pertumbuhan kira-kira ~1,6ⁿ (rasio emas), sesuai dengan O(φⁿ) = O(2ⁿ) secara longgar.
5. Implikasi: Fibonacci naif tidak praktis untuk n > 40. Solusi: gunakan memoization atau iterasi untuk menurunkan kompleksitas menjadi O(n).

Kapan Menggunakan Rekursi #

Rekursi cocok untuk masalah dengan struktur:

• Divide and conquer — masalah dapat dipecah menjadi sub-masalah independen (merge sort, quick sort, binary search).
• Struktur rekursif — data itu sendiri rekursif (tree, graph, nested structure).
• Backtracking — menjelajahi ruang solusi (permutasi, subset, maze solving).

Ringkasan #

• Recurrence relation T(n) = a·T(n/b) + f(n) adalah bentuk umum untuk analisis rekursif.
• Tiga teknik penyelesaian: substitution (tebak-buktikan), recursion tree (visualisasi pohon), dan Master Theorem (Chapter berikutnya).
• Rekursi linear menghasilkan O(n); rekursi bercabang seimbang dengan combine O(n) menghasilkan O(n log n).
• Fibonacci naif adalah contoh klasik rekursi yang tidak hati-hati menghasilkan O(2ⁿ).
• Pilih rekursi bila masalah memiliki struktur divide and conquer atau data rekursif; waspadai batas call stack.

Pada Chapter berikutnya kita akan mempelajari kompleksitas amortisasi — analisis khusus untuk operasi yang kadang mahal tetapi rata-rata murah, seperti push_back pada std::vector.