---

🧭 1. Pengantar Konsep Rekursi dan DP

6

📖 Definisi

• Rekursi (Recursion) adalah teknik pemrograman di mana sebuah fungsi memanggil dirinya sendiri untuk menyelesaikan masalah.
• Dynamic Programming (DP) adalah teknik optimasi yang menyelesaikan masalah dengan cara menyimpan hasil submasalah agar tidak dihitung ulang.

---

🧠 Narasi Konseptual

Bayangkan kamu ingin menghitung tangga:

• Rekursi → kamu memecah tangga menjadi langkah lebih kecil sampai dasar
• DP → kamu mengingat langkah yang sudah dihitung agar tidak mengulang

---

🔁 2. Rekursi (Recursion)

---

📌 2.1 Konsep Dasar Rekursi

6

📖 Definisi

Rekursi adalah proses di mana fungsi:

• Memanggil dirinya sendiri
• Memiliki base case (kasus dasar) untuk berhenti

---

🧠 Narasi

Rekursi seperti:

• Cermin di depan cermin → pantulan tak berujung
• Tapi ada batas agar tidak infinite loop (base case)

---

⚙️ 2.2 Struktur Rekursi

📌 Komponen Rekursi

Komponen	Penjelasan
Base Case	Kondisi berhenti
Recursive Case	Fungsi memanggil dirinya sendiri

---

💻 Contoh Sederhana

int faktorial(int n){
    if(n == 0) return 1; // base case
    return n * faktorial(n-1);
}

---

📊 2.3 Contoh Rekursi: Faktorial

🧠 Narasi

Faktorial 5:

5! = 5 × 4 × 3 × 2 × 1

---

🔄 2.4 Tree Rekursi (Contoh Fibonacci)

7

📖 Konsep

Fibonacci:

F(n) = F(n-1) + F(n-2)

---

🧠 Narasi

Rekursi Fibonacci:

• Banyak submasalah dihitung ulang
• Tidak efisien untuk n besar

---

⚠️ 2.5 Kelemahan Rekursi

📊 Tabel

Masalah	Penjelasan
Overlapping computation	Perhitungan berulang
Stack overflow	Rekursi terlalu dalam
Lambat	Eksponensial

---

⚡ 3. Dynamic Programming (DP)

---

📌 3.1 Konsep Dynamic Programming

8

📖 Definisi

Dynamic Programming adalah teknik untuk menyelesaikan masalah dengan:

• Memecah masalah menjadi submasalah
• Menyimpan hasil (memoization/tabulation)
• Menghindari perhitungan ulang

---

🧠 Narasi

DP seperti:

• Menulis hasil di buku catatan
• Tidak menghitung ulang masalah yang sama

---

🔑 3.2 Prinsip DP

📌 Dua Prinsip Utama

Prinsip	Penjelasan
Overlapping Subproblem	Submasalah berulang
Optimal Substructure	Solusi optimal dari subsolusi

---

🧮 3.3 Metode DP

---

🔹 A. Memoization (Top-Down)

7

📖 Konsep

• Rekursi + penyimpanan hasil
• Menghindari perhitungan ulang

---

🔹 B. Tabulation (Bottom-Up)

6

📖 Konsep

• Mengisi tabel dari bawah ke atas
• Tidak menggunakan rekursi

---

📊 3.4 Perbandingan Rekursi vs DP

📊 Tabel

Aspek	Rekursi	Dynamic Programming
Efisiensi	Rendah	Tinggi
Perhitungan ulang	Ya	Tidak
Memori	Call stack	Array/table
Kecepatan	Lambat	Cepat

---

⚡ 3.5 Contoh DP: Fibonacci

🔁 Rekursi (Tidak Efisien)

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

---

⚡ DP (Efisien)

int fib(int n){
    int dp[n+1];
    dp[0] = 0;
    dp[1] = 1;    for(int i=2; i<=n; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

---

🧠 3.6 Narasi Perbandingan

• Rekursi → seperti menghitung ulang dari awal setiap kali
• DP → seperti menyimpan hasil agar tidak menghitung ulang

---

📈 4. Analisis Kompleksitas

📊 Tabel

Metode	Fibonacci Complexity
Rekursi	O(2ⁿ)
DP	O(n)

---

🧪 5. Studi Kasus Dunia Nyata

📌 Contoh Penggunaan DP

Bidang	Contoh
AI	Path optimization
Game	Shortest path (AI movement)
Finance	Knapsack problem
Text processing	Edit distance

---

🎮 6. Contoh Masalah DP: Knapsack

6

📖 Konsep

Memilih barang dengan:

• Berat terbatas
• Nilai maksimal

---

📚 7. Ringkasan Materi

• Rekursi = fungsi memanggil dirinya sendiri
• DP = optimasi rekursi dengan menyimpan hasil
• DP memiliki 2 pendekatan: memoization & tabulation
• DP lebih efisien dari rekursi biasa
• Digunakan dalam AI, game, dan optimasi sistem

---

📝 8. Latihan / Diskusi

✏️ Soal Teori

1. Apa itu rekursi?
2. Apa kelemahan rekursi?
3. Jelaskan DP dan manfaatnya

💻 Soal Praktikum

1. Implementasi faktorial rekursif
2. Fibonacci dengan DP
3. Bandingkan waktu eksekusi

---

🎯 Penutup

Rekursi dan Dynamic Programming adalah fondasi penting dalam algoritma lanjutan, karena:

• Digunakan di AI
• Digunakan di optimasi sistem
• Digunakan di competitive programming