Beberapa persoalan terlalu dalam untuk dijelaskan dengan loop biasa: folder berisi folder berisi folder, percabangan catur beberapa langkah ke depan, semua susunan posisi ratu di papan catur. Pola berpikir untuk semuanya adalah recursion: sebuah method memanggil dirinya sendiri dengan versi masalah yang lebih kecil, sampai bertemu kasus paling sederhana yang bisa dijawab langsung. Recursion bukan trik sintaks — method rekursif menumpuk frame di call stack JVM, satu frame per panggilan yang belum selesai. Bab ini membedah mekanisme tersebut dengan jejak panggilan yang tercetak, lalu melangkah ke backtracking: rekursi yang berani mundur ketika cabang terbukti buntu, dipraktikkan pada permutasi dan puzzle N-Queens.

Base Case dan Kasus Rekursif #

Setiap method rekursif wajib punya dua bagian. Base case adalah kondisi saat jawaban dikembalikan langsung tanpa panggilan ulang — titik berhenti yang pasti tercapai. Kasus rekursif memecah masalah menjadi versi lebih kecil lalu memanggil method itu sendiri. Program berikut mencetak jejak lengkap tumpukan panggilan faktorial(5) supaya kedua bagian itu terlihat mata:

java RekursiDasar.java 
public class RekursiDasar {

    public static void main(String[] args) {
        System.out.println("=== Jejak panggilan faktorial(5) ===");
        long hasil = faktorial(5, 0);
        System.out.println("faktorial(5) = " + hasil);

        System.out.println();
        System.out.println("=== Fibonacci rekursif ===");
        for (int n = 0; n <= 10; n++) {
            System.out.printf("fib(%2d) = %4d%n", n, fib(n));
        }
    }

    // Rekursi dengan jejak: kedalaman menentukan lekukan agar tumpukan terlihat.
    static long faktorial(int n, int kedalaman) {
        System.out.println("  ".repeat(kedalaman) + "masuk faktorial(" + n + ")");
        if (n <= 1) {
            System.out.println("  ".repeat(kedalaman) + "kasus dasar: kembalikan 1");
            return 1;
        }
        long hasilNMinus1 = faktorial(n - 1, kedalaman + 1);
        long hasil = n * hasilNMinus1;
        System.out.println("  ".repeat(kedalaman) + n + " * " + hasilNMinus1
                + " = " + hasil);
        return hasil;
    }

    static long fib(int n) {
        if (n <= 1) {
            return n;    // dua kasus dasar: fib(0) dan fib(1)
        }
        return fib(n - 1) + fib(n - 2);
    }
}

Output yang Dihasilkan:

text 
=== Jejak panggilan faktorial(5) ===
masuk faktorial(5)
  masuk faktorial(4)
    masuk faktorial(3)
      masuk faktorial(2)
        masuk faktorial(1)
        kasus dasar: kembalikan 1
      2 * 1 = 2
    3 * 2 = 6
  4 * 6 = 24
5 * 24 = 120
faktorial(5) = 120

=== Fibonacci rekursif ===
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

Jejak tersebut adalah potret call stack yang hidup. Lima baris masuk faktorial(n) yang makin menjorok ke dalam memperlihatkan lima frame menumpuk — masing-masing menunggu hasil dari frame di bawahnya. Saat faktorial(1) akhirnya menyentuh base case dan mengembalikan 1, penyelesaian mengalir ke atas: 2×1 = 2, 3×2 = 6, 4×6 = 24, 5×24 = 120. Mekanisme identik terjadi pada method urutMerge di Bab Sorting — pembagian rekursif berhenti di array satu elemen karena satu elemen pasti terurut.

Disiplin base case bersifat mutlak. Lupakan base case, atau buat kasus rekursif yang tidak menyusut, maka frame menumpuk tanpa batas sampai JVM melempar StackOverflowError. Fibonacci rekursif menunjukkan jebakan halus yang berbeda: fib(n-1) + fib(n-2) menumbuhkan dua cabang per panggilan sehingga jumlah panggilan totalnya tumbuh eksponensial — fib(30) sudah memicu lebih dari satu juta panggilan. Persoalan tumpang tindih inilah yang kelak dibasmi dynamic programming.

