Saat fungsi rekursif dipanggil, compiler tidak hanya melacak “di mana kita sekarang” tetapi juga semua konteks pemanggilan sebelumnya. Setiap pemanggilan fungsi mendapatkan stack frame sendiri di call stack — area memori yang berisi parameter, variabel lokal, dan alamat pengembalian. Memahami call stack adalah kunci untuk memahami mengapa rekursi bekerja, mengapa variabel lokal bersifat independen antar pemanggilan, serta mengapa rekursi terlalu dalam menyebabkan stack overflow. Pada Chapter ini kita akan membedah call stack untuk factorial(5), melihat pertumbuhan dan unwinding-nya, lalu mengukur batas stack praktis di sistem Linux.

Anatomi Stack Frame #

Setiap stack frame berisi:

  1. Parameter fungsi: nilai argumen yang dilewatkan ke fungsi.
  2. Variabel lokal: variabel yang dideklarasikan di dalam fungsi.
  3. Alamat pengembalian: instruksi setelah pemanggil (caller).
  4. Saved registers: register yang harus dipulihkan saat fungsi kembali.

Ukuran frame bergantung pada jumlah dan tipe variabel lokal. Frame factorial(n) mungkin hanya 16 byte (parameter n, return address, padding), sedangkan frame dengan banyak std::vector bisa ratusan byte.

Mekanisme: Push saat Panggil, Pop saat Return #

Saat fungsi f memanggil g:

  1. Caller f mengevaluasi argumen, menempatkannya di register atau stack.
  2. Instruksi call g menyimpan alamat pengembalian ke stack, lalu melompat ke g.
  3. Prologue g menyimpan register yang akan dipakai, mengalokasikan ruang untuk variabel lokal.
  4. g dieksekusi.
  5. Epilogue g mengembalikan nilai, memulihkan register, pop frame, melompat ke alamat pengembalian.

Pada rekursi, langkah 1-3 terjadi berulang hingga base case. Lalu langkah 4-5 berurutan dari frame terdalam ke terluar — unwinding.

Call Stack factorial(5): Pertumbuhan #

Saat factorial(5) dipanggil dari main, call stack memiliki frame main dan factorial(5). Frame factorial(5) menyimpan n = 5. Saat factorial(5) memanggil factorial(4), frame baru ditambahkan di atas dengan n = 4. Demikian seterusnya hingga factorial(1) mencapai base case dan mengembalikan 1.

Call Stack factorial(5): Unwinding #

Setelah base case factorial(1) = 1 dikembalikan, frame factorial(1) di-pop. Sekarang factorial(2) melanjutkan dari titik pemanggilan, mengalikan 2 * 1 = 2, lalu return. Proses ini berlanjut hingga factorial(5) mengembalikan 120 ke main.

Variabel Lokal Bersifat Independen #

Kode: Variabel Lokal Berbeda di Setiap Frame #

cpp 
#include <iostream>

long long factorial_with_local(int n) {
    long long local_result;  // variabel lokal unik per frame
    std::cout << "masuk factorial(" << n
              << "), &local_result = " << &local_result << '\n';

    if (n <= 1) {
        local_result = 1;
    } else {
        local_result = n * factorial_with_local(n - 1);
    }

    std::cout << "kembali factorial(" << n
              << ") = " << local_result << '\n';
    return local_result;
}

