Recursion adalah teknik pemecahan masalah di mana sebuah function memanggil dirinya sendiri dengan input yang lebih kecil. Backtracking memperluas recursion dengan mencoba berbagai pilihan secara bertahap dan membatalkan pilihan yang tidak mengarah ke solusi. Pada chapter ini kita akan mempelajari dua konsep ini melalui implementasi factorial, Fibonacci, N-Queens, permutasi, dan subset sum di Kotlin. Pembaca akan melihat mengapa base case sangat krusial untuk menghentikan rekursi, dan bagaimana pola “coba–mundur” membuat backtracking mampu menjelajahi ruang solusi tanpa harus menyimpan semua kemungkinan sekaligus.

Anatomi Recursion #

Setiap function rekursif memiliki dua bagian wajib:

  1. Base case: kondisi yang menghentikan rekursi dan langsung mengembalikan nilai.
  2. Recursive case: pemanggilan diri sendiri dengan input yang lebih dekat ke base case.
kotlin Anatomi recursion 
fun factorial(n: Int): Long {
    if (n <= 1) return 1            // base case
    return n * factorial(n - 1)     // recursive case
}

Tanpa base case, rekursi berjalan tanpa henti hingga memori call stack habis dan program berhenti dengan StackOverflowError.

Risiko Stack Overflow #

Setiap pemanggilan function menambah satu frame ke call stack. Bila kedalaman rekursi terlalu besar (misalnya factorial(100_000)), stack habis sebelum base case tercapai. Kotlin menyediakan modifier tailrec yang memungkinkan compiler mengubah recursion menjadi loop iteratif bila recursive call adalah operasi terakhir (tail call).

kotlin Tail recursion 
tailrec fun factorialTail(n: Int, acc: Long = 1): Long {
    if (n <= 1) return acc
    return factorialTail(n - 1, acc * n)
}

Akumulator acc membawa hasil perhitungan sehingga pemanggilan rekursif menjadi tail call.

Backtracking: Coba, Mundur, Lanjut #

Backtracking adalah pola rekursi yang mengeksplorasi kandidat solusi secara sistematis. Saat sebuah pilihan tidak menghasilkan solusi valid, algoritma membatalkan pilihan tersebut (undo) dan mencoba alternatif lain. Dua langkah kunci adalah menandai pilihan dan membatalkan tanda setelah rekursi selesai.

Implementasi Recursion dan Backtracking #

kotlin 
// Demo Recursion dan Backtracking.

// === Recursion: factorial ===
fun factorial(n: Int): Long {
    require(n >= 0) { "n harus >= 0" }
    if (n <= 1) return 1
    return n * factorial(n - 1)
}

// === Recursion: Fibonacci ===
fun fibRec(n: Int): Int {
    if (n <= 1) return n
    return fibRec(n - 1) + fibRec(n - 2)
}

// === Recursion dengan base case yang salah (demonstrasi stack overflow) ===
// Tidak dipanggil di main untuk menghindari crash
fun infiniteRecursion(n: Int): Int {
    return infiniteRecursion(n + 1)
}

// === Backtracking: N-Queens ===
// Tempatkan N ratu di papan NxN tanpa saling serang
fun solveNQueens(n: Int): List<List<Int>> {
    val solutions = mutableListOf<List<Int>>()
    val board = IntArray(n) { -1 }  // board[row] = col

    fun aman(row: Int, col: Int): Boolean {
        for (r in 0 until row) {
            val c = board[r]
            if (c == col) return false  // kolom sama
            if (kotlin.math.abs(r - row) == kotlin.math.abs(c - col)) return false  // diagonal
        }
        return true
    }

    fun backtrack(row: Int) {
        if (row == n) {
            solutions.add(board.toList())
            return
        }
        for (col in 0 until n) {
            if (aman(row, col)) {
                board[row] = col
                backtrack(row + 1)
                board[row] = -1  // undo (backtrack)
            }
        }
    }

    backtrack(0)
    return solutions
}

// === Backtracking: permutasi ===
fun permutations(arr: IntArray): List<List<Int>> {
    val result = mutableListOf<List<Int>>()
    val used = BooleanArray(arr.size)
    val current = mutableListOf<Int>()

    fun backtrack() {
        if (current.size == arr.size) {
            result.add(current.toList())
            return
        }
        for (i in arr.indices) {
            if (!used[i]) {
                used[i] = true
                current.add(arr[i])
                backtrack()
                current.removeAt(current.lastIndex)
                used[i] = false
            }
        }
    }

    backtrack()
    return result
}

// === Backtracking: subset sum ===
fun subsetSum(arr: IntArray, target: Int): List<List<Int>> {
    val result = mutableListOf<List<Int>>()
    val current = mutableListOf<Int>()

    fun backtrack(idx: Int, sisa: Int) {
        if (sisa == 0) {
            result.add(current.toList())
            return
        }
        if (sisa < 0 || idx >= arr.size) return
        for (i in idx until arr.size) {
            current.add(arr[i])
            backtrack(i + 1, sisa - arr[i])
            current.removeAt(current.lastIndex)
        }
    }

    backtrack(0, target)
    return result
}

