Beberapa masalah secara natural menghasilkan dua atau lebih sub-masalah per pemanggilan — contoh klasik: Fibonacci (fib(n-1) + fib(n-2)), tree traversal (kiri dan kanan), atau generate all subsets. Rekursi jenis ini disebut rekursi bercabang. Meskipun ekspresi kodenya elegan, kompleksitas waktunya bisa meledak eksponensial: fib(50) naif butuh miliaran pemanggilan. Pada Chapter ini kita akan membedah Fibonacci dan Tribonacci, mengukur ledakan eksponensial secara empiris, dan melihat sekilas solusinya: memoization yang menjadi pintu masuk ke dynamic programming.

Aturan: Dua atau Lebih Panggilan Rekursif #

Fungsi rekursif bercabang memanggil dirinya dua atau lebih kali dalam satu tubuh fungsi. Setiap pemanggilan membuat recursion tree — pohon dengan root fungsi awal, anak-anaknya adalah panggilan rekursif, dan seterusnya hingga daun (base case).

Untuk Fibonacci naif fib(n):

  • fib(n) = fib(n-1) + fib(n-2) untuk n > 1
  • fib(0) = 0, fib(1) = 1 (base case)

Pohon rekursif untuk fib(5):

Perhatikan fib(3) dihitung dua kali, fib(2) dihitung tiga kali. Inilah sumber inefisiensi.

Mekanisme: Ledakan Eksponensial #

Jumlah panggilan rekursif T(n) untuk fib(n) mengikuti recurrence:

  • T(0) = T(1) = 1 (base case: 1 panggilan)
  • T(n) = T(n-1) + T(n-2) + 1 (dua sub-panggilan + 1 untuk diri sendiri)

Solusi: T(n) = Θ(φ^n) di mana φ = (1 + √5)/2 ≈ 1.618 (golden ratio). Artinya fib(50) butuh sekitar 1.618^50 ≈ 2.4 × 10^10 panggilan rekursif — detik menit.

Kode: Fibonacci Naif #

cpp 
#include <iostream>

long long fib_naive(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return fib_naive(n - 1) + fib_naive(n - 2);
}

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

Output yang Dihasilkan:

text 
fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(5) = 5
fib(10) = 55
fib(20) = 6765
  1. Baris if (n <= 0) return 0;: base case pertama untuk n = 0 atau negatif.
  2. Baris if (n == 1) return 1;: base case kedua untuk n = 1.
  3. Baris return fib_naive(n - 1) + fib_naive(n - 2);: dua panggilan rekursif. Inilah yang menyebabkan ledakan eksponensial.
  4. Hasil fib(20) = 6765: benar secara matematis, tetapi perhatikan bahwa fib(50) tidak akan selesai dalam waktu yang wajar.

Mengukur Jumlah Panggilan #

Kode: Hitung Jumlah Panggilan Rekursif #

cpp 
#include <iostream>

long long g_calls = 0;

long long fib_counted(int n) {
    ++g_calls;
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return fib_counted(n - 1) + fib_counted(n - 2);
}

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

Output yang Dihasilkan:

text 
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 rekulsif: 242785
fib(30) = 832040 | panggilan rekursif: 2692537
  1. g_calls: variabel global yang menghitung setiap pemanggilan fungsi.
  2. Pola pertumbuhan: 15 → 177 → 1973 → 21891 → 242785 → 2692537. Setiap kenaikan n 5 satuan, jumlah panggilan kira-kira ×11 (karena φ^5 ≈ 11.09).
  3. fib(30) ≈ 2.7 juta panggilan: masih bisa dihitung dalam puluhan milidetik. Tapi fib(50) akan butuh ~2.9 miliar panggilan — menit-menit.
  4. Konfirmasi eksponensial: rasio T(n+5) / T(n) ≈ 11, sesuai φ^5 ≈ 11.09.

Tribonacci: Tiga Cabang #

Tribonacci adalah generalisasi Fibonacci dengan tiga suku sebelumnya:

  • trib(n) = trib(n-1) + trib(n-2) + trib(n-3) untuk n > 2
  • trib(0) = 0, trib(1) = 0, trib(2) = 1 (base case)

Sekarang ada tiga panggilan rekursif per node → ledakan lebih cepat.

Kode: Tribonacci Naif #

cpp 
#include <iostream>

long long g_calls = 0;

long long trib(int n) {
    ++g_calls;
    if (n < 2) return 0;
    if (n == 2) return 1;
    return trib(n - 1) + trib(n - 2) + trib(n - 3);
}

