Rekursi

Sebuah metode boleh memanggil dirinya sendiri, dan teknik itu disebut rekursi. Setiap masalah yang bentuknya berulang pada skala lebih kecil cocok didekati dengan cara ini, dari faktorial sampai penelusuran struktur bersarang. Topik ini membahas dua syarat wajib rekursi, menelusuri apa yang terjadi pada stack saat panggilan menumpuk, lalu mengukur harga rekursi naif pada Fibonacci dan menurunkannya dengan memoisasi.

Kasus dasar dan langkah rekursif#

Metode rekursif berdiri di atas dua bagian. Kasus dasar adalah kondisi yang dijawab langsung tanpa memanggil diri lagi, sedangkan langkah rekursif menyelesaikan sebagian masalah lalu menyerahkan sisanya kepada panggilan yang lebih kecil. Tanpa salah satu dari keduanya, rekursi tidak pernah selesai.

Definisi faktorial di atas adalah rekursi dalam bentuknya yang paling murni, dan metode Java menerjemahkan kedua baris itu persis. Kondisi n <= 1 menjadi kasus dasar yang mencakup 0! dan 1!, sedangkan perkalian n * faktorial(n - 1) menjadi langkah rekursif yang selalu mendekati kasus dasar.

public class FaktorialRekursif {

    static long faktorial(int n) {
        if (n <= 1) {                    // kasus dasar
            return 1;
        }
        return n * faktorial(n - 1);     // langkah rekursif
    }

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

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800

Perulangan pada main hanya bertugas mencetak, sedangkan seluruh penghitungan terjadi berlapis di dalam faktorial. Karena setiap panggilan memanggil dengan n - 1, jumlah panggilan bertumbuh linier terhadap n dan berhenti tepat saat kasus dasar tercapai.

Menelusuri tumpukan panggilan#

Setiap panggilan metode, rekursif atau bukan, mendapat stack frame sendiri yang berisi parameter miliknya. Pada rekursi, frame-frame itu menumpuk hingga kasus dasar tercapai, lalu hasilnya kembali naik satu per satu saat setiap frame selesai. Menambahkan cetakan berinden pada metode faktorial membuat proses itu terlihat.

public class TelusuriFaktorial {

    static long faktorial(int n, int kedalaman) {
        String inden = "  ".repeat(kedalaman);
        System.out.println(inden + "masuk faktorial(" + n + ")");
        if (n <= 1) {
            System.out.println(inden + "kasus dasar, kembalikan 1");
            return 1;
        }
        long hasil = n * faktorial(n - 1, kedalaman + 1);
        System.out.println(inden + "faktorial(" + n + ") mengembalikan " + hasil);
        return hasil;
    }

    public static void main(String[] args) {
        long hasil = faktorial(4, 0);
        System.out.println("Hasil akhir: " + hasil);
    }
}

masuk faktorial(4)
  masuk faktorial(3)
    masuk faktorial(2)
      masuk faktorial(1)
      kasus dasar, kembalikan 1
    faktorial(2) mengembalikan 2
  faktorial(3) mengembalikan 6
faktorial(4) mengembalikan 24
Hasil akhir: 24

Empat frame menumpuk selama pemanggilan, satu untuk setiap nilai n, dan setiap frame memegang n miliknya sendiri. Puncaknya adalah kasus dasar yang mengembalikan 1 tanpa memanggil lagi, lalu arah keluarannya berbalik: setiap frame mengalikan nilai miliknya dengan hasil yang datang dari bawah. Kedalaman tumpukan setara dengan n, sehingga faktorial 1000 menumpuk seribu frame dan tetap lolos, sedangkan rekursi yang tidak pernah berhenti terus menumpuk sampai stack habis.

Fibonacci dan subproblem yang berulang#

Deret Fibonacci mendefinisikan $f(0) = 0$, $f(1) = 1$, lalu $f(n) = f(n-1) + f(n-2)$ untuk nilai yang lebih besar. Terjemahan langsungnya ke metode rekursif terlihat wajar, tetapi definisi ini memanggil diri dua kali, dan itulah sumber masalahnya.

Pohon panggilan fibonacci(4) di atas sudah menunjukkan pengulangan: fibonacci(2) dihitung dua kali dan fibonacci(1) tiga kali. Pengulangan berlipat cepat karena setiap simpul melahirkan dua cabang, sehingga jumlah panggilan bertumbuh mendekati $O(2^n)$. Untuk nilai yang cukup besar, versi naif tidak lagi praktis meskipun kodenya benar dan hasilnya tepat.

Memoisasi#

Memoisasi menyimpan hasil setiap perhitungan ke tempat penampung, lalu mengembalikan hasil simpanan itu bila subproblem yang sama diminta lagi. Dengan satu array sebagai cache, setiap nilai Fibonacci cukup dihitung satu kali untuk seluruh pemanggilan.

public class FibonacciDuaCara {

