Recursive Methods

Sebagian masalah punya struktur yang berulang pada dirinya sendiri: faktorial 4 adalah 4 dikali faktorial 3, yang pada gilirannya adalah 3 dikali faktorial 2 — hingga berhenti di faktorial 1. Java memungkinkan method memanggil dirinya sendiri; teknik ini bernama rekursi, dan method yang melakukannya disebut recursive method. Call stack yang kita pelajari pada Chapter Membuat Method menjadi pahlawan di sini: setiap pemanggilan rekursif mendapat stack frame sendiri dengan parameternya masing-masing, sehingga penghitungan bertingkat dapat menumpuk lalu terurai teratur. Pada Chapter ini kita tulis rekursi faktorial dan fibonacci, kenali syarat wajib base case, lalu amati langsung apa yang terjadi bila syarat itu hilang.

Faktorial dan Base Case #

Setiap recursive method yang benar tersusun dari dua bagian. Pertama, base case: kondisi ketika method mengembalikan nilai langsung tanpa memanggil dirinya lagi — titik pemberhentian rekursi. Kedua, recursive case: jalur yang memecah masalah menjadi versi lebih kecil lalu memanggil method itu sendiri. Method faktorial berikut mencatat jejak masuk dan keluarnya agar kita bisa mengamati urutan penghitungan:

public class Faktorial {

    static long faktorial(int n) {
        System.out.println("masuk  : faktorial(" + n + ")");
        if (n <= 1) {
            return 1;                       // base case
        }
        long hasil = n * faktorial(n - 1);  // recursive case
        System.out.println("keluar : faktorial(" + n + ") = " + hasil);
        return hasil;
    }

    public static void main(String[] args) {
        System.out.println("4! = " + faktorial(4));
    }
}

Output yang Dihasilkan:

masuk  : faktorial(4)
masuk  : faktorial(3)
masuk  : faktorial(2)
masuk  : faktorial(1)
keluar : faktorial(2) = 2
keluar : faktorial(3) = 6
keluar : faktorial(4) = 24
4! = 24

Urutan keluarannya memperlihatkan dua fase. Empat baris masuk tercetak berurutan menurun — call stack menumpuk empat frame, satu untuk tiap nilai n dari 4 sampai 1. Lalu tiga baris keluar naik kembali — frame terurai dari yang terdalam. Alur lengkapnya:

Bedah barisnya baris demi baris:

1. Baris 6 (if (n <= 1) dan return 1;): base case — ketika n sudah mencapai 1, method mengembalikan 1 tanpa pemanggilan lanjutan. Tanpa baris ini, rantai pemanggilan tidak pernah berhenti.
2. Baris 9 (long hasil = n * faktorial(n - 1);): recursive case — method menunda pengaliannya, memanggil faktorial(n - 1), dan menunggu nilai baliknya. Setiap pemanggilan mendapat frame baru berisi salinan n yang lebih kecil (mekanisme pass by value dari Chapter sebelumnya).
3. Baris 10 (System.out.println("keluar ...")): baris ini baru tercapai setelah seluruh pemanggilan di bawahnya selesai — itulah sebabnya baris keluar tercetak berurutan naik, bukan turun.

Perkalian akhir terjadi saat frame terurai: 1 dari base case dikali 2, hasilnya 2 dikali 3, hasilnya 6 dikali 4, menghasilkan 24.

Fibonacci dan Pemanggilan Rekursif Ganda #

Rekursi tidak terbatas satu pemanggilan per jalur. Deret fibonacci mendefinisikan setiap suku sebagai jumlah dua suku sebelumnya, sehingga recursive case-nya memanggil method dua kali:

public class Fibonacci {

    static int fibonacci(int n) {
        if (n == 0) {
            return 0;      // base case pertama
        }
        if (n == 1) {
            return 1;      // base case kedua
        }
        return fibonacci(n - 1) + fibonacci(n - 2);  // dua pemanggilan rekursif
    }

    public static void main(String[] args) {
        for (int i = 0; i <= 8; i++) {
            System.out.println("fibonacci(" + i + ") = " + fibonacci(i));
        }
    }
}

