Progres sesi
0 / 5
Sheet 12 · Materi Detail

Menara Hanoi

Rekursif lanjutan — rekursi bercabang pada Fibonacci, teka-teki Menara Hanoi, dan pencarian biner; kapan memilih rekursif atau iteratif; lalu finishing dan presentasi proyek akhir.

Durasi: 120 menit Prasyarat: Pertemuan 11 (rekursif dasar) Tools: simulator Hanoi, penghitung Fibonacci, visualisasi pencarian biner
1

Fibonacci: Rekursi yang Bercabang

Deret Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, … — tiap angka adalah jumlah dua angka sebelumnya. Definisinya rekursif dan langsung bisa ditulis jadi kode: fib(n) = fib(n − 1) + fib(n − 2), dengan base case fib(0) = 0 dan fib(1) = 1.

Bedanya dengan faktorial: di sini satu panggilan memicu dua panggilan. Hasilnya bukan antrean lurus, tapi pohon yang bercabang — dan banyak cabangnya menghitung hal yang sama berulang-ulang. Lihat berapa kali fib(2) muncul di pohon fib(5):

Penghitung panggilan Fibonacci
#include <stdio.h>

long long panggilan = 0;   /* variabel global: bisa diakses semua fungsi */

long long fibRekursif(int n) {
    panggilan++;
    if (n <= 1) return n;
    return fibRekursif(n - 1) + fibRekursif(n - 2);
}