int main() {
    long long hasil = factorial_with_local(3);
    std::cout << "hasil: " << hasil << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
masuk factorial(3), &local_result = 0x7fff945118d8
masuk factorial(2), &local_result = 0x7fff945118a8
masuk factorial(1), &local_result = 0x7fff94511878
kembali factorial(1) = 1
kembali factorial(2) = 2
kembali factorial(3) = 6
hasil: 6
  1. Alamat local_result berbeda di setiap frame: 0x...18d8, 0x...18a8, 0x...1878 — turun 48 byte per frame (ukuran frame factorial_with_local). Ini menunjukkan setiap pemanggilan memiliki variabel lokalnya sendiri.
  2. Variabel tidak terlihat antar frame: factorial(3) tidak bisa mengakses local_result dari factorial(2). Variabel lokal bersifat private per pemanggilan.
  3. Urutan “masuk”: turun (3 → 2 → 1), urutan “kembali”: naik (1 → 2 → 3). Sesuai pola LIFO stack.

Mengukur Ukuran Frame #

Kita dapat mengukur ukuran frame dengan mengurangi alamat variabel lokal di dua pemanggilan berurutan.

Kode: Mengukur Frame Size #

cpp 
#include <iostream>
#include <cstdint>

long g_prev_addr = 0;
long g_frame_size = 0;

long long factorial_measure(int n) {
    int local_marker;
    long cur_addr = reinterpret_cast<intptr_t>(&local_marker) & 0xFFFFF;

    if (g_prev_addr != 0) {
        g_frame_size = g_prev_addr - cur_addr;
    }
    g_prev_addr = cur_addr;

    if (n <= 1) return 1;
    return n * factorial_measure(n - 1);
}

int main() {
    long long hasil = factorial_measure(5);
    std::cout << "hasil = " << hasil << '\n';
    std::cout << "ukuran frame (approx) = " << g_frame_size << " byte\n";
    return 0;
}

Kompilasi tanpa optimasi agar layout stack akurat: g++ -O0 -std=c++17 ...

Output yang Dihasilkan:

text 
hasil = 120
ukuran frame (approx) = 64 byte
  1. reinterpret_cast<intptr_t>(&local_marker): mengambil alamat variabel lokal sebagai integer.
  2. & 0xFFFFF: mask 20 bit bawah agar mudah dibandingkan. 20 bit cukup untuk variasi dalam satu stack.
  3. g_frame_size = g_prev_addr - cur_addr: selisih alamat antar frame = ukuran frame. Karena stack tumbuh ke alamat rendah, prev - cur > 0.
  4. Hasil 64 byte: ukuran frame untuk fungsi sederhana dengan satu int lokal. Frame ini juga berisi parameter, return address, saved registers, alignment padding.

Batas Call Stack dan Overflow #

Call stack berukuran terbatas. Default di Linux: 8 MB. Di macOS: 8 MB. Di Windows: 1 MB (lebih kecil!).

Bila rekursi terlalu dalam, stack habis → stack overflow. Gejalanya:

  • Program crash dengan Segmentation fault (Linux) atau Stack overflow (Windows).
  • Pesan error sering tidak menyebut penyebab asli.
  • Tidak ada exception C++ yang dilempar — stack overflow langsung menghentikan proses.

Kode: Memicu Stack Overflow (Demonstrasi) #

cpp 
#include <iostream>

// Fungsi rekursi tak berhenti — akan overflow
void infinite_recursion(int depth) {
    // Safety net untuk demonstrasi (jangan dihapus)
    if (depth > 100000) {
        std::cout << "depth > 100000, berhenti paksa\n";
        return;
    }
    volatile int dummy[64];  // paksa frame lebih besar
    dummy[0] = depth;
    if (dummy[0] < 0) return;  // baca dummy agar compiler tidak optimasi
    infinite_recursion(depth + 1);
}

int main() {
    infinite_recursion(1);
    std::cout << "selesai\n";
    return 0;
}

Output yang Dihasilkan:

text 
depth > 100000, berhenti paksa
selesai
  1. Fungsi infinite_recursion: tanpa safety net, akan terus memanggil dirinya. dummy[64] memaksa frame 256 byte → batas ~32000 frame pada stack 8 MB.
  2. Kata kunci volatile: mencegah compiler mengoptimalkan dummy keluar dari stack. Variabel tetap dialokasikan di memori.
  3. Safety net if (depth > 100000): berhenti paksa untuk demonstrasi. Tanpa safety net, program crash.
  4. Pelajaran: rekursi yang dalam butuh perhatian khusus — gunakan iterasi atau tail recursion.

Memeriksa Ukuran Stack di Linux #

Kode: Membaca Limit Stack #

cpp 
#include <iostream>
#include <sys/resource.h>

int main() {
    struct rlimit rl;
    getrlimit(RLIMIT_STACK, &rl);
    std::cout << "soft limit stack: " << rl.rlim_cur / 1024 << " KB\n";

    if (rl.rlim_max == RLIM_INFINITY) {
        std::cout << "hard limit stack: unlimited\n";
    } else {
        std::cout << "hard limit stack: " << rl.rlim_max / 1024 << " KB\n";
    }

    // Estimasi maksimum frame rekursi (asumsi 64 byte/frame)
    long long max_frames = rl.rlim_cur / 64;
    std::cout << "estimasi maksimum frame (64 B/frame): "
              << max_frames << " frame\n";
    return 0;
}

Output yang Dihasilkan:

text 
soft limit stack: 8192 KB
hard limit stack: unlimited
estimasi maksimum frame (64 B/frame): 131072 frame
  1. getrlimit(RLIMIT_STACK, &rl): system call POSIX untuk membaca batas stack. rlim_cur = batas soft (bisa dinaikkan ke hard), rlim_max = batas hard.
  2. Cek RLIM_INFINITY: hard limit bisa “unlimited” (RLIM_INFINITY), yang ditampilkan sebagai angka sangat besar. Kita cek eksplisit untuk mencetak teks yang ramah.
  3. Hasil 8192 KB: stack 8 MB — default Linux.
  4. Estimasi 131072 frame: pada 64 byte/frame, kita bisa rekursi ~131 ribu tingkat. Bila frame lebih besar (misal 256 byte), batas turun ke ~32 ribu.
  5. ulimit -s di shell juga menampilkan/mengatur batas ini.

Mengubah Rekursi menjadi Iterasi dengan Stack Eksplisit #

Kode: Factorial dengan std::stack #

cpp 
#include <iostream>
#include <stack>

long long factorial_iterative(int n) {
    std::stack<int> call_stack;
    while (n > 1) {
        call_stack.push(n);
        --n;
    }
    long long result = 1;
    while (!call_stack.empty()) {
        result *= call_stack.top();
        call_stack.pop();
    }
    return result;
}

int main() {
    for (int n : {5, 10, 20}) {
        std::cout << "factorial(" << n << ") = "
                  << factorial_iterative(n) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text 
factorial(5) = 120
factorial(10) = 3628800
factorial(20) = 2432902008176640000
  1. Loop pertama (turun): push setiap nilai n, n-1, ..., 2 ke stack. Simulasi “memanggil rekursif”.
  2. Loop kedua (naik): pop satu per satu, kalikan ke result. Simulasi “unwinding”.
  3. Kompleksitas: O(n) waktu, O(n) ruang — sama dengan rekursi. Tetapi stack berada di heap, jauh lebih besar kapasitasnya.
  4. Hasil sesuai teori: factorial(20) = 2432902008176640000 (mendekati batas long long).

Ringkasan #

  • Setiap pemanggilan fungsi (rekursif atau biasa) membuat stack frame di call stack.
  • Stack frame berisi parameter, variabel lokal, alamat pengembalian, saved registers.
  • Rekursi tumbuh ke alamat rendah; base case memicu unwinding ke alamat tinggi.
  • Variabel lokal bersifat independen per pemanggilan — tidak bisa diakses antar frame.
  • Batas call stack di Linux: 8 MB default (cek ulimit -s). Di Windows: 1 MB.
  • Untuk rekursi yang sangat dalam, gunakan iterasi dengan stack eksplisit (std::stack<T>) yang dialokasikan di heap.