Strategi Lanjutan: Loop, Greedy, dan Rekursi

Memecahkan Masalah Secara Efisien

⏱ JP 1: Mengotomatiskan Tugas dengan Loop

🎯 Analogi: Menyapu Lantai Kelas

Bayangkan kamu diminta menyapu seluruh lantai kelas. Kamu tidak akan membuat instruksi terpisah untuk setiap ubin, seperti "Sapu ubin 1, sapu ubin 2, sapu ubin 3...". Kamu hanya punya satu set instruksi: "Ayunkan sapu", dan kamu **mengulanginya** terus-menerus sampai seluruh lantai bersih. Itulah inti dari **Loop**.

Konsep Teknis: Kerja Berulang

Pada pelajaran sebelumnya, kita menyimpulkan bahwa `if-else` tidak efisien untuk 1000 data karena kita harus melakukan **kerja berulang**. Dalam pemrograman, solusi untuk kerja berulang adalah **Loop (Perulangan)**.

Loop adalah instruksi untuk menjalankan blok kode yang sama berulang kali sampai sebuah kondisi terpenuhi. `for loop` adalah salah satu jenis loop yang paling umum.

💻 Aktivitas: Membedah Kode Pengurutan

Perhatikan kembali kode Strategi 2 dari pelajaran sebelumnya. Bagian `for ... in ...:` adalah sebuah loop!


# data_urut adalah list berisi: [('Citra', 95), ('Ali', 85), ('Budi', 70)]

# Loop dimulai di sini
for i, (nama, nilai) in enumerate(data_urut, start=1):
    # Blok kode ini akan diulang untuk setiap item di data_urut
    print(f"{i}. {nama} ({nilai})")

Tugas: Diskusikan dengan temanmu, apa yang akan terjadi jika `start=1` dihapus dari `enumerate`?

⏱ JP 2: Strategi Cerdas dengan Algoritma Greedy

🎯 Analogi: Memilih Jajanan di Kantin

Uangmu tinggal Rp 5.000, dan kamu sangat lapar. Di kantin ada banyak jajanan. Tanpa pikir panjang, kamu akan langsung memilih jajanan yang paling besar dan paling mengenyangkan dengan uangmu itu, misalnya bakwan atau lontong. Kamu membuat pilihan terbaik **saat ini** untuk mengatasi laparmu. Inilah pendekatan **Greedy**.

Konsep Teknis: Selalu Ambil yang Terbaik

Algoritma Greedy (rakus) adalah strategi pemecahan masalah dengan cara membuat pilihan terbaik (paling optimal) yang bisa diambil pada setiap langkah, tanpa memikirkan konsekuensi di masa depan.

💰 Skenario: Masalah Kembalian Uang

Seorang kasir harus memberikan kembalian sebesar Rp 48.000 dengan jumlah lembar uang paling sedikit. Pecahan yang tersedia: Rp 20.000, Rp 10.000, Rp 5.000, Rp 2.000, dan Rp 1.000. Pendekatan Greedy: "Pada setiap langkah, ambil pecahan uang terbesar yang nilainya tidak melebihi sisa kembalian."

💻 Aktivitas: Telusuri Kode Greedy

Salin kode ini ke Google Colab. Sebelum dijalankan, coba telusuri (trace) alur kerjanya di buku catatan untuk menebak hasilnya.


def kembalian_greedy(total_kembalian, pecahan):
    hasil = []
    pecahan.sort(reverse=True)
    
    for p in pecahan:
        while total_kembalian >= p:
            hasil.append(p)
            total_kembalian = total_kembalian - p
            
    return hasil

kembalian = 48000
pecahan_tersedia = [1000, 5000, 20000, 10000, 2000]

print(f"Kembalian untuk Rp {kembalian}:")
print(kembalian_greedy(kembalian, pecahan_tersedia))

⏱ JP 3: Memecah Masalah dengan Rekursi

🎯 Analogi: Boneka Matryoshka (Boneka Rusia)

Boneka Matryoshka

Bayangkan kamu membuka sebuah boneka Matryoshka. Di dalamnya, ada boneka lain yang lebih kecil, yang bentuknya persis sama. Kamu buka lagi, ada lagi yang lebih kecil. Kamu terus melakukan **tugas yang sama (membuka boneka)** pada **versi yang lebih kecil**, sampai kamu menemukan boneka terkecil yang tidak bisa dibuka lagi. Itulah cara kerja **Rekursi**.

Konsep Teknis: Fungsi Memanggil Dirinya Sendiri

Rekursi adalah teknik di mana sebuah fungsi menyelesaikan masalah dengan cara memanggil dirinya sendiri, tetapi dengan input yang lebih kecil/sederhana, hingga mencapai sebuah **kasus dasar (base case)** yang bisa langsung diselesaikan.

Skenario 1: Faktorial

Menghitung `5!` (5 × 4 × 3 × 2 × 1).

a. Perhitungan Manual

5! = 5 * 4 * 3 * 2 * 1 = 120

b. Simulasi Panggilan Rekursif (Interaktif)

Masukkan angka dan lihat bagaimana fungsi memecah masalah hingga ke `base case`, lalu menggabungkan hasilnya kembali.

Klik "Visualisasikan!" untuk melihat alur...

c. Kode Program


def faktorial(n):
    # Base Case: Jika n adalah 1, berhenti.
    if n == 1:
        return 1
    # Recursive Step: Panggil diri sendiri dengan n-1.
    else:
        return n * faktorial(n - 1)

print(f"Hasil dari 5! adalah: {faktorial(5)}")

Skenario 2: Deret Fibonacci

Mencari angka ke-5 dalam deret Fibonacci (1, 1, 2, 3, **5**, 8, ...). Aturan: `F(n) = F(n-1) + F(n-2)`.

a. Perhitungan Manual

F(5) = F(4) + F(3)
     = (F(3) + F(2)) + (F(2) + F(1))
     = ((F(2) + F(1)) + 1) + (1 + 1)
     = ((1 + 1) + 1) + 2
     = (2 + 1) + 2
     = 3 + 2 = 5

b. Simulasi Panggilan Rekursif

Setiap panggilan akan bercabang menjadi dua panggilan baru, membentuk struktur seperti pohon.

fib(5)
├── fib(4)
│ ├── fib(3)
│ │ ├── fib(2) -> 1
│ │ └── fib(1) -> 1
│ └── fib(2) -> 1
└── fib(3)
├── fib(2) -> 1
└── fib(1) -> 1

c. Kode Program


def fibonacci(n):
    # Base case: untuk n=1 atau n=2, hasilnya 1.
    if n <= 2:
        return 1
    # Recursive step: Panggil diri sendiri 2 kali.
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

# Mencari angka ke-5 dalam deret Fibonacci
print(f"Angka Fibonacci ke-5 adalah: {fibonacci(5)}")

🤔 Refleksi Akhir

Diskusikan dan jawab pertanyaan-pertanyaan ini di buku catatanmu untuk menyimpulkan pembelajaran kita.

1. Kapan Menggunakannya?

Menurutmu, untuk masalah apa kita sebaiknya menggunakan **Loop**? Dan untuk masalah seperti apa **Rekursi** lebih cocok?

2. Strategi Pilihan

Dari ketiga konsep (Loop, Greedy, Rekursi), strategi mana yang menurutmu paling kuat dan sering terpakai untuk menyelesaikan masalah sehari-hari? Berikan alasanmu.

3. Tantangan Terbesar

Konsep mana yang paling menantang untuk kamu pahami? Apa yang membuatnya sulit?