Rekursif lanjutan — rekursi bercabang pada Fibonacci, teka-teki Menara Hanoi, dan pencarian biner; kapan memilih rekursif atau iteratif; lalu finishing dan presentasi proyek akhir.
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):
#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
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:
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
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.
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
Semua yang bisa ditulis rekursif bisa juga ditulis iteratif (dan sebaliknya). Pertanyaannya: mana yang lebih cocok?
| Rekursif | Iteratif (loop) | |
|---|---|---|
| Kejelasan kode | Sangat jelas untuk masalah bercabang/bersarang (Hanoi, pohon, struktur folder) | Lebih jelas untuk proses lurus (menjumlah, mencari di array) |
| Memori | Setiap panggilan butuh frame; terlalu dalam → stack overflow | Hemat, cukup beberapa variabel |
| Kecepatan | Ada biaya tiap pemanggilan; bisa sangat boros kalau subsoal berulang (fib naif) | Umumnya lebih cepat |
| Contoh cocok | Hanoi, pencarian biner, menjelajah pohon/graf, algoritma bagi-dan-taklukkan | Faktorial, fibonacci, jumlah deret, traversal array |
int palindrom(char s[], int kiri, int kanan).cariBiner rekursif.
#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
Tunjukkan semua menu dengan input normal dan satu input aneh.
Jelaskan satu fungsi rekursif: base case-nya apa, bagaimana masalah diperkecil.
Gambar call stack untuk satu contoh kecil, mis. faktorial(3).
Ceritakan satu bug yang kamu temui dan cara menemukannya.
| Kriteria penilaian proyek | Bobot |
|---|---|
| Program berjalan, semua menu benar (termasuk validasi input) | 35% |
| Struktur: main hanya menu, logika dalam fungsi, nama jelas | 20% |
| Rekursif: base case dan recursive case tepat | 25% |
| Kerapian: indentasi konsisten, komentar seperlunya | 10% |
| Presentasi dan kemampuan menelusuri kode sendiri | 10% |
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)?
3. (P5) Nilai 70 dimasukkan ke rantai if (nilai >= 85) … else if (nilai >= 70) … else if (nilai >= 55) …. Berapa cabang yang dijalankan?
4. (P6) Berapa kali badan for (i = 1; i < 10; i += 3) dijalankan?
5. (P8) int a[4] = {5, 2, 8, 1}; — ekspresi mana yang menghasilkan elemen terakhir?
a[4] di luar batas; C juga tidak mengenal indeks negatif seperti Python.6. (P9) Berapa byte yang dibutuhkan untuk menyimpan string "C!"?
7. (P10) void f(int x) { x = 100; } dipanggil sebagai f(a) dengan a = 5. Berapa a setelahnya?
int *x dan dipanggil dengan f(&a).8. (P11–P12) Berapa langkah minimum untuk menyelesaikan Menara Hanoi dengan 4 cakram?