LKPD Informatika Kelas 11: Menganalisis Alternatif Solusi Persoalan Relasi Rekurensi dengan 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 pengantar kasus persoalan relasi rekurensi dengan cermat bersama kelompok atau secara mandiri.
• Fokuslah pada keterampilan menganalisis persoalan dan menemukan berbagai alternatif perumusan relasi rekursif yang valid.
• Gunakan ruang jawaban yang tersedia sesuai format yang diinstruksikan pada setiap kegiatan.
• Diskusikan hasil analisis bersama rekan kelompok secara aktif, santun, dan saling menghargai gagasan komputasional.

KEGIATAN

Kegiatan 1: Eksplorasi Dekomposisi Kasus Menara Tangga (Climbing Stairs)

Estimasi: 35 menit

Alat & Bahan:

• Buku catatan / LKPD cetak
• Alat tulis
• Sticky notes (opsional untuk simulasi langkah)

Petunjuk Pengerjaan:

1. Cermati persoalan: Seseorang menaiki tangga setinggi N anak tangga. Dari setiap posisi, ia dapat melangkah 1 anak tangga atau langsung 2 anak tangga sekaligus.
2. Analisis kasus kecil untuk N = 1, 2, 3, dan 4 secara manual untuk memetakan seluruh pola variasi urutan langkah.
3. Identifikasi bagaimana persoalan ukuran N dipecah menjadi subpersoalan serupa berukuran lebih kecil (relasi rekurensi).
4. Jawab pertanyaan analisis pada lembar kerja secara mandiri.

Pertanyaan:

1. Tuliskan seluruh kemungkinan kombinasi langkah untuk mencapai anak tangga ke-1, ke-2, ke-3, dan ke-4!

2. Berdasarkan pengamatan kombinasi langkah di atas, analisislah dekomposisi rekursif persoalan: bagaimana nilai cara melangkah ke anak tangga N dinyatakan berdasarkan nilai cara melangkah ke anak-anak tangga sebelumnya? Tentukan base case (basis) dan recurrence relation (relasi rekursifnya)!

Tabel 2 kolom (Nilai N | Daftar Urutan Kombinasi Langkah & Jumlah Total Cara) dilanjutkan uraian penjelasan pemecahan dekomposisi rekursif beserta perumusan matematis basis dan relasi rekursinya.

Kegiatan 2: Analisis Alternatif Solusi Rekursi: Top-Down vs Bottom-Up State

Estimasi: 50 menit

Alat & Bahan:

• Kertas plano / LKPD cetak
• Spidol warna untuk diagram alur rekursi

Petunjuk Pengerjaan:

1. Bentuk kelompok beranggotakan 3-4 murid.
2. Telaah persoalan yang sama (Menaiki N Tangga), namun kali ini analisislah bagaimana strategi algoritmik rekursi dapat dirancang dengan lebih dari satu sudut pandang (alternatif solusi): Alternatif A (Top-Down: menghitung mundur sisa tangga dari N menuju 0) dan Alternatif B (Bottom-Up Recursive/Forward State: rekursi maju mengakumulasi posisi saat ini dari 0 menuju target N).
3. Bandingkan struktur parameter fungsi rekursif, kondisi basis terminasi, serta pemanggilan rekursif pada kedua alternatif solusi tersebut.

Pertanyaan:

1. Analisislah Alternatif Solusi A (Top-Down): Jika fungsi didefinisikan hitungCaraSisa(sisaTangga), bagaimana perumusan kondisi basis (saat sisaTangga == 0 dan sisaTangga < 0) serta pemanggilan rekursifnya?

2. Analisislah Alternatif Solusi B (Forward State Accumulation): Jika fungsi didefinisikan hitungCaraMaju(posisiSaatIni, targetN), bagaimana perumusan basis terminasi dan pemanggilan rekursifnya?

3. Lakukan perbandingan analitis antara Alternatif Solusi A dan Alternatif Solusi B dalam tabel komparasi meliputi: parameter masukan, mekanisme pengurangan/penambahan masalah, dan kesamaan hasil akhirnya!

Format isian uraian untuk penurunan relasi Alternatif A dan B, diikuti tabel komparasi 4 kolom: Aspek Analisis | Alternatif A (Top-Down) | Alternatif B (Forward State) | Kesimpulan Kesetaraan.

Kegiatan 3: Analisis Solusi Alternatif pada Persoalan dengan Aturan Khusus

Estimasi: 50 menit

Alat & Bahan:

• LKPD cetak
• Penggaris dan pena warna

Petunjuk Pengerjaan:

1. Perhatikan variasi persoalan: Tangga memiliki N anak tangga, tetapi anak tangga ke-3 LICIN/RUSAK sehingga TIDAK BOLEH dipijak sama sekali.
2. Analisislah bagaimana rekursi dapat menghasilkan alternatif pendekatan dalam memodelkan larangan ini: Alternatif 1 (Menangani tangga rusak sebagai base case rekursi bernilai 0 cara) vs Alternatif 2 (Memodifikasi percabangan rekursif sebelum pemanggilan fungsi dilakukan).
3. Simulasikan pohon pemanggilan rekursi untuk N = 4 dengan tangga ke-3 rusak.
4. Selesaikan kegiatan ini termasuk sesi perumusan kesimpulan, transisi, dan refleksi pembelajaran.

Pertanyaan:

1. Analisislah Alternatif 1: Bagaimana struktur relasi rekursi jika anak tangga rusak (misal tangga k = 3) dimasukkan sebagai kondisi basis pencegah?

2. Analisislah Alternatif 2: Bagaimana struktur relasi rekursi jika pemanggilan fungsi rekursif dicegah sebelum cabang dipanggil (filtering cabang)?

3. Dari hasil pohon penelusuran untuk N = 4 (tangga 3 rusak), berapakah total alternatif cara yang valid dan urutan langkah apa saja yang sah?

Diagram/pohon pemanggilan rekursi sederhana N=4, lembar analisis perbandingan Alternatif 1 & 2, serta kotak isian jalur valid dan total cara.

REFLEKSI

1. Bagaimana pemahaman konsep dekomposisi rekursi membantumu melihat bahwa satu masalah komputasi ternyata dapat dimodelkan dengan lebih dari satu alternatif rancangan relasi rekurensi?

2. Ketika menghadapi persoalan rekursif yang memiliki kendala atau pembatasan (seperti kondisi anak tangga rusak), alternatif penanganan mana yang menurutmu paling intuitif dan mengapa?

3. Langkah strategi belajar apa yang akan kamu gunakan ke depan saat menganalisis relasi matematis rekursif yang lebih rumit?