Backtracking Memilih lalu Mundur #

Backtracking memakai rekursi untuk berjalan menyusuri ruang solusi: rangkaian keputusan bertahap. Resepnya tiga langkah — pilih satu kandidat, telusuri cabangnya lebih dalam, lalu mundur (backtrack) membatalkan pilihan agar kandidat lain bisa dicoba. Generasi permutasi adalah contoh termurni:

java Permutasi.java 
import java.util.Arrays;

public class Permutasi {

    static int[] hasil;
    static boolean[] dipakai;

    public static void main(String[] args) {
        int[] data = {1, 2, 3};
        hasil = new int[data.length];
        dipakai = new boolean[data.length];

        System.out.println("=== Permutasi {1, 2, 3} urutan leksikografis ===");
        buat(data, 0);
    }

    // Backtracking: pilih kandidat terkecil yang belum dipakai, isi posisi,
    // telusuri lebih dalam, lalu lepaskan pilihan untuk cabang berikutnya.
    static void buat(int[] data, int posisi) {
        if (posisi == data.length) {
            System.out.println(Arrays.toString(hasil));
            return;
        }
        for (int i = 0; i < data.length; i++) {
            if (!dipakai[i]) {
                dipakai[i] = true;      // pilih
                hasil[posisi] = data[i];
                buat(data, posisi + 1); // telusuri
                dipakai[i] = false;     // mundur: kembalikan pilihan
            }
        }
    }
}

Output yang Dihasilkan:

text 
=== Permutasi {1, 2, 3} urutan leksikografis ===
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

Enam permutasi tercetak terurut leksikografis — dari [1, 2, 3] sampai [3, 2, 1] — karena loop kandidat selalu mencoba nilai terkecil yang tersedia lebih dulu. Mari kita bedah intinya:

  1. Array dipakai: catatan kandidat mana yang sedang dipakai di cabang saat ini. Inilah “ingatan” yang memastikan satu nilai tidak muncul dua kali dalam satu permutasi.
  2. Baris 26 (dipakai[i] = true): keputusan dipilih, ditandai, lalu rekursi turun ke posisi berikutnya dengan satu kandidat lebih sedikit.
  3. Baris 28 (dipakai[i] = false;): baris inilah backtracking itu sendiri. Setelah seluruh cabang di bawah selesai dieksplorasi, pilihan dibatalkan sehingga loop bisa mencoba kandidat berikutnya di posisi yang sama. Hilangkan satu baris ini dan program hanya mencetak satu permutasi.

N-Queens Mundur Saat Terdesak #

Puzzle N-Queens menguji backtracking sungguhan: tempatkan 4 ratu pada papan 4×4 agar tidak ada dua ratu saling menyerang — artinya tidak berbagi baris, kolom, atau diagonal. Karena satu baris hanya boleh menampung satu ratu, satu solusi cukup direpresentasikan array posisi[baris] = kolom:

java NQueens.java 
import java.util.Arrays;

public class NQueens {

    static final int UKURAN = 4;
    static int[] posisi = new int[UKURAN];   // posisi[baris] = kolom ratu
    static int jumlahSolusi = 0;
    static long percobaan;

    public static void main(String[] args) {
        System.out.println("=== N-Queens " + UKURAN + "x" + UKURAN
                + ": semua solusi ===");
        tempatkan(0);
        System.out.println("Total solusi: " + jumlahSolusi);
        System.out.println("Total percobaan penempatan ratu: " + percobaan);
    }

