M12 Tingkat: Pengayaan Estimasi: 90 Menit

Pengenalan Rekursi dan Strategi Pemecahan Masalah

Materi dibuka. Kerjakan latihan di bawah untuk menguji penguasaan materi.

Tujuan Pembelajaran Modul

✓ Mengenali kasus dasar dan langkah rekursif.
✓ Menelusuri fungsi rekursif sederhana.
✓ Membedakan complete search dan pruning.
✓ Memahami ide awal greedy dan dynamic programming.

Apa itu rekursi?

Rekursi terjadi ketika sebuah fungsi memanggil dirinya sendiri untuk menyelesaikan versi masalah yang lebih kecil. Fungsi rekursif harus memiliki kasus dasar agar pemanggilan berhenti.

Contoh faktorial

Faktorial n, ditulis n!, adalah n×(n-1)×...×1 untuk n positif, dan 0!=1. Definisi rekursifnya: faktorial(0)=1; faktorial(n)=n×faktorial(n-1) untuk n>0.

Complete search dan pruning

Complete search memeriksa seluruh kandidat yang relevan. Pruning menghentikan eksplorasi suatu kandidat ketika sudah diketahui bahwa kandidat itu tidak mungkin menghasilkan solusi yang valid atau lebih baik. Pruning harus mempertahankan kebenaran hasil.

Sekilas greedy dan dynamic programming

Greedy memilih keputusan lokal berdasarkan aturan tertentu. Keputusan lokal tidak selalu menghasilkan solusi global terbaik, sehingga perlu pembuktian atau alasan yang sesuai. Dynamic programming menyimpan hasil submasalah agar tidak menghitung hal yang sama berulang kali.

Contoh Soal & Pembahasan Terarah

Masalah:

Apa hasil faktorial(4) dengan definisi faktorial(0)=1 dan faktorial(n)=n×faktorial(n-1)?

Solusi & Penalaran:

faktorial(4)=4×faktorial(3)=4×3×faktorial(2)=4×3×2×faktorial(1)=4×3×2×1×faktorial(0)=24.

Implementasi Kode C++:

#include <iostream>
using namespace std;
int faktorial(int n) {
    if (n == 0) return 1;
    return n * faktorial(n - 1);
}
int main() {
    cout << faktorial(4) << '\n';
}

Latihan Pemahaman

Uji Penguasaan Materi (3 Soal)

Kunci jawaban diperiksa di server. Pembahasan lengkap akan muncul setelah Anda mengirimkan jawaban.

Soal #1 • M12Q1

short answer

Dengan definisi Fibonacci F(0)=0, F(1)=1, dan F(n)=F(n-1)+F(n-2), berapa F(5)?

Soal #2 • M12Q2

multiple choice

Mengapa fungsi rekursif membutuhkan kasus dasar?

A. Agar selalu menghasilkan angka genap

B. Agar pemanggilan dapat berhenti

C. Agar tidak memiliki parameter

D. Agar program tidak memakai memori

Verifikasi langsung di backend

Soal #3 • M12Q3

multiple choice

Apa tujuan pruning pada complete search?

A. Memeriksa kandidat yang sama berkali-kali

B. Menghentikan cabang yang tidak mungkin memberi solusi yang relevan

C. Mengacak urutan input

D. Menghapus jawaban benar