Mekanika rekursi

Fungsi rekursif adalah fungsi yang memanggil dirinya sendiri sampai sebuah kondisi penghentian tercapai. Topik ini membedah mekanisme di balik pemanggilan tersebut, mulai dari kasus dasar, call stack, sampai pohon panggilan yang dapat dibaca langsung dari keluaran program. Setelah selesai membaca, rekursi faktorial dan jumlah deret dapat ditulis sambil mengetahui persis apa yang terjadi pada memori di setiap langkahnya.

Dua komponen wajib fungsi rekursif#

Setiap fungsi rekursif wajib memiliki dua komponen, yaitu kasus dasar (base case) dan langkah rekursif yang mendekati kasus dasar. Kasus dasar adalah kondisi ketika fungsi berhenti memanggil diri dan langsung mengembalikan nilai tanpa pemanggilan baru. Langkah rekursif adalah pemanggilan diri dengan masukan yang lebih dekat ke kasus dasar, misalnya dari n menjadi n-1. Apabila salah satu komponen ini hilang, panggilan tidak pernah berhenti dan program berakhir dengan error.

Faktorial menjadi contoh yang mudah dihitung ulang karena rumusnya memuat keduanya secara eksplisit:

Bagian kedua rumus adalah kasus dasarnya, sedangkan bagian pertama adalah langkah rekursifnya. Setiap pemanggilan mengurangi nilai n satu satuan, sehingga n pasti mencapai 1 pada suatu saat dan kasus dasar tercapai. Perhatikan arah langkahnya: masukan harus selalu bergerak menuju kasus dasar. Memanggil diri dengan masukan yang sama besar akan menghasilkan perulangan tanpa ujung, meskipun kasus dasarnya sudah ditulis dengan benar.

Call stack dan frame pemanggilan#

Setiap pemanggilan fungsi mendapat satu frame (bingkai) pada call stack, yaitu tumpukan yang menyimpan data pemanggilan yang sedang berjalan. Frame tersebut memuat variabel lokal milik panggilan itu beserta titik kembali, yakni tempat eksekusi berlanjut setelah fungsi selesai. Pada rekursi, frame baru ditumpuk di atas frame lama setiap kali fungsi memanggil diri. Kedalaman rekursi adalah banyaknya frame yang menumpuk pada satu waktu.

Frame dilepas dari stack ketika fungsi mengembalikan nilai, sehingga tumpukan menyusut dari atas ke bawah. Urutan pelepasannya selalu berlawanan dengan urutan masuknya: faktorial(1) selesai lebih dahulu, barulah faktorial(2), dan seterusnya sampai faktorial(4). Batas kedalaman ini nyata. CPython membatasi sekitar 1000 frame secara bawaan, dan melewatinya memunculkan RecursionError.

Gambar berikut menelusuri pohon panggilan faktorial(4). Panah biru menandai panggilan yang menumpuk frame baru, sedangkan panah oranye putus-putus menandai pengembalian nilai yang melepas frame kembali.

Mempercayai rekursi lewat kontrak induksi#

Menulis rekursi tidak menuntut penelusuran seluruh pohon panggilan di kepala. Kebiasaan yang melelahkan itu digantikan oleh kontrak induksi dengan dua langkah. Pertama, anggaplah panggilan rekursif di dalam fungsi sudah mengembalikan jawaban yang benar untuk masukan yang lebih kecil. Kedua, pastikan satu langkah saja benar, yaitu langkah yang menggabungkan jawaban tadi dengan pekerjaan panggilan sekarang. Sisa pohon tidak perlu dipikirkan saat menulis, karena kebenarannya mewarisi langkah yang sudah dibuktikan.

Pada faktorial, kontraknya terbaca dalam dua baris. Pertama, kasus dasar benar karena $1! = 1$. Kedua, bila faktorial(n - 1) benar mengembalikan $(n-1)!$, maka n * faktorial(n - 1) mengembalikan $n!$, sesuai rumus. Kedua poin itu menutup seluruh pohon: kebenaran faktorial(4) mewarisi kebenaran faktorial(3), dan seterusnya sampai kasus dasar.

Cara berpikir ini identik dengan pembuktian induksi pada matematika. Basisnya adalah kasus dasar, sedangkan langkah induksinya adalah satu pemanggilan fungsi. Saat menguji fungsi baru, periksa kedua bagian itu terlebih dahulu, kemudian biarkan keluaran program yang menutup keraguan sisanya.

Menelusuri rekursi lewat keluaran program#

Kontrak induksi nyaman untuk penulisan, tetapi sesekali tumpukan frame perlu dilihat langsung. Cara termurah adalah mencetak satu baris pada setiap masuk dan setiap kembali, dengan indentasi yang bertambah sesuai kedalaman. Berkas berikut melakukannya untuk faktorial(4):

def faktorial(n, kedalaman=0):
    # menghitung n! sambil mencetak jejak kedalaman rekursinya
    indentasi = "    " * kedalaman
    print(f"{indentasi}masuk  faktorial({n})")
    if n <= 1:
        # kasus dasar: 1! = 1
        print(f"{indentasi}dasar  faktorial({n}) = 1")
        return 1
    hasil = n * faktorial(n - 1, kedalaman + 1)
    print(f"{indentasi}naik   faktorial({n}) = {hasil}")
    return hasil

print("faktorial(4) =", faktorial(4))

masuk  faktorial(4)
    masuk  faktorial(3)
        masuk  faktorial(2)
            masuk  faktorial(1)
            dasar  faktorial(1) = 1
        naik   faktorial(2) = 2
    naik   faktorial(3) = 6
