Rekursi

Ada masalah yang strukturnya menyerupai dirinya sendiri: menghitung faktorial berarti mengalikan n dengan faktorial n-1; menelusuri folder berarti menelusuri isi folder beserta subfolder-subfoldernya. Untuk masalah seperti ini, solusi yang paling alami adalah fungsi yang memanggil dirinya sendiri — teknik bernama rekursi. Setiap panggilan memecahkan versi masalah yang sedikit lebih kecil, hingga sampai pada kasus terkecil yang jawabannya sudah pasti. Pada Chapter ini kita menulis dua fungsi rekursif klasik, membedah komponen wajibnya, dan mengukur harganya yang tidak selalu murah.

Fungsi yang Memanggil Diri Sendiri #

Faktorial adalah contoh pembuka yang paling ringkas: n! = n × (n-1) × (n-2) × … × 1, yang bisa dibaca ulang sebagai “n dikali faktorial (n-1)”. Definisi matematis itu langsung menjadi kode:

#include <iostream>

// Basis: 0! = 1! = 1
unsigned long long faktorial(int n) {
    if (n <= 1) {
        return 1;                    // base case: rekrusi berhenti di sini
    }
    return n * faktorial(n - 1);     // recursive case: panggil diri sendiri
}

int main() {
    for (int n : {1, 5, 10, 20}) {
        std::cout << n << "! = " << faktorial(n) << "\n";
    }
    return 0;
}

Output yang Dihasilkan:

1! = 1
5! = 120
10! = 3628800
20! = 2432902008176640000

Dua bagian yang wajib ada pada setiap fungsi rekursif terlihat jelas di sini. Base case (Baris 6-8) adalah kondisi berhenti: saat n <= 1, fungsi menjawab langsung dengan 1 tanpa memanggil siapa pun. Recursive case (Baris 9) adalah langkah yang mengecilkan masalah: n * faktorial(n - 1) memanggil dirinya dengan masukan lebih kecil satu angka, lalu hasilnya dikalikan kembali. Untuk faktorial(5), rantai panggilannya membentang faktorial(5) → faktorial(4) → … → faktorial(1), dan jawaban menyebar kembali dari panggilan terdalam ke luar: 1 → 2 → 6 → 24 → 120. Return type unsigned long long kita pilih karena 20! ≈ 2,43 × 10¹⁸ jauh melampaui kapasitas int biasa.

Base Case: Rem untuk Rekursi #

Base case bukan formalitas — ia satu-satunya penghenti rekrusi. Apa yang terjadi bila ia hilang? Setiap panggilan menyiapkan ruang kerja sendiri di memori, yang disebut stack frame: berisi parameter, variabel lokal, dan alamat kembali ke pemanggil. Panggilan bersarang menumpuk frame di atas frame di stack, dan stack punya batas ukuran yang terbatas (umumnya beberapa MB per program). Potongan berikut tidak punya jalur berhenti — jangan dijalankan sebagai contoh baik:

unsigned long long faktorial(int n) {
    return n * faktorial(n - 1);   // tidak ada jalur berhenti
}

int main() {
    std::cout << faktorial(5) << "\n";
    return 0;
}

Parameter n terus mengecil melewati 0, -1, -2, dan seterusnya tanpa pernah memenuhi kondisi apa pun, sementara stack frame menumpuk tanpa henti. Ketika stack penuh, program berhenti dengan stack overflow — pada Linux biasanya muncul sebagai segmentation fault. Kesalahan yang lebih licik adalah base case yang ADA tetapi tidak pernah tercapai (misalnya memeriksa n == 0 padahal n berkurang dua per langkah); gejalanya sama. Praktik amannya: pastikan setiap jalur rekursi mengarah ke base case, dan uji fungsi rekursif dengan masukan terkecilnya lebih dulu.

Menghitung Biaya Rekursi: Kasus Fibonacci #

Faktorial memanggil dirinya SATU kali per langkah — rantainya lurus. Fibonacci naif memanggil dirinya DUA kali, dan di sanalah biayanya bertumbuh eksponensial. Program berikut menghitung fibonacci dengan rekrusi sambil menghitung jumlah pemanggilan, lalu membandingkannya dengan versi loop:

#include <iostream>

long long jumlahPanggilan = 0;   // penghitung global untuk melihat biaya rekrusi

// Versi rekrusi naif: dua cabang per panggilan
long long fibonacci(int n) {
    ++jumlahPanggilan;
    if (n <= 1) {
        return n;    // base case: fib(0) = 0, fib(1) = 1
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

// Versi loop: satu lintasan dari bawah ke atas
long long fibonacciLoop(int n) {
    long long a = 0;
    long long b = 1;
    for (int i = 2; i <= n; ++i) {
        long long berikut = a + b;
        a = b;
        b = berikut;
    }
    return b;
}

int main() {
    for (int n : {10, 20, 30}) {
        jumlahPanggilan = 0;
        long long hasil = fibonacci(n);
        std::cout << "fib(" << n << ") = " << hasil
                  << " (" << jumlahPanggilan << " kali dipanggil)\n";
    }
    std::cout << "fib(60) via loop = " << fibonacciLoop(60) << "\n";
    return 0;
}

Output yang Dihasilkan:

fib(10) = 55 (177 kali dipanggil)
fib(20) = 6765 (21891 kali dipanggil)
fib(30) = 832040 (2692537 kali dipanggil)
fib(60) via loop = 1548008755920

Angka penghitung bercerita: dari fib(10) ke fib(20) pemanggilan naik seratus kali lipat, dan fib(30) membutuhkan 2,7 juta panggilan untuk satu jawaban. Penyebabnya adalah pekerjaan ulang: fibonacci(30) menghitung fibonacci(28) dua kali, fibonacci(26) empat kali, dan seterusnya — jumlah panggilan bertumbuh sekitar dua kali lipat setiap n naik satu. Sementara itu versi loop menyelesaikan fib(60) — nilai yang jauh lebih besar — dalam satu lintasan sederhana tanpa panggilan bertingkat. Variabel global jumlahPanggilan di sini memakai konsep variabel global yang kita pelajari pada Chapter Scope dan Lifetime Variabel.

Rujukan resmi tentang fungsi yang menjadi rumah teknik ini ada di cppreference: functions . Rekursi memakai nama fungsi yang sudah diketahui; Chapter berikutnya membahas cara memegang fungsi sebagai DATA lewat function pointer.