    // Coba semua kolom pada satu baris; naik satu baris setelah penempatan aman.
    static void tempatkan(int baris) {
        if (baris == UKURAN) {
            jumlahSolusi++;
            cetakPapan();
            return;
        }
        for (int kolom = 0; kolom < UKURAN; kolom++) {
            percobaan++;
            if (aman(baris, kolom)) {
                posisi[baris] = kolom;    // pilih: taruh ratu
                tempatkan(baris + 1);     // telusuri baris berikutnya
                // mundur: posisi[baris] akan tertimpa pada iterasi berikutnya
            }
        }
    }

    static boolean aman(int baris, int kolom) {
        for (int b = 0; b < baris; b++) {
            if (posisi[b] == kolom) {
                return false;    // ada ratu pada kolom yang sama
            }
            if (Math.abs(posisi[b] - kolom) == baris - b) {
                return false;    // ada ratu pada diagonal yang sama
            }
        }
        return true;
    }

    static void cetakPapan() {
        System.out.println("Solusi " + jumlahSolusi + ": kolom per baris = "
                + Arrays.toString(posisi));
        for (int baris = 0; baris < UKURAN; baris++) {
            StringBuilder sb = new StringBuilder("  ");
            for (int kolom = 0; kolom < UKURAN; kolom++) {
                sb.append(kolom == posisi[baris] ? "Q " : ". ");
            }
            System.out.println(sb);
        }
        System.out.println();
    }
}

Output yang Dihasilkan:

text 
=== N-Queens 4x4: semua solusi ===
Solusi 1: kolom per baris = [1, 3, 0, 2]
  . Q . . 
  . . . Q 
  Q . . . 
  . . Q . 

Solusi 2: kolom per baris = [2, 0, 3, 1]
  . . Q . 
  Q . . . 
  . . . Q 
  . Q . . 

Total solusi: 2
Total percobaan penempatan ratu: 60

Program menemukan tepat 2 solusi — papan pertama dengan kolom per baris [1, 3, 0, 2], papan kedua [2, 0, 3, 1] yang merupakan cerminan pertama — setelah 60 percobaan penempatan. Bedah proses berpikirnya:

  1. Baris 25-29 (base case): ketika baris == UKURAN, keempat ratu sudah duduk aman — solusi dicatat, lalu return membuat alur mundur satu tingkat untuk mencari solusi lain di cabang berbeda.
  2. Baris 30-38 (pilih dan telusuri): loop mencoba kolom 0 sampai 3 pada baris saat ini. Hanya penempatan yang lolos pemeriksaan aman yang diturunkan ke baris berikutnya; sisanya langsung dilewati tanpa rekursi.
  3. Baris 41-50 (aman): cukup memeriksa baris-baris di atas — kolom sama tertangkap posisi[b] == kolom, diagonal sama tertangkap selisih kolom yang sama dengan selisih baris. Pemeriksaan murah inilah yang memangkas 4⁴ = 256 kemungkinan menjadi 60 percobaan.
  4. Mundur implisit: berbeda dari permutasi yang memakai array dipakai, penempatan ratu dibatalkan cukup dengan menimpa posisi[baris] pada iterasi kolom berikutnya — struktur masalahnya memungkinkan pembatalan tanpa pembersihan eksplisit.

Backtracking kuat karena memangkas cabang yang terbukti buntu. Namun kadang persoalan punya struktur yang lebih kaya dari sekadar bisa dipangkas: serangkaian pilihan yang tampak paling menguntungkan saat ini justru menghasilkan solusi global. Bab berikutnya membahas kapan strategi serakah semacam itu sah — dan kapan ia runtuh.

Referensi #

Berkas Sumber

Berkas pendukung halaman ini dapat diunduh dan dijalankan langsung sesuai penjelasan di atas.

NQueens.java

Unduh berkas
java 
import java.util.Arrays;

public class NQueens {

    static final int UKURAN = 4;
    static int[] posisi = new int[UKURAN];   // posisi[baris] = kolom ratu
    static int jumlahSolusi = 0;
    static long percobaan;

    public static void main(String[] args) {
        System.out.println("=== N-Queens " + UKURAN + "x" + UKURAN
                + ": semua solusi ===");
        tempatkan(0);
        System.out.println("Total solusi: " + jumlahSolusi);
        System.out.println("Total percobaan penempatan ratu: " + percobaan);
    }

