Dokumentasi C interaktif: Rekursi

Q: Apa itu rekursi di C?

Rekursi adalah fungsi yang memanggil dirinya sendiri untuk menyelesaikan versi lebih kecil dari masalah yang sama. Setiap fungsi rekursif butuh dua hal: base case yang kembali tanpa rekursi, dan kasus rekursif yang bergerak semakin dekat ke base case itu secara nyata. Tanpa base case, pemanggilannya tidak pernah berhenti dan program crash karena stack overflow.

Q: Bagaimana cara menulis fungsi faktorial di C?

int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); }. Base case-nya menangani 0 dan 1, dan setiap pemanggilan rekursif mengurangi n satu per satu sampai mencapainya. Perhatikan bahwa int mengalami overflow di 13!: pakai unsigned long long untuk nilai yang lebih besar.

Q: Kenapa Fibonacci rekursif sangat lambat di C?

Karena fib(n) memanggil fib(n-1) dan fib(n-2), yang menghitung ulang submasalah yang sama berkali-kali. Jumlah pemanggilannya tumbuh secara eksponensial, sehingga fib(50) bisa butuh waktu bertahun-tahun. Menulis ulangnya sebagai loop yang menyimpan dua nilai terakhir membuatnya linear dan instan.

Q: Apa penyebab stack overflow pada rekursi di C?

Setiap pemanggilan memakai satu frame memori stack untuk parameter dan variabel lokalnya, dan stack hanya berukuran beberapa megabyte. Base case yang hilang atau tidak bisa dicapai berarti rekursi tak berujung dan crash seketika; bahkan rekursi yang benar pun bisa menghabiskan stack kalau kedalamannya mencapai ratusan ribu tingkat.

Fungsi yang memanggil dirinya sendiri

Tidak ada yang melarang fungsi C memanggil dirinya sendiri. Namanya sendiri sudah berada dalam scope di dalam badannya, jadi ini sah:

void countdown(int n) {
    printf("%d\n", n);
    countdown(n - 1);      /* calls itself - but never stops! */
}

Tapi kode itu juga rusak. Ia mencetak tanpa henti, sampai ke angka negatif, sampai programnya crash. Yang hilang adalah base case: kondisi saat fungsi kembali tanpa memanggil dirinya sendiri.

#include <stdio.h>

void countdown(int n) {
    if (n <= 0) {              /* base case: stop */
        printf("Liftoff!\n");
        return;
    }
    printf("%d\n", n);
    countdown(n - 1);          /* recursive case: a smaller problem */
}

int main(void) {
    countdown(5);
    return 0;
}

Setiap fungsi rekursif punya tepat dua bagian ini:

Base case: input terkecil, yang dijawab langsung tanpa pemanggilan lagi.
Kasus rekursif: menyelesaikan masalah lewat versi dirinya yang benar-benar lebih kecil.

"Benar-benar lebih kecil" adalah bagian yang sering salah. countdown(n - 1) bergerak ke arah 0 di setiap pemanggilan. countdown(n) tidak, dan begitu juga countdown(n / 2) kalau n bisa tetap 1 selamanya. Setiap jalur harus memperkecil masalahnya, atau base case tidak akan pernah tercapai.

Faktorial

Contoh pertama yang standar. n! adalah n × (n-1) × ... × 1, dan 0! didefinisikan sebagai 1. Definisi itu sudah rekursif: n! = n × (n-1)!.

#include <stdio.h>

unsigned long long factorial(int n) {
    if (n <= 1) {                       /* base case: 0! and 1! are both 1 */
        return 1;
    }
    return n * factorial(n - 1);        /* recursive case */
}

int main(void) {
    for (int i = 0; i <= 10; i++) {
        printf("%2d! = %llu\n", i, factorial(i));
    }
    printf("20! = %llu\n", factorial(20));
    return 0;
}

Telusuri factorial(4) untuk melihat bagaimana jawabannya disusun. Pemanggilannya turun ke bawah, dan perkaliannya terjadi saat kembali naik:

factorial(4)  -> 4 * factorial(3)
                      factorial(3) -> 3 * factorial(2)
                                           factorial(2) -> 2 * factorial(1)
                                                                factorial(1) -> 1   (base case)
                                           factorial(2) = 2 * 1  = 2
                      factorial(3) = 3 * 2  = 6
factorial(4)  = 4 * 6  = 24

Tidak ada yang dikalikan sampai base case kembali. Setiap pemanggilan yang tertunda duduk menunggu sambil memegang n miliknya sendiri, dan inilah hal yang perlu dipahami betul: pemanggilan yang menunggu itu memakan memori.

Perhatikan tipe kembaliannya. int mengalami overflow sekitar 13!, diam-diam menghasilkan angka yang salah, karena C tidak memeriksanya. unsigned long long bisa sampai 20! dan tidak lebih, karena 21! melebihi 64 bit. Yang membatasi di sini bukan rekursinya, tapi tipenya.