int main() {
    for (int n : {5, 10, 15, 20, 25}) {
        g_calls = 0;
        long long result = trib(n);
        std::cout << "trib(" << n << ") = " << result
                  << " | panggilan: " << g_calls << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text 
trib(5) = 4 | panggilan: 13
trib(10) = 81 | panggilan: 289
trib(15) = 1705 | panggilan: 6094
trib(20) = 35890 | panggilan: 128287
trib(25) = 755476 | panggilan: 2700421
  1. Baris trib(n-1) + trib(n-2) + trib(n-3): tiga panggilan rekursif. Setiap node memiliki 3 anak.
  2. Pertumbuhan: 13 → 289 → 6094 → 128287 → 2700421. Rasio per kenaikan 5: ~22×, ~21×, ~21×, ~21× — sesuai dengan basis eksponensial baru.
  3. Basis eksponensial Tribonacci: λ ≈ 1.839 (lebih besar dari φ ≈ 1.618 Fibonacci). Ledakan lebih cepat dari Fibonacci.
  4. trib(25) butuh 2.7 juta panggilan — untuk Fibonacci, fib(25) hanya butuh 243 ribu. Tribonacci meledak ~11x lebih cepat.

Memoization: Solusi Ledakan Eksponensial #

Akar masalah: sub-masalah yang sama dihitung berulang kali. Solusi: simpan hasil yang sudah dihitung, gunakan kembali bila diminta lagi. Teknik ini disebut memoization.

Kode: Fibonacci dengan Memoization #

cpp 
#include <iostream>
#include <vector>

long long g_calls = 0;
std::vector<long long> g_memo;

long long fib_memo(int n) {
    ++g_calls;
    if (n <= 0) return 0;
    if (n == 1) return 1;
    if (g_memo[n] != -1) return g_memo[n];
    g_memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
    return g_memo[n];
}

int main() {
    int n = 40;
    g_memo.assign(n + 1, -1);
    g_calls = 0;
    long long result = fib_memo(n);
    std::cout << "fib_memo(" << n << ") = " << result << '\n';
    std::cout << "panggilan rekursif: " << g_calls << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
fib_memo(40) = 102334155
panggilan rekursif: 79
  1. Baris if (g_memo[n] != -1) return g_memo[n];: bila hasil sudah ada di memo, langsung kembalikan. Tidak ada panggilan rekursif tambahan.
  2. Baris g_memo[n] = fib_memo(n - 1) + fib_memo(n - 2);: hitung sekali, simpan ke memo.
  3. fib(40) = 102334155: dengan memoization, hanya butuh 79 panggilan rekursif. Tanpa memo, fib(40) butuh ~331 juta panggilan.
  4. Kompleksitas: O(n) waktu dan O(n) ruang. Memoization mengubah eksponensial menjadi linier.

Versi Iteratif Fibonacci #

Bila hanya butuh nilai fib(n), versi iteratif paling efisien: O(n) waktu, O(1) ruang.

Kode: Fibonacci Iteratif O(1) Space #

cpp 
#include <iostream>

long long fib_iter(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    long long prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; ++i) {
        long long cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

int main() {
    for (int n : {10, 20, 50, 90}) {
        std::cout << "fib_iter(" << n << ") = " << fib_iter(n) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text 
fib_iter(10) = 55
fib_iter(20) = 6765
fib_iter(50) = 12586269025
fib_iter(90) = 2880067194370816120
  1. Variabel prev2, prev1: hanya menyimpan dua suku terakhir. Tidak ada array, tidak ada rekursi.
  2. Loop dari 2 hingga n: update prev1 dan prev2 setiap iterasi.
  3. Kompleksitas: O(n) waktu, O(1) ruang. Paling efisien untuk Fibonacci.
  4. fib(90) ≈ 2.88 × 10^18: masih muat di long long (maks ~9.2 × 10^18).

Rekursi Bercabang Lain: Kombinasi dan Subsets #

Rekursi bercabang tidak hanya untuk Fibonacci. Contoh lain:

  • Subsets: setiap elemen bisa masuk atau tidak → 2 cabang per elemen → 2^n total.
  • Permutations: setiap posisi bisa diisi oleh elemen yang tersisa → n! total.
  • Tree DFS: 2 cabang per node (kiri, kanan) → O(n) total bila tidak ada subtree duplikat.

Perbedaan dengan Fibonacci: tree DFS mengunjungi setiap node tepat sekali, sehingga tetap O(n). Fibonacci naif mengunjungi sub-masalah yang sama berulang kali → eksponensial.

Ringkasan #

  • Rekursi bercabang memanggil dirinya dua atau lebih kali per pemanggilan → membentuk recursion tree.
  • Fibonacci naif: 2 cabang per node → O(φ^n) ≈ O(1.618^n). fib(50) tidak praktis.
  • Tribonacci: 3 cabang → O(λ^n) ≈ O(1.839^n). Lebih cepat meledak dari Fibonacci.
  • Memoization menyimpan hasil sub-masalah → transformasi dari eksponensial ke polinomial.
  • Versi iteratif Fibonacci: O(n) waktu, O(1) ruang — paling efisien.
  • Rekursi bercabang tidak selalu eksponensial: bila setiap sub-masalah unik (misal tree DFS), total tetap O(n).