fun main() {
    println("=== Demo Recursion dan Backtracking ===")

    println("--- Recursion: factorial ---")
    for (n in 0..10) print("$n! = ${factorial(n)}  ")
    println()

    println()
    println("--- Recursion: Fibonacci ---")
    for (n in 0..10) print("fib($n)=${fibRec(n)}  ")
    println()

    println()
    println("--- Backtracking: N-Queens ---")
    for (n in 1..6) {
        val sol = solveNQueens(n)
        println("N=$n: ${sol.size} solusi")
    }

    println()
    println("--- Contoh solusi N-Queens 4x4 ---")
    val sol4 = solveNQueens(4)
    sol4.first().forEachIndexed { row, col ->
        val line = ".".repeat(col) + "Q" + ".".repeat(3 - col)
        println("  $line")
    }

    println()
    println("--- Backtracking: permutasi ---")
    val perms = permutations(intArrayOf(1, 2, 3))
    println("Permutasi [1,2,3]: ${perms.size} hasil")
    perms.forEach { println("  $it") }

    println()
    println("--- Backtracking: subset sum ---")
    val nums = intArrayOf(3, 5, 7, 9, 11)
    val target = 16
    val subsets = subsetSum(nums, target)
    println("Array: ${nums.toList()}, target: $target")
    println("Subset yang menjumlah $target: ${subsets.size} buah")
    subsets.forEach { println("  $it") }
}

Output yang Dihasilkan:

text 
=== Demo Recursion dan Backtracking ===
--- Recursion: factorial ---
0! = 1  1! = 1  2! = 2  3! = 6  4! = 24  5! = 120  6! = 720  7! = 5040  8! = 40320  9! = 362880  10! = 3628800  

--- Recursion: Fibonacci ---
fib(0)=0  fib(1)=1  fib(2)=1  fib(3)=2  fib(4)=3  fib(5)=5  fib(6)=8  fib(7)=13  fib(8)=21  fib(9)=34  fib(10)=55  

--- Backtracking: N-Queens ---
N=1: 1 solusi
N=2: 0 solusi
N=3: 0 solusi
N=4: 2 solusi
N=5: 10 solusi
N=6: 4 solusi

--- Contoh solusi N-Queens 4x4 ---
  .Q..
  ...Q
  Q...
  ..Q.

--- Backtracking: permutasi ---
Permutasi [1,2,3]: 6 hasil
  [1, 2, 3]
  [1, 3, 2]
  [2, 1, 3]
  [2, 3, 1]
  [3, 1, 2]
  [3, 2, 1]

--- Backtracking: subset sum ---
Array: [3, 5, 7, 9, 11], target: 16
Subset yang menjumlah 16: 2 buah
  [5, 11]
  [7, 9]

Bedah Kode Baris-per-Baris #

Mari kita amati bagian kunci:

  1. factorial (baris 4-8): Base case n <= 1 mengembalikan 1 untuk menghentikan rekursi. Recursive case n * factorial(n - 1) memanggil diri sendiri dengan n berkurang satu. Function ini tidak tail-recursif karena operasi perkalian terjadi setelah pemanggilan rekursif kembali.
  2. fibRec (baris 11-14): Dua base case (n == 0 dan n == 1) menutup kedua cabang dasar deret Fibonacci. Recursive case menjumlahkan dua pemanggilan rekursif. Tanpa memoization, kompleksitasnya O(2ⁿ) karena pohon pemanggilan tumbuh eksponensial.
  3. solveNQueens (baris 24-53): Array board menyimpan posisi kolom ratu pada setiap baris. Local function aman(row, col) memeriksa tidak ada ratu lain di kolom yang sama atau di diagonal yang sama. Local function backtrack(row) mencoba setiap kolom untuk baris saat ini; bila aman, ratu ditempatkan, rekursi ke baris berikutnya, lalu board[row] = -1 membatalkan penempatan agar kolom lain dapat dicoba.
  4. permutations (baris 56-79): Array used melacak elemen yang sudah dipakai pada cabang saat ini. Saat sebuah elemen dipilih, used[i] = true dan elemen dimasukkan ke current. Setelah rekursi selesai, used[i] = false dan elemen dikeluarkan dari current agar dapat dipilih kembali di cabang lain.
  5. subsetSum (baris 82-101): Parameter idx mencegah pengulangan kombinasi yang sama dengan urutan berbeda. Parameter sisa melacak sisa target yang harus dicapai. Base case sisa == 0 menandakan kombinasi valid ditemukan; sisa < 0 atau idx >= arr.size menghentikan cabang yang tidak produktif.

Kapan Memakai Backtracking #

Backtracking cocok untuk masalah dengan ruang solusi besar tetapi dapat dipangkas secara sistematis, seperti puzzle Sudoku, kombinasi password, dan penjadwalan. Bila setiap pilihan menghasilkan banyak cabang dan solusi parsial dapat dieliminasi awal, backtracking lebih efisien daripada brute force murni. Untuk masalah dengan subproblem yang tumpang tindih (misalnya Fibonacci naif), dynamic programming memberi kompleksitas lebih baik.

Penutup #

Recursion adalah cara alami untuk mengekspresikan masalah yang memiliki struktur berulang, sedangkan backtracking memperluasnya dengan kemampuan mencoba dan membatalkan pilihan. Pemahaman kedua pola ini menjadi fondasi untuk algoritma lanjutan seperti greedy dan dynamic programming yang akan dibahas pada chapter berikutnya.

Referensi #

Referensi Lanjutan #