Base case-nya sengaja memakai n <= 1, bukan n == 1: factorial(0) seharusnya 1, dan <= menanganinya. Dengan n == 1, memanggil factorial(0) akan terus berekursi ke -1, -2, dan tidak pernah berhenti. Ini ilustrasi yang bagus tentang bagaimana base case yang "jelas benar" bisa melewatkan sebuah input.

Fibonacci, dan kenapa versi naifnya adalah jebakan

Fibonacci adalah contoh klasik lainnya: setiap angka adalah jumlah dua angka sebelumnya, dimulai dari 0 dan 1. Definisi rekursifnya bisa langsung ditulis.

#include <stdio.h>

long long calls = 0;

int fib(int n) {
    calls++;
    if (n < 2) {
        return n;                       /* fib(0) = 0, fib(1) = 1 */
    }
    return fib(n - 1) + fib(n - 2);
}

int main(void) {
    for (int n = 10; n <= 35; n += 5) {
        calls = 0;
        int result = fib(n);
        printf("fib(%2d) = %-8d (%lld calls)\n", n, result, calls);
    }
    return 0;
}

Lihat jumlah pemanggilannya. fib(10) butuh 177 pemanggilan; fib(35) butuh hampir 30 juta. Setiap kenaikan 5 mengalikan pekerjaannya sekitar sebelas kali.

Alasannya terlihat di pohon pemanggilannya. fib(5) memanggil fib(4) dan fib(3); fib(4) memanggil fib(3) lagi; dan masing-masing menghitung ulang fib(2) dari awal. Tidak ada yang diingat, jadi submasalah yang sama diselesaikan berulang-ulang, dan jumlah pemanggilan tumbuh kira-kira seperti 1,6ⁿ. fib(50) dengan cara ini akan berjalan berhari-hari; fib(100) akan berjalan lebih lama dari umur alam semesta.

Versi loop menyimpan dua nilai terakhir dan bersifat linear:

#include <stdio.h>

