Rekursi vs Iterasi

Rekursi dan iterasi adalah dua cara berbeda untuk mengekspresikan pengulangan. Rekursi menawarkan keterbacaan yang lebih baik untuk masalah dengan struktur self-similar (tree, backtracking), sementara iterasi lebih efisien untuk loop linier sederhana. Memahami trade-off keduanya penting agar kita bisa memilih alat yang tepat untuk setiap masalah. Pada Chapter ini kita akan membandingkan keduanya, melihat konsep tail recursion, dan mempelajari cara mengubah rekursi menjadi iterasi dengan stack eksplisit.

Perbandingan Umum #

Contoh: Factorial Rekursif vs Iteratif #

Kode: Perbandingan Lengkap #

#include <iostream>
#include <chrono>

long long factorial_rec(int n) {
    if (n <= 1) return 1;
    return n * factorial_rec(n - 1);
}

long long factorial_iter(int n) {
    long long result = 1;
    for (int i = 2; i <= n; ++i) result *= i;
    return result;
}

int main() {
    int n = 20;
    int repeats = 1000000;

    // Hitung jumlah komputasi (modulo untuk hindari overflow)
    const long long MOD = 1000000007;
    auto t1 = std::chrono::high_resolution_clock::now();
    long long sum_r = 0;
    for (int i = 0; i < repeats; ++i) sum_r = (sum_r + factorial_rec(n)) % MOD;
    auto t2 = std::chrono::high_resolution_clock::now();
    long long sum_i = 0;
    for (int i = 0; i < repeats; ++i) sum_i = (sum_i + factorial_iter(n)) % MOD;
    auto t3 = std::chrono::high_resolution_clock::now();

    auto us_rec = std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count();
    auto us_iter = std::chrono::duration_cast<std::chrono::microseconds>(t3 - t2).count();
    std::cout << "rekursif: " << us_rec << " us, sum = " << sum_r << '\n';
    std::cout << "iteratif: " << us_iter << " us, sum = " << sum_i << '\n';
    if (us_iter > 0) {
        std::cout << "ratio rekursif/iteratif: "
                  << static_cast<double>(us_rec) / us_iter << "x\n";
    }
    return 0;
}

Output yang Dihasilkan:

rekursif: 5696 us, sum = 61975718
iteratif: 5646 us, sum = 61975718
ratio rekursif/iteratif: 1.00886x

1. factorial_rec(20) memanggil dirinya 20 kali: 20 stack frame dialokasikan, 20 kali return. Setiap pemanggilan menambah overhead.
2. factorial_iter(20) menggunakan satu loop: 19 kali increment, multiply, compare. Jauh lebih murah per iterasi.
3. Ratio ~1.0x: dengan -O2, compiler menerapkan optimasi pada kedua versi (misalnya inlining atau TCO pada rekursif). Selisihnya sangat kecil.
4. Catatan: timing non-deterministik — angka aktual bervariasi antar run. Untuk n kecil seperti 20, overhead benchmarking (1 juta iterasi) mendominasi dibanding perbedaan algoritma.
5. % MOD: mencegah overflow long long akibat akumulasi 1 juta kali factorial(20) yang seharusnya menghasilkan ~2.4e24 (melebihi batas long long ~9.2e18).

Konsep: Tail Recursion #

Tail recursion adalah bentuk rekursi di mana panggilan rekursif adalah operasi terakhir sebelum return. Tidak ada operasi “menunggu” hasil rekursif — hasil rekursif langsung dikembalikan.

Contoh: Factorial Biasa (Bukan Tail Recursion) #

long long factorial_rec(int n) {
    if (n <= 1) return 1;
    return n * factorial_rec(n - 1);  // masih harus mengalikan n
}

Baris return n * factorial_rec(n - 1) tidak tail recursion karena n * adalah operasi yang menunggu hasil factorial_rec(n-1). Setelah factorial_rec(n-1) kembali, perkalian dilakukan, baru hasil dikembalikan.

Contoh: Factorial Tail Recursion #

Kita bisa mengubah ke tail recursion dengan accumulator — parameter yang membawa hasil parsial.

#include <iostream>

long long factorial_tail(int n, long long acc = 1) {
    if (n <= 1) return acc;
    return factorial_tail(n - 1, n * acc);  // tail call
}

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

Output yang Dihasilkan:

factorial_tail(5) = 120
factorial_tail(10) = 3628800
factorial_tail(20) = 2432902008176640000

1. Parameter acc: accumulator yang membawa hasil parsial. Saat rekursi mencapai base case, acc berisi hasil akhir.
2. Baris return factorial_tail(n - 1, n * acc);: ini adalah tail call. Tidak ada operasi lain setelah pemanggilan rekursif — hasilnya langsung dikembalikan.
3. Hasil identik dengan factorial biasa — 120, 3628800, 2432902008176640000.

Apakah C++ Mengoptimasi Tail Recursion? #