Output yang Dihasilkan:

fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(2) = 1
fibonacci(3) = 2
fibonacci(4) = 3
fibonacci(5) = 5
fibonacci(6) = 8
fibonacci(7) = 13
fibonacci(8) = 21

Dua base case diperlukan karena rekursinya bercabang dua: fibonacci(2) memanggil fibonacci(1) dan fibonacci(0) — bila salah satu tidak dihentikan di base case, cabang itu akan terus turun ke angka negatif. Harga dari kejelasan ini adalah biaya: fibonacci(n) menghitung ulang submasalah yang sama berkali-kali. Jumlah pemanggilan tumbuh eksponensial — menghitung fibonacci(40) dengan bentuk murni ini menuntut lebih dari seratus juta pemanggilan, sedangkan versi iteratif dengan dua variabel cukup 40 langkah.

Base Case yang Hilang #

Apa yang terjadi bila recursive method tidak memiliki base case? Setiap pemanggilan menumpuk frame baru di call stack, dan call stack berukuran terbatas — beberapa ratus ribu frame pada thread biasa. Saat ruangnya habis, JVM melempar StackOverflowError. Program berikut menangkap error tersebut agar pesannya tercetak rapi:

public class DemoStackOverflow {

    // Rekursi tanpa base case: setiap pemanggilan menumpuk frame baru
    static int turun(int n) {
        return turun(n - 1);
    }

    public static void main(String[] args) {
        try {
            turun(1);
            System.out.println("selesai");
        } catch (StackOverflowError e) {
            System.out.println("StackOverflowError terjadi: call stack penuh");
        }
    }
}

Output yang Dihasilkan:

StackOverflowError terjadi: call stack penuh

Method turun terus memanggil turun(n - 1) tanpa kondisi berhenti, sehingga frame bertumpuk hingga batas stack terlampaui. Baris catch (StackOverflowError e) menangkap kejadian itu dan mencetak satu baris ringkas. Perhatikan bahwa yang ditangkap bertipe StackOverflowError, bukan Exception — error kehabisan stack termasuk kategori Error, keluarga masalah serius yang lazimnya tidak ditangkap; kita menangkapnya di sini semata-mata untuk memperagakan gejalanya.

Rekursi memperlihatkan betapa eratnya method dengan call stack: frame yang ditumpuknya sendiri menjadi tempat kerja sementara. Topik berikutnya menggeser sudut pandang dari bagaimana method berjalan ke siapa pemilik method — apakah method milik class itu sendiri atau milik setiap objek yang dibuat dari class tersebut. Perbedaan static versus instance method adalah materi Chapter selanjutnya.

Referensi #

• Java API: java.lang.StackOverflowError
• JLS SE25 §8.4: Method Declarations
• dev.java: Belajar Java

public class DemoStackOverflow {

    // Rekursi tanpa base case: setiap pemanggilan menumpuk frame baru
    static int turun(int n) {
        return turun(n - 1);
    }

    public static void main(String[] args) {
        try {
            turun(1);
            System.out.println("selesai");
        } catch (StackOverflowError e) {
            System.out.println("StackOverflowError terjadi: call stack penuh");
        }
    }
}

public class Faktorial {

    static long faktorial(int n) {
        System.out.println("masuk  : faktorial(" + n + ")");
        if (n <= 1) {
            return 1;                       // base case
        }
        long hasil = n * faktorial(n - 1);  // recursive case
        System.out.println("keluar : faktorial(" + n + ") = " + hasil);
        return hasil;
    }

    public static void main(String[] args) {
        System.out.println("4! = " + faktorial(4));
    }
}

public class Fibonacci {

    static int fibonacci(int n) {
        if (n == 0) {
            return 0;      // base case pertama
        }
        if (n == 1) {
            return 1;      // base case kedua
        }
        return fibonacci(n - 1) + fibonacci(n - 2);  // dua pemanggilan rekursif
    }

    public static void main(String[] args) {
        for (int i = 0; i <= 8; i++) {
            System.out.println("fibonacci(" + i + ") = " + fibonacci(i));
        }
    }
}