    static int panggilanNaif;

    static int fibonacciNaif(int n) {
        panggilanNaif++;
        if (n <= 1) {
            return n;
        }
        return fibonacciNaif(n - 1) + fibonacciNaif(n - 2);
    }

    static int panggilanMemo;

    static int fibonacciMemo(int n, int[] cache) {
        panggilanMemo++;
        if (n <= 1) {
            return n;
        }
        if (cache[n] != 0) {
            return cache[n];
        }
        cache[n] = fibonacciMemo(n - 1, cache) + fibonacciMemo(n - 2, cache);
        return cache[n];
    }

    public static void main(String[] args) {
        System.out.println("fibonacciNaif(20) = " + fibonacciNaif(20)
                + ", jumlah panggilan: " + panggilanNaif);
        int[] cache = new int[21];
        System.out.println("fibonacciMemo(20) = " + fibonacciMemo(20, cache)
                + ", jumlah panggilan: " + panggilanMemo);
    }
}

fibonacciNaif(20) = 6765, jumlah panggilan: 21891
fibonacciMemo(20) = 6765, jumlah panggilan: 39

Kedua metode mengembalikan nilai yang sama, tetapi jumlah panggilannya berjauhan. Versi naif melakukan 21891 pemanggilan untuk nilai 20, sedangkan versi ber-cache hanya 39. Selisih itu membesar sangat cepat seiring n, karena biaya versi naif bertumbuh eksponensial sedangkan versi ber-cache bertumbuh linier dengan sedikit memori tambahan untuk array cache-nya.

Kapan rekursi dipilih#

Rekursi paling pas untuk masalah yang bentuknya memang bersarang: menelusuri folder di dalam folder, membaca dokumen JSON yang elemennya berisi elemen lain, atau memecah data menjadi dua bagian berulang kali. Untuk akumulasi lurus seperti penjumlahan atau pencarian nilai terbesar, perulangan biasa lebih ringan karena tidak menumpuk frame di stack.

Java tidak memangkas panggilan rekursif yang berada di posisi terakhir seperti sebagian bahasa lain, sehingga kedalaman rekursi selalu memakan stack sungguhan. Bila kedalaman yang dibutuhkan sangat besar atau tidak terbatas, ubah ke bentuk perulangan dan simpan pekerjaan yang belum selesai pada struktur data sendiri, misalnya stack atau queue yang dikelola program.

Kesalahan umum#

• Menulis langkah yang menjauh dari kasus dasar, misalnya faktorial(n + 1). Panggilan tidak pernah berhenti dan berakhir dengan StackOverflowError.
• Menghitung Fibonacci naif untuk nilai yang besar. Versi tanpa cache mulai terasa lambat di kisaran n 40, sementara versi ber-cache selesai tanpa terasa.
• Lupa return pada langkah rekursif. Metode bertipe kembalian wajib mengembalikan nilai di setiap jalurnya, termasuk jalur yang memanggil diri.
• Menyimpan cache di field static yang dipakai lintas masalah. Sisa perhitungan masalah lama bisa terbaca sebagai hasil untuk masalah yang lain.

Ringkasan#

• Rekursi menuntut kasus dasar dan langkah rekursif yang selalu mendekati kasus dasar itu.
• Setiap panggilan mendapat frame sendiri di stack, sehingga kedalaman rekursi memakan stack sungguhan.
• Fibonacci naif mengulang subproblem secara eksponensial, sedangkan memoisasi menurunkannya menjadi linier dengan satu array cache.
• Rekursi dipilih untuk struktur bersarang, sedangkan perulangan lebih pas untuk akumulasi lurus.

Referensi#

• StackOverflowError — Oracle — dokumentasi error yang muncul saat stack untuk panggilan metode habis.
• Recursion (computer science) — Wikipedia — ringkasan konsep rekursi, kasus dasar, dan contoh klasiknya.