Recursion adalah teknik pemrograman di mana sebuah fungsi memanggil dirinya sendiri untuk menyelesaikan sub-masalah yang lebih kecil. Recursion cocok untuk masalah yang memiliki struktur self-similar—misalnya factorial, Fibonacci, traversal pohon, atau algoritma divide and conquer seperti quicksort. Namun recursion juga membawa risiko serius: setiap pemanggilan mengonsumsi stack frame, dan recursion tanpa base case akan mengakibatkan stack overflow. Pada chapter ini kita akan menelusuri dua contoh klasik recursion (factorial dan Fibonacci), membedah struktur base case dan recursive case, serta membahas risiko stack overflow dan kapan recursion sebaiknya dihindari.

Anatomi Recursion: Base Case dan Recursive Case #

Setiap fungsi rekursif harus memiliki dua komponen:

  1. Base case: kondisi penghentian di mana fungsi mengembalikan nilai langsung tanpa memanggil dirinya lagi. Tanpa base case, recursion berjalan tanpa henti sampai stack overflow.
  2. Recursive case: kondisi di mana fungsi memanggil dirinya dengan input yang lebih kecil, mendekati base case.

Pemanggilan rekursif harus selalu mendekati base case; bila tidak, recursion tidak akan pernah berhenti.

Contoh Klasik: Factorial #

Factorial dari n (ditulis n!) adalah hasil perkalian 1 × 2 × 3 × ... × n. Definisi rekursifnya: n! = n × (n-1)!, dengan base case 0! = 1. Contoh: 5! = 5 × 4! = 5 × 4 × 3! = ... = 120.

c 
#include <stdio.h>

/* Recursive factorial: n! = n * (n-1)! */
long factorial(int n) {
    if (n <= 1) {
        return 1;                  /* Base case */
    }
    return n * factorial(n - 1);   /* Recursive case */
}

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

Output yang Dihasilkan:

text 
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800

Mari kita telaah baris-baris kode di atas:

  1. Baris 4 (long factorial(int n)): return type long agar dapat menampung factorial besar (misal 10! = 3628800 yang masih dalam rentang long 64-bit).
  2. Baris 5-7 (if (n <= 1) return 1;): base case. Bila n ≤ 1, fungsi mengembalikan 1 tanpa recursion. Tanpa base case ini, recursion akan berjalan tanpa henti.
  3. Baris 8 (return n * factorial(n - 1);): recursive case. Fungsi memanggil factorial(n - 1)—pemanggilan dengan input yang lebih kecil, mendekati base case. Setelah pemanggilan rekursif kembali, hasilnya dikalikan dengan n lalu dikembalikan.

Saat factorial(5) dipanggil, urutan eksekusi adalah: factorial(5) → 5 * factorial(4) → 5 * (4 * factorial(3)) → ... → 5 * 4 * 3 * 2 * 1 = 120. Setiap pemanggilan membuat stack frame baru di call stack; setelah base case tercapai, stack frame dibongkar satu per satu dan hasil dihitung mundur.

Visualisasi Konsep #

Diagram berikut memperlihatkan tumpukan call stack saat factorial(5) dievaluasi secara rekursif, mulai dari pemanggilan awal hingga base case dan pelipatan kembali:

Pada diagram di atas, recursion terbagi menjadi dua fase: fase push (menumpuk stack frame) dan fase pop (membongkar stack frame dan menghitung hasil). Fase push berjalan dari factorial(5) turun ke factorial(1)—setiap pemanggilan membuat stack frame baru berisi parameter n dan alamat return. Saat base case factorial(1) tercapai, fase pop dimulai: setiap stack frame dihitung mundur (factorial(2) = 2 * 1 = 2, factorial(3) = 3 * 2 = 6, dan seterusnya) hingga mencapai factorial(5) = 120. Karena setiap pemanggilan mengonsumsi stack frame, recursion terlalu dalam akan menyebabkan stack overflow—oleh karena itu selalu pastikan recursion mendekati base case pada setiap langkah.

Contoh Klasik: Fibonacci #

Deret Fibonacci didefinisikan sebagai Fib(0) = 0, Fib(1) = 1, dan Fib(n) = Fib(n-1) + Fib(n-2) untuk n ≥ 2. Implementasi rekursif paling langsung:

c 
#include <stdio.h>

/* Recursive Fibonacci: Fib(n) = Fib(n-1) + Fib(n-2) */
int fib(int n) {
    if (n <= 0) return 0;          /* Base case 1 */
    if (n == 1) return 1;           /* Base case 2 */
    return fib(n - 1) + fib(n - 2); /* Recursive case */
}

int main(void) {
    printf("Deret Fibonacci (0..15): ");
    for (int i = 0; i <= 15; i++) {
        printf("%d", fib(i));
        if (i < 15) printf(", ");
    }
    printf("\n");
    return 0;
}