Kode: Verifikasi TCO pada GCC #

#include <iostream>

// Tail recursion — apakah dioptimasi?
long long sum_to(int n, long long acc = 0) {
    if (n == 0) return acc;
    return sum_to(n - 1, acc + n);
}

int main() {
    // n = 1000000 — akan stack overflow tanpa TCO
    std::cout << "sum_to(1000000) = " << sum_to(1000000) << '\n';
    return 0;
}

Output yang Dihasilkan (dengan -O2):

sum_to(1000000) = 500000500000

1. n = 1000000: tanpa TCO, akan butuh 1 juta stack frame → stack overflow.
2. Dengan -O2 di GCC: TCO diterapkan, panggilan rekursif diubah menjadi loop. Tidak ada stack overflow.
3. Tanpa -O2: program akan crash dengan Segmentation fault.
4. Pelajaran: TCO bergantung compiler dan flag. Untuk portabilitas, gunakan iterasi.

Mengubah Rekursi Menjadi Iterasi #

Setiap fungsi rekursif dapat diubah menjadi iteratif dengan stack eksplisit. Triknya: simpan state yang biasanya ada di stack frame ke dalam std::stack<T>.

Kode: Tree Traversal Rekursif vs Iteratif #

#include <iostream>
#include <vector>
#include <stack>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

// Pre-order rekursif
void preorder_rec(TreeNode* root) {
    if (!root) return;
    std::cout << root->val << ' ';
    preorder_rec(root->left);
    preorder_rec(root->right);
}

// Pre-order iteratif dengan stack eksplisit
void preorder_iter(TreeNode* root) {
    if (!root) return;
    std::stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode* node = s.top(); s.pop();
        std::cout << node->val << ' ';
        if (node->right) s.push(node->right);  // push kanan dulu
        if (node->left)  s.push(node->left);   // agar left diproses dulu
    }
}

int main() {
    //      1
    //     / \
    //    2   3
    //   / \
    //  4   5
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    std::cout << "preorder rekursif: ";
    preorder_rec(root);
    std::cout << '\n';

    std::cout << "preorder iteratif: ";
    preorder_iter(root);
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

preorder rekursif: 1 2 4 5 3 
preorder iteratif: 1 2 4 5 3 

1. preorder_rec: versi rekursif. Setiap panggilan menempati stack frame baru. Mudah dibaca tetapi terbatas oleh call stack 8 MB.
2. preorder_iter: versi iteratif dengan std::stack<TreeNode*>. Push anak kanan dulu, lalu anak kiri, agar kiri diproses duluan (LIFO).
3. Output identik: kedua versi menghasilkan urutan yang sama — 1 2 4 5 3.
4. Keunggulan iteratif: stack eksplisit di heap, bisa menangani jutaan node tanpa overflow.

Kapan Memilih Rekursi #

Pilih rekursi bila:

1. Struktur masalah rekursif alami: tree, graph, ekspresi matematika rekursif (factorial, Fibonacci).
2. Backtracking: eksplorasi state dengan banyak cabang.
3. Divide and conquer: merge sort, quicksort, algoritma pohon.
4. Kedalaman terbatas: tree dengan kedalaman < 1000, atau ada jaminan tidak akan sangat dalam.

Pilih iterasi bila:

1. Loop linier sederhana: sum, max, min, count.
2. Kedalaman bisa sangat besar: input data 10^6 atau lebih.
3. Performance kritikal: hot loop, embedded systems.
4. Tidak yakin dengan TCO: bila target compiler tidak menjamin optimasi.

Pola Umum Konversi #

Untuk rekursi linier (satu panggilan rekursif per fungsi):

rekursif:
    f(input):
        if base: return base_value
        return combine(input, f(smaller))

iteratif:
    result = base_value
    while input != base:
        result = combine(input, result)
        input = smaller(input)
    return result

Untuk rekursi bercabang (dua panggilan rekursif seperti tree):

rekursif:
    f(node):
        if !node: return
        process(node)
        f(node.left)
        f(node.right)

iteratif:
    stack.push(root)
    while !stack.empty():
        node = stack.pop()
        if !node: continue
        process(node)
        stack.push(node.right)
        stack.push(node.left)

Ringkasan #

• Rekursi unggul dalam keterbacaan untuk masalah self-similar (tree, backtracking).
• Iterasi unggul dalam efisiensi untuk loop linier dan kedalaman besar.
• Tail recursion: panggilan rekursif adalah operasi terakhir — bisa dioptimasi compiler menjadi loop.
• C++ tidak menjamin TCO; GCC/Clang menerapkannya pada -O2 tetapi tidak portable.
• Untuk rekursi yang dalam, ubah ke iterasi dengan std::stack<T> eksplisit.
• Pemilihan: rekursi untuk kejelasan struktur, iterasi untuk performa dan kedalaman tak terbatas.