Progres sesi
0 / 5
Sheet 11 · Materi Detail

Cermin di Dalam Cermin

Rekursif dasar — fungsi yang memanggil dirinya sendiri untuk menyelesaikan versi masalah yang lebih kecil, sampai bertemu kasus paling sederhana. Kita bongkar cara kerjanya lewat call stack.

Durasi: 120 menit Prasyarat: Pertemuan 10 (fungsi & stack frame) Tools: visualisasi call stack
1

Masalah yang Berisi Dirinya Sendiri

Kamu antre di bioskop dan pengin tahu posisimu, tapi antreannya terlalu panjang untuk dihitung. Caranya: tanya orang di depanmu "kamu nomor berapa?", lalu tambah satu. Orang itu juga nggak tahu, jadi dia tanya orang di depannya… sampai ke orang paling depan yang langsung tahu jawabannya: "aku nomor 1". Jawaban lalu dioper balik ke belakang, tiap orang menambah satu.

Itulah rekursif: menyelesaikan masalah dengan memanggil diri sendiri untuk versi masalah yang lebih kecil. Setiap fungsi rekursif wajib punya dua bagian:

Base case

Kasus dasar — berhenti

Kasus paling kecil yang jawabannya langsung diketahui tanpa memanggil diri sendiri. "Aku orang paling depan, nomorku 1."

Recursive case

Kasus rekursif — memperkecil

Memanggil diri sendiri dengan masalah yang lebih dekat ke base case, lalu mengolah hasilnya. "Nomorku = nomor orang di depanku + 1."

Contoh klasik: faktorial. 5! = 5 × 4 × 3 × 2 × 1. Perhatikan bahwa 5! = 5 × 4!, dan 4! = 4 × 3!, dan seterusnya. Definisinya sudah rekursif:

  • n! = 1, jika n ≤ 1  ← base case
  • n! = n × (n − 1)!, jika n > 1  ← recursive case
long long faktorial(int n) {
    long long hasil = 1;
    int i;
    for (i = 2; i <= n; i++) {
        hasil *= i;
    }
    return hasil;
}
long long faktorial(int n) {
    if (n <= 1) {
        return 1;                      /* base case */
    }
    return n * faktorial(n - 1);       /* recursive case */
}
Versi rekursif hampir sama persis dengan definisi matematikanya. Itulah daya tarik rekursif: untuk masalah yang strukturnya memang "berisi dirinya sendiri", kodenya jadi pendek dan mudah dibaca.
2

Call Stack: Fase Turun dan Fase Naik

Ingat stack frame dari Pertemuan 10? Setiap pemanggilan faktorial mendapat frame sendiri dengan n-nya masing-masing. Ada dua fase:

  • Fase turun: faktorial(4) memanggil faktorial(3), yang memanggil faktorial(2)… Frame terus menumpuk, masing-masing menunggu jawaban dari bawahnya.
  • Fase naik: begitu base case tercapai, jawaban dikembalikan ke frame di bawahnya, yang menyelesaikan perkaliannya lalu mengembalikan hasilnya lagi… sampai kembali ke main.

Jalankan penelusur di bawah. Coba juga fungsi cetak untuk melihat bedanya kode yang dijalankan sebelum dan sesudah panggilan rekursif, dan tanpa base case untuk melihat apa yang terjadi kalau rem-nya lupa dipasang.

3

Resep Merancang Fungsi Rekursif

Jangan mencoba membayangkan seluruh tumpukan panggilan waktu menulis kode rekursif — itu bikin pusing. Cukup jawab tiga pertanyaan, lalu percaya bahwa panggilan untuk masalah yang lebih kecil sudah benar (ini mirip langkah induksi di matematika):

Pertanyaanpangkat(b, e) = bejumlahDigit(n)
1. Kasus terkecil & jawabannya?e = 0 → 1n < 10 (satu digit) → n itu sendiri
2. Bagaimana memperkecil masalah?e − 1buang digit terakhir: n / 10
3. Bagaimana menggabungkan hasilnya?b × pangkat(b, e − 1)n % 10 + jumlahDigit(n / 10)
#include <stdio.h>

long long faktorial(int n) {
    if (n <= 1) return 1;
    return n * faktorial(n - 1);
}

int jumlah(int n) {
    if (n == 0) return 0;
    return n + jumlah(n - 1);
}

long long pangkat(int b, int e) {
    if (e == 0) return 1;
    return b * pangkat(b, e - 1);
}

int jumlahDigit(int n) {
    if (n < 10) return n;
    return n % 10 + jumlahDigit(n / 10);
}

int main(void) {
    printf("5!                = %lld\n", faktorial(5));
    printf("1 + 2 + ... + 10  = %d\n", jumlah(10));
    printf("2 pangkat 10      = %lld\n", pangkat(2, 10));
    printf("jumlahDigit(2026) = %d\n", jumlahDigit(2026));
    return 0;
}
5!                = 120
1 + 2 + ... + 10  = 55
2 pangkat 10      = 1024
jumlahDigit(2026) = 10
Tiga cara rekursif gagal: (1) tidak ada base case → memanggil diri sendiri selamanya sampai memori stack habis (stack overflow, program crash dengan "Segmentation fault"); (2) base case tidak pernah tercapai — misalnya f(n - 2) dengan base case n == 0 tapi n ganjil, jadi n melompati 0 ke negatif; (3) lupa return di recursive case — hasil panggilan dihitung tapi dibuang.
4

