STRATEGI ALGORITMIK DAN PEMROGRAMAN
Pertemuan 1 • Rekursi: dari konsep menjadi algoritma
Kita sudah mengenal rekursi.
Sekarang kita belajar CARA MEMBUAT solusi rekursif.
Alur hari ini:
Pahami masalah → Temukan pola → Tentukan Base Case → Tentukan Recursive Case → Tulis Pseudocode
1. Rekursi Itu Bukan Sekadar Mengulang
Rekursi digunakan ketika sebuah masalah dapat dijelaskan menggunakan versi yang lebih kecil dari masalah yang sama.
Contoh:
5! membutuhkan 4!
4! membutuhkan 3!
3! membutuhkan 2!
Jadi, masalah besar → masalah yang lebih kecil → masalah yang lebih kecil lagi.
2. Contoh Lengkap: Faktorial 5!
Faktorial berarti perkalian bilangan dari n sampai 1.
5! = 5 × 4 × 3 × 2 × 1
Kita ubah menjadi pola:
5! = 5 × 4!
4! = 4 × 3!
3! = 3 × 2!
2! = 2 × 1!
1! = 1
Perhatikan: setiap langkah mengubah n menjadi n − 1.
3. Menemukan Rumus Rekursif
Dari pola tadi kita dapatkan:
n! = n × (n − 1)!
Artinya:
Untuk menghitung n!, kita cukup menghitung (n − 1)! terlebih dahulu, lalu mengalikannya dengan n.
Contoh:
5! = 5 × 4!
Jika 4! = 24, maka 5! = 5 × 24 = 120.
4. Mengapa Harus Ada Base Case?
Kalau kita terus menjalankan n! = n × (n−1)!, prosesnya akan terus turun.
5! → 4! → 3! → 2! → 1! → 0! → ...
Maka kita perlu menentukan kondisi berhenti.
BASE CASE = kondisi yang membuat rekursi berhenti.
Untuk contoh kita:
1! = 1 ← BASE CASE
5. Recursive Case
RECURSIVE CASE = aturan yang membuat masalah dipanggil kembali dalam ukuran yang lebih kecil.
Pada faktorial:
n! = n × (n − 1)!
Bagian rekursifnya adalah:
(n − 1)!
Jadi kita punya dua komponen:
BASE CASE → 1! = 1
RECURSIVE CASE → n! = n × (n−1)!
6. Cara Menyelesaikan 5! dengan Rekursi
Langkah 1 → 5! = 5 × 4!
Langkah 2 → 4! = 4 × 3!
Langkah 3 → 3! = 3 × 2!
Langkah 4 → 2! = 2 × 1!
Langkah 5 → 1! = 1 ← berhenti
Sekarang hitung kembali dari bawah:
1! = 1
2! = 2 × 1 = 2
3! = 3 × 2 = 6
4! = 4 × 6 = 24
5! = 5 × 24 = 120
7. Dari Ide ke Pseudocode
Tujuan pseudocode: menuliskan logika sebelum menggunakan bahasa pemrograman.
FAKTORIAL(n)
JIKA n = 1
KEMBALIKAN 1
JIKA TIDAK
KEMBALIKAN n × FAKTORIAL(n − 1)
Perhatikan:
• JIKA n = 1 → Base Case
• FAKTORIAL(n − 1) → Recursive Case
8. Cara Membaca Pseudocode
Misalnya FAKTORIAL(4):
1. n = 4, bukan 1 → gunakan recursive case
2. 4 × FAKTORIAL(3)
3. FAKTORIAL(3) → 3 × FAKTORIAL(2)
4. FAKTORIAL(2) → 2 × FAKTORIAL(1)
5. FAKTORIAL(1) → 1 → berhenti
Kemudian hasil dikembalikan:
2 × 1 = 2 → 3 × 2 = 6 → 4 × 6 = 24
9. Coba Bersama: Masalah Tangga
Misalkan ada tangga.
f(1) = 1 cara
f(2) = 2 cara
Untuk 3 anak tangga:
f(3) = f(2) + f(1)
= 2 + 1
= 3 cara
Pertanyaan:
Mengapa f(3) membutuhkan hasil dari masalah yang lebih kecil?
10. Latihan Individu
KERJAKAN 5–7 MENIT
A. Lengkapi:
5! = 5 × ____
4! = 4 × ____
3! = 3 × ____
B. Tentukan:
1. Base Case faktorial = __________
2. Recursive Case faktorial = __________
C. Hitung 4! dengan menuliskan semua langkah rekursinya.
11. Tantangan: Buat Algoritma
Masalah:
Diberikan dua bilangan A dan B. Tentukan bilangan terbesar.
Tuliskan:
1. INPUT = ?
2. PROSES = ?
3. OUTPUT = ?
4. Langkah algoritma = ?
Belum perlu coding. Fokus pada CARA BERPIKIR.
12. Baru Setelah Itu: C++
Setelah algoritma jelas, barulah kita implementasikan.
int faktorial(int n) {
if (n == 1)
return 1;
return n * faktorial(n - 1);
}
Cara membacanya:
if (n == 1) → Base Case
faktorial(n - 1) → Recursive Case
13. Tracing Kode C++
Jika dipanggil:
faktorial(4)
Komputer mengikuti:
4 × faktorial(3)
→ 4 × 3 × faktorial(2)
→ 4 × 3 × 2 × faktorial(1)
→ 4 × 3 × 2 × 1
→ 24
Jadi komputer tidak “menebak” jawaban. Ia mengikuti aturan yang kita rancang.
14. Kesalahan yang Sering Terjadi
❌ Tidak memiliki Base Case
→ rekursi tidak berhenti.
❌ Recursive Case tidak membuat masalah lebih kecil
→ proses bisa tidak pernah selesai.
❌ Langsung coding tanpa memahami masalah
→ sulit menemukan kesalahan logika.
✔️ Urutan yang benar:
MASALAH → POLA → ALGORITMA → PSEUDOCODE → CODING → TESTING
15. Kesimpulan Pertemuan
Hari ini kita belajar cara membangun solusi rekursif:
1. Temukan pola masalah yang lebih kecil.
2. Tentukan Base Case sebagai kondisi berhenti.
3. Tentukan Recursive Case.
4. Tulis pseudocode.
5. Setelah logika benar, baru diterjemahkan ke C++.
Pertemuan berikutnya: kita akan melakukan TRACING rekursi dan latihan C++.
TUGAS INDIVIDU
Dikerjakan individu
1. Hitung 5! dengan metode rekursi. Tulis sampai Base Case, lalu hitung kembali dari bawah.
2. Tuliskan Base Case dan Recursive Case dari faktorial.
3. Buat satu contoh masalah sehari-hari yang memiliki pola “masalah besar → masalah lebih kecil”. Jelaskan polanya.
4. Tantangan: Tuliskan pseudocode sederhana untuk menghitung faktorial n.