LKPD Informatika Kelas 11: Menganalisis Formulasi Kondisi Basis dan Langkah Rekursif pada Strategi Algoritmik Rekursi

INFORMASI UMUM

TUJUAN PEMBELAJARAN

1. Menganalisis persoalan yang bisa menghasilkan lebih dari satu solusi dengan pemahamannya terhadap strategi algoritmik rekursi untuk menghasilkan beberapa alternatif solusi

PETUNJUK UMUM

• Bacalah setiap narasi persoalan komputasi dengan saksama bersama kelompok atau secara mandiri.
• Fokuskan penalaran pada identifikasi kondisi basis (base case) dan formulasi langkah rekursif (recursive step) yang memungkinkan terbentuknya lebih dari satu jalur pemecahan persoalan.
• Tuliskan hasil analisis secara runtut pada format ruang jawaban yang telah disediakan.
• Gunakan waktu secara efektif sesuai estimasi yang tertera pada setiap kegiatan.

KEGIATAN

Kegiatan 1: Aktivitas 1: Menganalisis Titik Cabang Rekursi pada Persoalan Menghitung Kombinasi Langkah Tangga

Estimasi: 40 menit

Alat & Bahan:

• Buku tulis/kertas kerja berpetak
• Alat tulis/pensil warna untuk menggambar diagram pohon rekursi

Petunjuk Pengerjaan:

1. Cermati skenario persoalan: Seseorang menaiki tangga dengan N anak tangga. Dari setiap posisi, ia dapat melangkah 1 anak tangga atau langsung 2 anak tangga sekaligus. Kita ingin mengetahui seluruh alternatif cara untuk mencapai anak tangga ke-N.
2. Analisis dekomposisi masalah tersebut ke dalam subpersoalan yang lebih kecil.
3. Rumuskan kondisi basis dan langkah rekursifnya, lalu telaah bagaimana pemecahan rekursif ini menghasilkan lebih dari satu alternatif solusi urutan langkah.

Pertanyaan:

1. Berdasarkan skenario menaiki N anak tangga (langkah 1 atau 2), tentukan kondisi basis (base case) dan langkah rekursif (recursive step) dalam bentuk relasi rekurensi untuk fungsi Cara(N). Berikan analisis mengapa kondisi basis tersebut mutlak diperlukan!

2. Lakukan penelusuran (tracing) untuk N = 4. Tuliskan seluruh alternatif solusi urutan langkah yang dihasilkan melalui dekomposisi rekursif tersebut!

Tuliskan jawaban pada lembar kerja: (1) Formulasi matematis f(N) beserta syarat batasnya disertai penjelasan peran basis; (2) Daftar lengkap variasi urutan langkah untuk N = 4 berdasarkan penelusuran cabang rekursi.

Kegiatan 2: Aktivitas 2: Analisis Perbandingan Formulasi Rekursif untuk Persoalan Penukaran Koin (Coin Change)

Estimasi: 45 menit

Alat & Bahan:

• Lembar kerja tabel perbandingan
• Pulpen

Petunjuk Pengerjaan:

1. Perhatikan persoalan: Diberikan target nominal uang Rp4.000 dan tersedia koin dengan pecahan [Rp1.000, Rp2.000]. Terdapat beberapa kombinasi koin yang dapat membentuk nominal tersebut.
2. Analisis persoalan ini menggunakan pendekatan strategi rekursi untuk menemukan alternatif-alternatif kombinasi yang valid.
3. Bandingkan dua formulasi rekursif: Alternatif A (pohon keputusan berbasis pengurangan nominal koin per langkah) vs Alternatif B (pohon keputusan berbasis pilihan: sertakan koin pecahan ke-i atau lewati ke pecahan berikutnya).
4. Isi tabel analisis komparasi formulasi rekursif.

Pertanyaan:

1. Lengkapi tabel perbandingan analisis dua strategi rekursi untuk persoalan penukaran koin Rp4.000 dengan pecahan [1000, 2000]: tentukan kondisi basis sukses, kondisi basis gagal/terminasi, dan formula relasi rekursif untuk masing-masing alternatif solusi!

2. Berdasarkan analisis kedua formulasi di atas, sebutkan seluruh alternatif solusi susunan koin unik yang berhasil dibentuk untuk nominal Rp4.000!

Isi tabel 4 kolom: [Komponen Analisis | Alternatif A (Kurangi Nominal) | Alternatif B (Keputusan Pilihan Koin) | Keterangan], lalu tuliskan daftar himpunan kombinasi koin unik di bawah tabel.

Kegiatan 3: Aktivitas 3: Menganalisis Variasi Solusi Jalur Lintasan Grid Rekursif dan Refleksi

Estimasi: 50 menit

Alat & Bahan:

• Kertas plano/HVS
• Spidol/pena

Petunjuk Pengerjaan:

1. Sebuah robot berada di titik sudut kiri-atas grid berukuran 3x3 (titik (1,1)) dan harus mencapai sudut kanan-bawah (titik (3,3)). Robot hanya diizinkan bergerak ke Kanan (K) atau ke Bawah (B).
2. Diskusikan dalam kelompok: rumuskan fungsi rekursif CariJalur(x, y) untuk menemukan seluruh lintasan yang memungkinkan.
3. Analisis bagaimana percabangan rekursi di setiap koordinat (bergerak ke (x+1, y) ATAU (x, y+1)) menghasilkan kumpulan alternatif lintasan.
4. Lakukan refleksi individu di akhir kegiatan mengenai prinsip kerja kondisi basis dan percabangan rekursif.

Pertanyaan:

1. Formulasikan kondisi basis dan langkah rekursif untuk robot pada grid 3x3 menuju (3,3). Kapan rekursi berhenti dan kapan rekursi bercabang menghasilkan solusi alternatif?

2. Daftarkan seluruh alternatif string urutan langkah (menggunakan simbol K = Kanan, B = Bawah) yang dihasilkan oleh pohon rekursi untuk perjalanan dari (1,1) ke (3,3)!

Tuliskan hasil diskusi kelompok berupa formulasi aturan rekursi beserta diagram pohon keputusan dan daftar 6 string lintasan. Sediakan kolom refleksi individual di bagian bawah lembar kerja.

REFLEKSI

1. Bagaimana peran perumusan kondisi basis (base case) dalam memastikan bahwa penelusuran rekursi yang bercabang tidak mengalami perulangan tak berhingga (infinite loop)?

2. Ketika sebuah persoalan komputasi dapat diselesaikan dengan lebih dari satu alternatif formulasi rekursi (seperti pada persoalan koin atau lintasan grid), hal apa yang menjadi pertimbanganmu dalam memilih struktur rekursi yang paling mudah dianalisis?

3. Bagian mana dari proses pembuatan pohon rekursi yang paling membantumu memahami terbentuknya banyak alternatif solusi dari satu persoalan awal?