Proyek Akhir Tahap 2

Lanjutkan toolkit.c dari Pertemuan 10:

  1. Ganti isi jumlahDigit dengan versi rekursif. Program harus tetap memberi hasil yang sama (472 → 13). Jangan lupa tangani bilangan negatif di luar fungsi rekursifnya.
  2. Tambahkan menu faktorial (rekursif, long long). Tolak input negatif dan input di atas 20 dengan pesan yang jelas — 21! sudah tidak muat di long long.
  3. Tambahkan menu pangkat be (rekursif) untuk e ≥ 0.
  4. Bonus: buat pangkat yang lebih cepat dengan ide be = (be/2)² untuk e genap. Berapa panggilan yang dihemat untuk 230?
long long faktorial(int n) {
    if (n <= 1) return 1;
    return n * faktorial(n - 1);
}

int jumlahDigit(int n) {          /* dipanggil dengan n >= 0 */
    if (n < 10) return n;
    return n % 10 + jumlahDigit(n / 10);
}

/* di dalam switch: */
case 4:
    printf("n = ");
    scanf("%d", &n);
    if (n < 0 || n > 20) {
        printf("n harus 0..20\n");
    } else {
        printf("%d! = %lld\n", n, faktorial(n));
    }
    break;

/* bonus: pangkat cepat, sekitar log2(e) panggilan */
long long pangkatCepat(long long b, int e) {
    long long setengah;
    if (e == 0) return 1;
    setengah = pangkatCepat(b, e / 2);
    if (e % 2 == 0) return setengah * setengah;
    return b * setengah * setengah;
}

Bonus: pangkat biasa untuk e = 30 butuh 31 panggilan; pangkatCepat cuma 6 (e = 30, 15, 7, 3, 1, 0).

5

Latihan Mandiri

  1. Tulis fungsi rekursif int hitungDigit(int n) yang mengembalikan banyaknya digit n (misal 2026 → 4).
  2. Tulis prosedur rekursif void biner(int n) yang mencetak n dalam bilangan biner (13 → 1101). Petunjuk: cetak biner(n / 2) dulu, baru n % 2.
  3. Telusuri dengan tabel (seperti di penelusur): berapa kali jumlah dipanggil untuk jumlah(6), dan berapa frame maksimal yang menumpuk bersamaan?
#include <stdio.h>

int hitungDigit(int n) {
    if (n < 10) return 1;
    return 1 + hitungDigit(n / 10);
}

void biner(int n) {
    if (n >= 2) {
        biner(n / 2);
    }
    printf("%d", n % 2);
}

int main(void) {
    printf("Digit 2026: %d\n", hitungDigit(2026));
    printf("13 dalam biner: ");
    biner(13);
    printf("\n");
    return 0;
}
Digit 2026: 4
13 dalam biner: 1101

Nomor 3: jumlah(6), jumlah(5), …, jumlah(0) = 7 panggilan. Karena tidak ada yang selesai sebelum jumlah(0) tercapai, ketujuhnya menumpuk bersamaan (ditambah frame main).

6

Cek Pemahaman

1. Dua bagian yang wajib ada di setiap fungsi rekursif adalah…

Base case menghentikan rekursi; recursive case memperkecil masalah dan memanggil diri sendiri.

2. Dengan fungsi jumlah di atas, berapa nilai jumlah(4)?

4 + jumlah(3) = 4 + 3 + jumlah(2) = 4 + 3 + 2 + 1 + jumlah(0) = 4 + 3 + 2 + 1 + 0 = 10.

3. Fungsi cetak(n) mencetak n, memanggil cetak(n - 1), lalu mencetak n lagi (base case n == 0). Apa output cetak(3)?

printf pertama dijalankan di fase turun (3, 2, 1). printf kedua baru dijalankan saat frame dilepas di fase naik, mulai dari frame terdalam (1, 2, 3).

4. Apa yang terjadi saat memanggil f(5)?

int f(int n) {
    if (n == 0) return 0;
    return 1 + f(n - 2);
}
n melompati 0 karena berkurang 2 dari bilangan ganjil. Base case-nya harus n <= 0 supaya aman.

5. Saat faktorial(5) mencapai base case, berapa frame faktorial yang sedang menumpuk di stack?

faktorial(5), (4), (3), (2), (1) — lima frame, semuanya menunggu. Base case n ≤ 1 tercapai di faktorial(1). Cek di penelusur.
Skor: 0 / 5 terjawab benar
7

Ringkasan Pertemuan 11

  • Rekursif = fungsi memanggil dirinya sendiri untuk masalah yang lebih kecil.
  • Wajib ada base case (berhenti) dan recursive case (memperkecil + menggabungkan).
  • Tiap panggilan punya frame sendiri. Fase turun menumpuk frame; fase naik mengembalikan hasil satu per satu.
  • Rancang dengan tiga pertanyaan: kasus terkecil? cara memperkecil? cara menggabungkan?
  • Tanpa base case (atau base case terlewati) → stack overflow.
Selanjutnya

Pertemuan terakhir: rekursif yang memanggil dirinya dua kali (Fibonacci), teka-teki Menara Hanoi, pencarian biner, perbandingan rekursif vs iteratif — dan presentasi proyek akhir.

made by boflyeta.dev