naik   faktorial(4) = 24
faktorial(4) = 24

Setiap baris masuk menandai frame baru yang naik ke stack, sedangkan baris dasar dan naik menandai pelepasan frame ketika nilai dikembalikan. Pola V pada indentasinya, turun sampai kasus dasar lalu naik kembali, adalah bentuk umum seluruh rekursi linier. Pencetakan seperti ini murah ditambahkan dan tidak mengubah hasil sama sekali, cukup dihapus setelah kepercayaan pada rekursinya terbentuk. Pola yang sama dipakai untuk menjumlahkan deret 1 sampai 5:

def jumlah(n, kedalaman=0):
    # menjumlahkan 1 + 2 + ... + n secara rekursif
    print('    ' * kedalaman + f'jumlah({n})')
    if n == 1:
        return 1
    return n + jumlah(n - 1, kedalaman + 1)
print('total =', jumlah(5))

jumlah(5)
    jumlah(4)
        jumlah(3)
            jumlah(2)
                jumlah(1)
total = 15

Pencetakan per panggilan berbeda di kedua contoh. faktorial mencetak dua kali per panggilan, sekali saat masuk dan sekali saat kembali, sedangkan jumlah cukup mencetak sekali saat masuk. Banyaknya baris masuk sekaligus menunjukkan kedalaman maksimum, yaitu lima pada deret dan empat pada faktorial. Baris naik juga memperlihatkan urutan pelepasan frame yang berlawanan dengan urutan masuknya. Teknik yang sama dipakai pada templat backtracking di modul ini untuk memeriksa urutan pilihan yang dibangun.

Varian Java#

Algoritma yang sama diterjemahkan ke Java tanpa perubahan logika. Kasus dasar dan langkah rekursifnya tetap, sedangkan perbedaannya ada pada tipe data dan cara menjalankannya. Tipe long dipakai karena hasil faktorial membesar cepat. Tipe int mulai meluap pada 13! karena hasilnya sudah melewati nilai maksimum 2.147.483.647 yang bisa ditampungnya. Logikanya sama persis dengan versi Python, sehingga perbedaannya murni bahasa, bukan algoritma.

public class Faktorial {
    // menghitung faktorial secara rekursif

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

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

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320

Program Java modern dijalankan langsung dari satu berkas sumber dengan perintah java Faktorial.java, tanpa tahap kompilasi manual. Setiap pemanggilan faktorial di Java juga menumpuk frame pada call stack milik JVM. Bila kedalaman melebihi kapasitasnya, Java melempar StackOverflowError, padanan dari RecursionError pada Python.

Nilai kembalian long menampung hasil hingga 20!, karena batas tipe itu sekitar 9,22 kuintiliun sedangkan 20! bernilai sekitar 2,43 kuintiliun. Perulangan pada main memanggil fungsi untuk masukan satu sampai delapan, sehingga keluarannya dapat diperiksa satu baris demi satu baris terhadap tabel faktorial yang dikenal. Bila kebutuhan perhitungan melampaui 20!, tipe long juga meluap dan kelas BigInteger menjadi pilihan berikutnya.

Kesalahan umum#

Kesalahan pertama adalah kasus dasar yang hilang. Fungsi berikut memanggil diri tanpa pernah berhenti, dan Python menghentikannya dengan RecursionError setelah batas frame terlampaui. Pemanggilan di bawah dibungkus dengan try hanya untuk menangkap pesannya agar keluaran program tetap ringkas, bukan sebagai pola untuk ditiru:

def hitung_mundur(n):
    # SALAH: tidak ada kasus dasar, panggilan tidak pernah berhenti
    return hitung_mundur(n - 1)
try:
    hitung_mundur(10)
except RecursionError:
    print("RecursionError: kedalaman panggilan melebihi batas")

RecursionError: kedalaman panggilan melebihi batas

Kesalahan kedua lebih licik, yaitu kasus dasar yang ada tetapi tidak terjangkau. Faktorial dengan kasus dasar n == 1 terdengar benar, tetapi bila dipanggil dengan n bernilai 0 atau negatif, nilai itu melompati 1 dan terus turun tanpa berhenti. Perbaikannya adalah memperlebar kasus dasar menjadi n <= 1, atau menolak masukan di luar rentang sebelum rekursi dimulai. Kedua kesalahan ini terdeteksi dengan cara yang sama, yaitu menjalankan program pada masukan terkecil terlebih dahulu. Uji cepat itu murah, dan kasus dasarnya langsung terlihat pada keluaran yang tak kunjung berhenti.

Ringkasan#

• Setiap fungsi rekursif memuat kasus dasar dan langkah rekursif yang bergerak menuju kasus dasar tersebut.
• Setiap panggilan menumpuk frame pada call stack, dan frame dilepas ketika fungsi mengembalikan nilai.
• Kepercayaan pada rekursi dibangun lewat kontrak induksi, yaitu menganggap panggilan yang lebih dalam benar lalu membuktikan satu langkah penggabungannya.
• Pencetakan berindentasi per kedalaman mengubah pohon panggilan yang abstrak menjadi keluaran yang dapat dibaca.

Referensi#

• sys — System-specific parameters and functions — Python documentation — Menetapkan dan memeriksa batas kedalaman rekursi lewat sys.setrecursionlimit() dan sys.getrecursionlimit().
• Recursion (computer science) — Wikipedia — Definisi rekursi dan contoh klasiknya pada fungsi matematika.