Output yang Dihasilkan:

text 
Deret Fibonacci (0..15): 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610

Fungsi fib memiliki dua base case (n <= 0 → 0, n == 1 → 1) dan satu recursive case. Perhatikan bahwa pemanggilan fib(n - 1) + fib(n - 2) membuat dua pemanggilan rekursif pada setiap level. Konsekuensinya, kompleksitas waktu fungsi ini adalah eksponensial O(2^n)—fib(40) dapat memakan detik untuk dihitung karena pemanggilan rekursif yang tumpang tindih. Untuk n besar, gunakan versi iteratif atau memoization (seperti yang ditunjukkan pada chapter Static Local Variables).

Tail Recursion #

Tail recursion adalah bentuk recursion di mana pemanggilan rekursif adalah operasi terakhir yang dilakukan fungsi—hasil pemanggilan rekursif dikembalikan langsung tanpa operasi tambahan. Beberapa compiler dapat mengoptimalkan tail recursion menjadi loop, menghilangkan overhead stack frame. Sayangnya, GCC tidak melakukan optimisasi tail call di C secara default (kecuali dengan flag -O2 dan beberapa syarat).

c 
#include <stdio.h>
#include <stdlib.h>

/* Prototype untuk fungsi yang dipakai sebelum didefinisikan */
long factorial(int n);

/* Recursion biasa: factorial */
long factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

/* Tail recursion: accumulator menjadi parameter */
long factorial_tail(int n, long acc) {
    if (n <= 1) return acc;
    return factorial_tail(n - 1, n * acc);
}

/* Versi wrapper untuk panggilan awal */
long factorial_iter(int n) {
    return factorial_tail(n, 1L);
}

/* Contoh recursion dengan deep call */
void hitung_mundur(int n) {
    if (n <= 0) {
        printf("Selesai!\n");
        return;
    }
    printf("%d ", n);
    hitung_mundur(n - 1);
}

int main(void) {
    printf("5! (rekursif biasa)  = %ld\n", factorial(5));
    printf("5! (tail recursive)  = %ld\n", factorial_iter(5));
    printf("Hitung mundur: ");
    hitung_mundur(5);
    return 0;
}

Output yang Dihasilkan:

text 
5! (rekursif biasa)  = 120
5! (tail recursive)  = 120
Hitung mundur: 5 4 3 2 1 Selesai!

Pada contoh di atas, factorial_tail menerima parameter tambahan acc (accumulator) yang membawa hasil parsial. Pemanggilan rekursif factorial_tail(n - 1, n * acc) adalah tail call karena tidak ada operasi lain setelah pemanggilan—hasilnya langsung dikembalikan. Bandingkan dengan factorial biasa: pemanggilan n * factorial(n - 1) bukan tail call karena hasil pemanggilan rekursif masih dikalikan dengan n setelahnya.

Risiko Stack Overflow #

Recursion tanpa base case, atau dengan kedalaman yang sangat besar, dapat menyebabkan stack overflow. Setiap pemanggilan fungsi mengonsumsi stack frame (berisi parameter, variabel lokal, alamat kembali). Stack memiliki ukuran terbatas (umumnya 8 MB di Linux). Bila recursion terlalu dalam, stack habis dan program crash dengan segmentation fault.

c 
#include <stdio.h>

/* Demonstrate stack overflow dengan recursion tak berujung */
void loop_tanpa_henti(int n) {
    printf("n = %d (alamat: %p)\n", n, (void *)&n);
    loop_tanpa_henti(n + 1);   /* Tanpa base case - akan stack overflow */
}

int main(void) {
    loop_tanpa_henti(1);
    return 0;
}

Output yang Dihasilkan (terpotong—program crash karena segmentation fault):

text 
n = 261927 (alamat: 0x7ffd10d40c5c)
n = 261928 (alamat: 0x7ffd10d40c3c)
n = 261929 (alamat: 0x7ffd10d40c1c)
n = 261930 (alamat: 0x7ffd10d40bfc)
n = 261931 (alamat: 0x7ff---Segmentation fault

Pada contoh di atas, fungsi loop_tanpa_henti tidak memiliki base case—setiap pemanggilan menambah stack frame baru tanpa pernah membebaskan. Setelah sekitar 261.000 pemanggilan (bergantung pada ukuran stack dan stack frame), stack habis dan program crash. Compiler GCC modern mendeteksi pola ini dan mengeluarkan warning -Winfinite-recursion saat kompilasi.

Dengan pemahaman recursion, kita siap melangkah ke chapter Function Pointers (Pengantar) untuk membahas bagaimana fungsi sendiri dapat diperlakukan sebagai data yang dilewatkan antar fungsi.