long long fibFast(int n) {
    if (n < 2) {
        return n;
    }
    long long prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        long long next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

int main(void) {
    for (int n = 10; n <= 90; n += 10) {
        printf("fib(%2d) = %lld\n", n, fibFast(n));
    }
    return 0;
}

fib(90) langsung selesai. Pelajarannya bukan "rekursi itu lambat", tapi rekursi dengan submasalah yang tumpang tindih itu lambat kecuali kamu mengingat jawabannya. Simpan hasilnya di array sambil menghitung (memoization), dan versi rekursifnya juga jadi linear.

Call stack dan stack overflow

Setiap pemanggilan fungsi butuh tempat untuk menyimpan parameternya, variabel lokalnya, dan alamat untuk kembali. Tempat penyimpanan itu adalah stack frame, yang didorong masuk saat pemanggilan dimulai dan dikeluarkan saat fungsi kembali. Rekursi menumpuk frame satu di atas yang lain: factorial(1000) punya seribu frame yang hidup bersamaan, masing-masing dengan n miliknya sendiri.

Stack tidak besar. Ukuran bawaan yang umum adalah 1 sampai 8 MB, jadi beberapa puluh ribu frame adalah batas yang realistis, dan jauh lebih sedikit kalau setiap frame menyimpan array lokal yang besar. Lewati batas itu dan programnya mati:

Segmentation fault (core dumped)

Itulah stack overflow, dan ada dua cara mendapatkannya:

Rekursi tak berujung: base case yang hilang atau tidak bisa dicapai. Ini bug, dan crash-nya langsung terjadi:

int bad(int n) {
    return bad(n - 1);      /* no base case - crashes in a fraction of a second */
}

Benar tapi terlalu dalam: berekursi sekali per elemen pada list berisi sejuta item. Logikanya benar; pendekatannya tidak muat di stack. Tulis ulang sebagai loop, atau susun ulang supaya kedalamannya logaritmik (berekursi pada separuh bagian, seperti yang dilakukan binary search dan merge sort, memberi kedalaman sekitar 20 untuk sejuta item).

Sebagian compiler bisa mengubah tail recursion, yaitu saat pemanggilan rekursif adalah hal paling akhir yang dilakukan fungsi tanpa pekerjaan tertunda sesudahnya, menjadi loop yang memakai ulang satu frame. countdown di atas adalah tail recursive; factorial bukan, karena perkaliannya masih harus dilakukan setelah pemanggilan kembali. Tapi C tidak mewajibkan optimasi ini, jadi bisa terjadi atau tidak, tergantung compiler dan flag-nya. Jangan pernah menulis C yang hanya bekerja karena optimizer menghilangkan sebuah tail call.

Di mana rekursi benar-benar unggul

Setiap fungsi rekursif bisa ditulis ulang sebagai loop, dan untuk penghitungan sederhana loop jelas lebih baik. Rekursi baru menunjukkan nilainya saat datanya sendiri rekursif, yaitu saat sebuah struktur berisi salinan dirinya yang lebih kecil.

Binary search adalah contoh yang rapi: cari di separuh bagian, lalu separuh dari bagian itu.

#include <stdio.h>

/* returns the index of target, or -1 */
int binarySearch(const int a[], int low, int high, int target) {
    if (low > high) {
        return -1;                          /* base case: nothing left */
    }
    int mid = low + (high - low) / 2;       /* avoids overflow on big indices */

    if (a[mid] == target) {
        return mid;                         /* base case: found it */
    }
    if (a[mid] < target) {
        return binarySearch(a, mid + 1, high, target);
    }
    return binarySearch(a, low, mid - 1, target);
}

int main(void) {
    int sorted[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(sorted) / sizeof(sorted[0]);

    int targets[] = {23, 2, 91, 50};
    for (int i = 0; i < 4; i++) {
        printf("%2d -> index %d\n", targets[i], binarySearch(sorted, 0, n - 1, targets[i]));
    }
    return 0;
}

Di sini ada dua base case, dan itu normal: satu untuk berhasil dan satu untuk habis. Kedalamannya sekitar log₂(n), jadi bahkan satu miliar elemen hanya butuh tiga puluh frame.

Tempat lain di mana rekursi paling cocok: menelusuri tree atau linked list, menjelajahi direktori, mem-parse ekspresi bersarang, dan algoritma pengurutan divide-and-conquer seperti quicksort dan merge sort. Di semua itu, kode rekursifnya lebih pendek sekaligus lebih jelas daripada loop dengan stack eksplisit yang menggantikannya.

Rekursi atau loop?

Use a loop when       the problem is linear - counting, summing, scanning
Use recursion when    the data is nested - trees, nested structures, divide and conquer
Rewrite recursion     if the depth can grow with the input size without bound
Never use recursion   when subproblems overlap, unless you memoize

Dua catatan praktis. Pemanggilan rekursif sedikit lebih mahal daripada satu iterasi loop, karena ada frame yang harus didorong dan dikeluarkan setiap kali, jadi untuk loop sederhana yang sering dijalankan, versi iteratif menang dalam kecepatan sekaligus memori. Lalu debugging-nya berbeda: stack trace dari rekursi yang dalam berisi ratusan frame yang kelihatan sama, jadi cetak parameternya saat fungsi dimasuki (seperti yang dilakukan penghitung calls di atas) saat ada yang tidak berhenti.

Menulis fungsi rekursif: daftar cek

Temukan base case lebih dulu. Apa input terkecilnya, dan apa jawabannya? Kalau kamu tidak bisa menyebutkannya, fungsinya tidak bisa ditulis.
Anggap pemanggilan rekursifnya bekerja. Jangan menelusurinya di kepala: percayalah bahwa factorial(n - 1) mengembalikan (n-1)!, lalu tulis satu langkah yang mengubahnya menjadi jawaban.
Pastikan setiap jalur mengecil. Setiap pemanggilan rekursif harus bergerak ke arah base case untuk setiap input yang mungkin, termasuk 0 dan angka negatif.
Periksa kedalamannya. Kira-kira berapa frame dalamnya rekursi ini pada data sungguhan? Ribuan tidak masalah; jutaan tidak.
Periksa tumpang tindihnya. Kalau submasalah yang sama dihitung dua kali, kamu butuh memoization atau loop.

Pertanyaan yang sering diajukan

Apa itu rekursi di C?

Rekursi adalah fungsi yang memanggil dirinya sendiri untuk menyelesaikan versi lebih kecil dari masalah yang sama. Setiap fungsi rekursif butuh dua hal: base case yang kembali tanpa rekursi, dan kasus rekursif yang bergerak semakin dekat ke base case itu secara nyata. Tanpa base case, pemanggilannya tidak pernah berhenti dan program crash karena stack overflow.

Bagaimana cara menulis fungsi faktorial di C?

int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); }. Base case-nya menangani 0 dan 1, dan setiap pemanggilan rekursif mengurangi n satu per satu sampai mencapainya. Perhatikan bahwa int mengalami overflow di 13!: pakai unsigned long long untuk nilai yang lebih besar.

Kenapa Fibonacci rekursif sangat lambat di C?

Karena fib(n) memanggil fib(n-1) dan fib(n-2), yang menghitung ulang submasalah yang sama berkali-kali. Jumlah pemanggilannya tumbuh secara eksponensial, sehingga fib(50) bisa butuh waktu bertahun-tahun. Menulis ulangnya sebagai loop yang menyimpan dua nilai terakhir membuatnya linear dan instan.

Apa penyebab stack overflow pada rekursi di C?