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.
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:
Kasus paling kecil yang jawabannya langsung diketahui tanpa memanggil diri sendiri. "Aku orang paling depan, nomorku 1."
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:
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 */
}
Ingat stack frame dari Pertemuan 10? Setiap pemanggilan faktorial mendapat frame sendiri dengan n-nya masing-masing. Ada dua fase:
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.
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):
| Pertanyaan | pangkat(b, e) = be | jumlahDigit(n) |
|---|---|---|
| 1. Kasus terkecil & jawabannya? | e = 0 → 1 | n < 10 (satu digit) → n itu sendiri |
| 2. Bagaimana memperkecil masalah? | e − 1 | buang 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
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.Lanjutkan toolkit.c dari Pertemuan 10:
jumlahDigit dengan versi rekursif. Program harus tetap memberi hasil yang sama (472 → 13). Jangan lupa tangani bilangan negatif di luar fungsi rekursifnya.long long). Tolak input negatif dan input di atas 20 dengan pesan yang jelas — 21! sudah tidak muat di long long.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).
int hitungDigit(int n) yang mengembalikan banyaknya digit n (misal 2026 → 4).void biner(int n) yang mencetak n dalam bilangan biner (13 → 1101). Petunjuk: cetak biner(n / 2) dulu, baru n % 2.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).
1. Dua bagian yang wajib ada di setiap fungsi rekursif adalah…
2. Dengan fungsi jumlah di atas, berapa nilai jumlah(4)?
3. Fungsi cetak(n) mencetak n, memanggil cetak(n - 1), lalu mencetak n lagi (base case n == 0). Apa output cetak(3)?
4. Apa yang terjadi saat memanggil f(5)?
int f(int n) {
if (n == 0) return 0;
return 1 + f(n - 2);
}
n <= 0 supaya aman.5. Saat faktorial(5) mencapai base case, berapa frame faktorial yang sedang menumpuk di stack?