🎯 Tujuan Pembelajaran

Setelah pertemuan ini, mahasiswa mampu:

1. Menganalisis algoritma rekursif dengan base case & recursive case
2. Menghitung kompleksitas dengan recurrence relation
3. Menerapkan Master Theorem
4. Mengimplementasikan memoization untuk optimasi
5. Menerapkan paradigma divide-and-conquer

📋 Agenda

1. Review Rekursi & Tracing
2. Analisis Kompleksitas dengan Recurrence Relation
3. Master Theorem
4. Tail Recursion & Optimasi
5. Memoization
6. Paradigma Divide-and-Conquer
7. Binary Search & Tower of Hanoi

BAGIAN 1

📖 Review Rekursi

📖 Apa itu Rekursi?

💻 Anatomi Fungsi Rekursif

returnType fungsiRekursif(parameter) {
    // Base case: kondisi berhenti
    if (kondisiBerhenti) {
        return nilaiDasar;
    }
    // Recursive case: pemanggilan diri sendiri
    return fungsiRekursif(parameterYangLebihKecil);
}
                

💻 Contoh Klasik: Faktorial

int faktorial(int n) {
    // Base case
    if (n <= 1) {
        return 1;
    }
    // Recursive case
    return n * faktorial(n - 1);
}
// faktorial(5) → 5 × 4 × 3 × 2 × 1 = 120
                

🔍 Tracing Rekursi

Call stack turun (pemanggilan) lalu naik (return values)

📊 Tabel Tracing faktorial(5)

BAGIAN 2

📈 Analisis Kompleksitas Rekursi

📈 Recurrence Relation

🌳 Metode Pohon Rekursi

Total cost = n × (log₂n + 1) = O(n log n)

BAGIAN 3

🎓 Master Theorem

🎓 Master Theorem

Untuk T(n) = aT(n/b) + f(n), bandingkan f(n) dengan n^(log_b(a)):

📐 Flowchart Master Theorem

🧠 Contoh: T(n) = 4T(n/2) + n

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

Ini adalah kompleksitas Merge Sort!

• a = 2, b = 2, f(n) = n
• log₂(2) = 1 → n^(log_b(a)) = n¹ = n
• f(n) = n = Θ(n¹) → Kasus 2

BAGIAN 4

🔧 Tail Recursion dan Optimasi

🔧 Apa itu Tail Recursion?

return n * faktorial(n-1);
// Operasi × SETELAH rekursi
                        

return faktorialTail(n-1, n*acc);
// Rekursi adalah TERAKHIR
                        

📊 Perbandingan Stack Usage

*dengan Tail Call Optimization (TCO)

💻 Contoh: Faktorial Tail Recursive

int faktorialTail(int n, int acc = 1) {
    if (n <= 1) return acc;     // Base: return accumulator
    return faktorialTail(n-1, n*acc);  // Tail recursive
}

// Tracing faktorialTail(5, 1):
// (5, 1) → (4, 5) → (3, 20) → (2, 60) → (1, 120) → 120
                

BAGIAN 5

💾 Memoization

💾 Konsep Memoization

// O(2^n) - sangat lambat!
int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);  // Banyak duplikasi!
}
                    

🔴 Overlapping Subproblems

fib(3) dihitung 2 kali, fib(2) dihitung 3 kali!

💻 Fibonacci dengan Memoization

unordered_map<int, long long> memo;

long long fibMemo(int n) {
    if (n <= 1) return n;
    // Cek apakah sudah pernah dihitung
    if (memo.find(n) != memo.end()) {
        return memo[n];  // Return dari cache
    }
    // Hitung dan simpan
    memo[n] = fibMemo(n-1) + fibMemo(n-2);
    return memo[n];
}
                

📊 Perbandingan Performa

*dengan TCO

BAGIAN 6

⚔️ Paradigma Divide-and-Conquer

⚔️ Divide-and-Conquer

📊 Visualisasi Divide-and-Conquer

📊 Algoritma D&C Klasik

*average case

BAGIAN 7

🔍 Binary Search

🔍 Binary Search

💻 Binary Search Rekursif

int binarySearch(int arr[], int left, int right, int target) {
    if (left > right) return -1;  // Base: tidak ditemukan
    
    // Divide: hitung titik tengah
    int mid = left + (right - left) / 2;
    
    // Conquer
    if (arr[mid] == target)
        return mid;
    else if (target < arr[mid])
        return binarySearch(arr, left, mid-1, target);
    else
        return binarySearch(arr, mid+1, right, target);
}
                

📐 Analisis Binary Search

Recurrence: T(n) = T(n/2) + O(1)

BAGIAN 8

🗼 Tower of Hanoi

🗼 Deskripsi Masalah

🧠 Strategi Divide-and-Conquer

1. Divide: Pindahkan n-1 disk dari A ke B (pakai C)
2. Conquer: Pindahkan disk terbesar dari A ke C
3. Combine: Pindahkan n-1 disk dari B ke C (pakai A)

💻 Implementasi Tower of Hanoi

void hanoi(int n, char src, char dst, char aux) {
    if (n == 1) {
        cout << "Pindah disk 1: " << src << " → " << dst << endl;
        return;
    }
    
    // Pindahkan n-1 disk ke auxiliary
    hanoi(n-1, src, aux, dst);
    
    // Pindahkan disk terbesar ke destination
    cout << "Pindah disk " << n << ": " << src << " → " << dst << endl;
    
    // Pindahkan n-1 disk ke destination
    hanoi(n-1, aux, dst, src);
}
                

📊 Kompleksitas Tower of Hanoi

BAGIAN 9

🔄 Konversi Rekursi ke Iterasi

🔄 Mengapa Mengkonversi?

💻 Contoh: Faktorial dengan Stack

int faktorialStack(int n) {
    stack<int> s;
    // Push semua nilai (simulasi rekursi turun)
    while (n > 1) {
        s.push(n);
        n--;
    }
    // Pop dan kalikan (simulasi rekursi naik)
    int result = 1;
    while (!s.empty()) {
        result *= s.top();
        s.pop();
    }
    return result;
}
                

📝 Ringkasan

*dengan TCO

🧠 Quiz 1

🧠 Quiz 2

🧠 Quiz 3

🎖️ Aplikasi Pertahanan

❓ Pertanyaan?

Silakan bertanya atau diskusi

Referensi: Cormen Ch.4 | Weiss Ch.1.3 | Hubbard Ch.4

Terima Kasih! 🙏

Struktur Data dan Algoritma

Pertemuan 07: Rekursi Lanjut dan Divide-and-Conquer

© 2026 - CC BY 4.0