    // Coba semua kolom pada satu baris; naik satu baris setelah penempatan aman.
    static void tempatkan(int baris) {
        if (baris == UKURAN) {
            jumlahSolusi++;
            cetakPapan();
            return;
        }
        for (int kolom = 0; kolom < UKURAN; kolom++) {
            percobaan++;
            if (aman(baris, kolom)) {
                posisi[baris] = kolom;    // pilih: taruh ratu
                tempatkan(baris + 1);     // telusuri baris berikutnya
                // mundur: posisi[baris] akan tertimpa pada iterasi berikutnya
            }
        }
    }

    static boolean aman(int baris, int kolom) {
        for (int b = 0; b < baris; b++) {
            if (posisi[b] == kolom) {
                return false;    // ada ratu pada kolom yang sama
            }
            if (Math.abs(posisi[b] - kolom) == baris - b) {
                return false;    // ada ratu pada diagonal yang sama
            }
        }
        return true;
    }

    static void cetakPapan() {
        System.out.println("Solusi " + jumlahSolusi + ": kolom per baris = "
                + Arrays.toString(posisi));
        for (int baris = 0; baris < UKURAN; baris++) {
            StringBuilder sb = new StringBuilder("  ");
            for (int kolom = 0; kolom < UKURAN; kolom++) {
                sb.append(kolom == posisi[baris] ? "Q " : ". ");
            }
            System.out.println(sb);
        }
        System.out.println();
    }
}

Permutasi.java

Unduh berkas
java 
import java.util.Arrays;

public class Permutasi {

    static int[] hasil;
    static boolean[] dipakai;

    public static void main(String[] args) {
        int[] data = {1, 2, 3};
        hasil = new int[data.length];
        dipakai = new boolean[data.length];

        System.out.println("=== Permutasi {1, 2, 3} urutan leksikografis ===");
        buat(data, 0);
    }

    // Backtracking: pilih kandidat terkecil yang belum dipakai, isi posisi,
    // telusuri lebih dalam, lalu lepaskan pilihan untuk cabang berikutnya.
    static void buat(int[] data, int posisi) {
        if (posisi == data.length) {
            System.out.println(Arrays.toString(hasil));
            return;
        }
        for (int i = 0; i < data.length; i++) {
            if (!dipakai[i]) {
                dipakai[i] = true;      // pilih
                hasil[posisi] = data[i];
                buat(data, posisi + 1); // telusuri
                dipakai[i] = false;     // mundur: kembalikan pilihan
            }
        }
    }
}

RekursiDasar.java

Unduh berkas
java 
public class RekursiDasar {

    public static void main(String[] args) {
        System.out.println("=== Jejak panggilan faktorial(5) ===");
        long hasil = faktorial(5, 0);
        System.out.println("faktorial(5) = " + hasil);

        System.out.println();
        System.out.println("=== Fibonacci rekursif ===");
        for (int n = 0; n <= 10; n++) {
            System.out.printf("fib(%2d) = %4d%n", n, fib(n));
        }
    }

    // Rekursi dengan jejak: kedalaman menentukan lekukan agar tumpukan terlihat.
    static long faktorial(int n, int kedalaman) {
        System.out.println("  ".repeat(kedalaman) + "masuk faktorial(" + n + ")");
        if (n <= 1) {
            System.out.println("  ".repeat(kedalaman) + "kasus dasar: kembalikan 1");
            return 1;
        }
        long hasilNMinus1 = faktorial(n - 1, kedalaman + 1);
        long hasil = n * hasilNMinus1;
        System.out.println("  ".repeat(kedalaman) + n + " * " + hasilNMinus1
                + " = " + hasil);
        return hasil;
    }

    static long fib(int n) {
        if (n <= 1) {
            return n;    // dua kasus dasar: fib(0) dan fib(1)
        }
        return fib(n - 1) + fib(n - 2);
    }
}