long long fibIteratif(int n) {
    long long a = 0, b = 1, c;
    int i;
    if (n == 0) return 0;
    for (i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

int main(void) {
    int n = 25;
    printf("fibRekursif(%d) = %lld\n", n, fibRekursif(n));
    printf("jumlah panggilan  = %lld\n", panggilan);
    printf("fibIteratif(%d) = %lld\n", n, fibIteratif(n));
    return 0;
}
fibRekursif(25) = 75025
jumlah panggilan  = 242785
fibIteratif(25) = 75025
Hampir seperempat juta panggilan untuk n = 25, sementara versi iteratif cukup 24 putaran. Tiap n naik 1, jumlah panggilan naik sekitar 1,6 kali lipat (pertumbuhan eksponensial). Rekursif itu elegan, tapi kalau subsoalnya tumpang-tindih, versi naifnya bisa sangat boros. Solusinya (di kelas lanjutan): simpan hasil yang sudah dihitung — teknik memoization.
2

Menara Hanoi: Masalah yang Paling Enak Diselesaikan Rekursif

Ada tiga tiang (A, B, C) dan n cakram berbeda ukuran yang tersusun di tiang A, terbesar di bawah. Tugasnya: pindahkan semua ke tiang C, dengan aturan (1) hanya satu cakram dipindah setiap langkah, (2) hanya cakram teratas yang boleh diambil, (3) cakram besar tidak boleh di atas cakram kecil.

Mencari langkahnya secara iteratif itu bikin pusing. Tapi dengan cara pikir rekursif, jawabannya cuma tiga kalimat. Untuk memindahkan n cakram dari A ke C:

  1. Pindahkan n − 1 cakram teratas dari A ke B (pakai C sebagai bantuan) — percayakan pada rekursi.
  2. Pindahkan cakram terbesar dari A ke C.
  3. Pindahkan n − 1 cakram dari B ke C (pakai A sebagai bantuan) — rekursi lagi.

Base case: 0 cakram → tidak perlu melakukan apa-apa.

#include <stdio.h>

void hanoi(int n, char asal, char bantu, char tujuan) {
    if (n == 0) return;
    hanoi(n - 1, asal, tujuan, bantu);
    printf("Pindahkan cakram %d dari %c ke %c\n", n, asal, tujuan);
    hanoi(n - 1, bantu, asal, tujuan);
}

int main(void) {
    hanoi(3, 'A', 'B', 'C');
    return 0;
}
Pindahkan cakram 1 dari A ke C
Pindahkan cakram 2 dari A ke B
Pindahkan cakram 1 dari C ke B
Pindahkan cakram 3 dari A ke C
Pindahkan cakram 1 dari B ke A
Pindahkan cakram 2 dari B ke C
Pindahkan cakram 1 dari A ke C

Coba langsung: simulator Menara Hanoi

Simulator Hanoi
Jumlah langkah minimum = 2ⁿ − 1

Menurut legenda, para biarawan memindahkan 64 cakram emas; dunia kiamat saat mereka selesai. Dengan satu langkah per detik, 2⁶⁴ − 1 langkah butuh sekitar 585 miliar tahun. Aman.

3

Pencarian Biner Rekursif

Mencari kata di kamus, kamu nggak membaca dari halaman pertama. Kamu buka tengah, lihat apakah kata yang dicari ada sebelum atau sesudahnya, lalu ulangi di separuh yang benar. Itulah pencarian biner — syaratnya data harus sudah terurut.

Strukturnya rekursif: cari di tengah; kalau bukan, cari lagi (rekursif) di separuh kiri atau kanan. Base case ada dua: ketemu, atau rentangnya kosong (kiri > kanan). Untuk 1.000.000 data, pencarian linear bisa butuh 1.000.000 langkah; pencarian biner paling banyak sekitar 20.

#include <stdio.h>

int cariBiner(int a[], int kiri, int kanan, int x) {
    int tengah;
    if (kiri > kanan) return -1;              /* base case: tidak ada */
    tengah = (kiri + kanan) / 2;
    if (a[tengah] == x) return tengah;        /* base case: ketemu */
    if (x < a[tengah])
        return cariBiner(a, kiri, tengah - 1, x);
    return cariBiner(a, tengah + 1, kanan, x);
}

int main(void) {
    int a[] = {3, 8, 12, 17, 23, 31, 42, 56, 64, 77};
    int n = 10;
    printf("Cari 42 -> indeks %d\n", cariBiner(a, 0, n - 1, 42));
    printf("Cari 5  -> indeks %d\n", cariBiner(a, 0, n - 1, 5));
    return 0;
}
Cari 42 -> indeks 6
Cari 5  -> indeks -1
4

Rekursif atau Iteratif?

Semua yang bisa ditulis rekursif bisa juga ditulis iteratif (dan sebaliknya). Pertanyaannya: mana yang lebih cocok?

RekursifIteratif (loop)
Kejelasan kodeSangat jelas untuk masalah bercabang/bersarang (Hanoi, pohon, struktur folder)Lebih jelas untuk proses lurus (menjumlah, mencari di array)
MemoriSetiap panggilan butuh frame; terlalu dalam → stack overflowHemat, cukup beberapa variabel
KecepatanAda biaya tiap pemanggilan; bisa sangat boros kalau subsoal berulang (fib naif)Umumnya lebih cepat
Contoh cocokHanoi, pencarian biner, menjelajah pohon/graf, algoritma bagi-dan-taklukkanFaktorial, fibonacci, jumlah deret, traversal array
Pegangan praktis: kalau masalahnya secara alami "terdiri dari versi kecil dirinya sendiri" dan kedalamannya tidak terlalu besar, rekursif membuat kode lebih mudah dipahami. Kalau prosesnya lurus satu arah, loop biasanya pilihan yang lebih aman dan cepat.
5

Proyek Akhir Tahap 3 & Presentasi

Tahap 3 — lengkapi Mini Toolkit Angka:
  1. Menu Fibonacci: tampilkan fib(n) versi rekursif dan iteratif beserta jumlah panggilan rekursifnya. Batasi n ≤ 40.
  2. Menu cek palindrom: baca satu kata, cek dengan fungsi rekursif int palindrom(char s[], int kiri, int kanan).
  3. Menu pencarian biner: baca k angka terurut ke array, baca angka yang dicari, panggil cariBiner rekursif.
  4. Uji semua menu, termasuk input aneh (negatif, 0, menu tidak ada).
#include <stdio.h>
#include <string.h>

int palindrom(char s[], int kiri, int kanan) {
    if (kiri >= kanan) return 1;                 /* base case: sudah bertemu di tengah */
    if (s[kiri] != s[kanan]) return 0;           /* base case: ketemu yang beda */
    return palindrom(s, kiri + 1, kanan - 1);    /* periksa bagian dalam */
}

int main(void) {
    char kata1[] = "katak";
    char kata2[] = "kasur";
    printf("%s: %d\n", kata1, palindrom(kata1, 0, (int)strlen(kata1) - 1));
    printf("%s: %d\n", kata2, palindrom(kata2, 0, (int)strlen(kata2) - 1));
    return 0;
}
katak: 1
kasur: 0

Panduan presentasi (5–7 menit per orang)

1 · Demo

Jalankan program

Tunjukkan semua menu dengan input normal dan satu input aneh.

2 · Kode

Satu fungsi favorit

Jelaskan satu fungsi rekursif: base case-nya apa, bagaimana masalah diperkecil.

3 · Trace

Telusuri di papan

Gambar call stack untuk satu contoh kecil, mis. faktorial(3).

4 · Refleksi

Bug tersulit

Ceritakan satu bug yang kamu temui dan cara menemukannya.

Kriteria penilaian proyekBobot
Program berjalan, semua menu benar (termasuk validasi input)35%
Struktur: main hanya menu, logika dalam fungsi, nama jelas20%
Rekursif: base case dan recursive case tepat25%
Kerapian: indentasi konsisten, komentar seperlunya10%
Presentasi dan kemampuan menelusuri kode sendiri10%
6

Kuis Tantangan Akhir

Delapan soal yang merangkum seluruh kelas, dari pseudocode sampai rekursif.

1. (P1) Pada pseudocode, x ← x + 1 berarti…

← adalah penugasan: sisi kanan dihitung dulu dengan nilai lama, hasilnya disimpan ke kiri. Di C ditulis x = x + 1; atau x++;.

2. (P2, P4) Dengan int n = 13;, berapa nilai (n % 2 == 0) || (n / 2 > 5)?

13 % 2 = 1, jadi kiri salah. 13 / 2 = 6 (pembagian bulat), 6 > 5 benar. Salah ATAU benar = benar → 1.

3. (P5) Nilai 70 dimasukkan ke rantai if (nilai >= 85) … else if (nilai >= 70) … else if (nilai >= 55) …. Berapa cabang yang dijalankan?

Rantai else-if berhenti di kondisi benar pertama. Sisanya dilewati walaupun juga benar.

4. (P6) Berapa kali badan for (i = 1; i < 10; i += 3) dijalankan?

i = 1, 4, 7 → tiga kali. Berikutnya i = 10, dan 10 < 10 salah.

5. (P8) int a[4] = {5, 2, 8, 1}; — ekspresi mana yang menghasilkan elemen terakhir?

Indeks 0..n−1. a[4] di luar batas; C juga tidak mengenal indeks negatif seperti Python.

6. (P9) Berapa byte yang dibutuhkan untuk menyimpan string "C!"?

'C', '!', dan terminator '\0' — tiga char, masing-masing 1 byte.

7. (P10) void f(int x) { x = 100; } dipanggil sebagai f(a) dengan a = 5. Berapa a setelahnya?

Pass by value: x hanya salinan. Untuk mengubah a, fungsi harus menerima int *x dan dipanggil dengan f(&a).

8. (P11–P12) Berapa langkah minimum untuk menyelesaikan Menara Hanoi dengan 4 cakram?

Langkah(n) = 2 × Langkah(n − 1) + 1, dengan Langkah(0) = 0 → 1, 3, 7, 15. Rumus tertutupnya 2ⁿ − 1 = 2⁴ − 1 = 15.
Skor: 0 / 8 terjawab benar
7

Ringkasan Pertemuan 12 & Penutup Kelas

  • Rekursi bercabang (Fibonacci) membentuk pohon panggilan; versi naifnya menghitung subsoal yang sama berulang-ulang dan tumbuh eksponensial.
  • Menara Hanoi: pindahkan n − 1, pindahkan yang terbesar, pindahkan n − 1 lagi. Butuh 2ⁿ − 1 langkah.
  • Pencarian biner (data terurut) membuang separuh data tiap langkah — base case: ketemu atau rentang kosong.
  • Pilih rekursif untuk masalah yang strukturnya bersarang; pilih loop untuk proses lurus.
Selesai — selamat!

Kamu sudah menempuh perjalanan dari menulis resep di kertas sampai fungsi yang memanggil dirinya sendiri. Langkah berikutnya yang disarankan: pointer lebih dalam, struct, file I/O, dan algoritma pengurutan (bubble, selection, merge sort) — merge sort akan terasa akrab karena rekursif.

made by boflyeta.dev