tailrec Functions

Rekursi seringkali menulis algoritma tertentu secara natural — misalnya faktorial atau deret Fibonacci. Sayangnya, rekursi mendalam dapat menghabiskan call stack dan memicu StackOverflowError. Kotlin menyediakan keyword tailrec yang memberi tahu kompilator untuk menulis ulang rekursi menjadi loop iteratif. Pada chapter ini kita akan melihat syarat dan manfaat tailrec.

Bentuk Rekursi Tail #

Agar kompilator dapat menulis ulang, function harus dalam bentuk tail recursion — pemanggilan rekursif harus menjadi operasi terakhir yang dieksekusi sebelum return. Akumulator dipakai agar hasil dihitung di sepanjang rekursi, bukan di tahap akhir.

tailrec fun faktorial(n: Long, acc: Long = 1): Long {
    return if (n <= 1) acc else faktorial(n - 1, acc * n)
}

tailrec fun fib(n: Int, a: Long = 0, b: Long = 1): Long {
    return if (n == 0) a else fib(n - 1, b, a + b)
}

tailrec fun jumlahDeret(n: Int, acc: Int = 0): Int {
    return if (n == 0) acc else jumlahDeret(n - 1, acc + n)
}

fun main() {
    println("5! = ${faktorial(5)}")
    println("10! = ${faktorial(10)}")
    println("20! = ${faktorial(20)}")

    println("fib(10) = ${fib(10)}")
    println("fib(20) = ${fib(20)}")

    println("Jumlah deret 1..100 = ${jumlahDeret(100)}")
}

Output yang Dihasilkan:

5! = 120
10! = 3628800
20! = 2432902008176640000
fib(10) = 55
fib(20) = 6765
Jumlah deret 1..100 = 5050

Mari kita bedah baris per baris:

1. tailrec fun faktorial(n: Long, acc: Long = 1): keyword tailrec memberi tahu kompilator untuk mengoptimalkan. Parameter acc adalah akumulator yang membawa hasil parsial — 5 dipanggil dengan acc=1, lalu rekursif faktorial(4, 5), faktorial(3, 20), dan seterusnya.
2. if (n <= 1) acc else faktorial(n - 1, acc * n): pemanggilan rekursif faktorial(n - 1, acc * n) adalah operasi terakhir. Tidak ada operasi tambahan setelah pemanggilan rekursif kembali — syarat tail recursion terpenuhi.
3. tailrec fun fib(n: Int, a: Long = 0, b: Long = 1): dua akumulator a dan b membawa dua angka terakhir deret Fibonacci. Pemanggilan rekursif fib(n - 1, b, a + b) memajukan deret satu langkah.
4. fib(20): meskipun input besar, tidak terjadi StackOverflowError karena kompilator menulis ulang pemanggilan menjadi loop.

Mengapa Tail Recursion Aman #

Pada rekursi biasa, setiap pemanggilan function menempatkan frame baru di call stack. Frame ini berisi parameter lokal, alamat kembali, dan konteks eksekusi. Bila kedalaman mencapai ribuan, stack habis dan program berhenti dengan StackOverflowError. Tail recursion memungkinkan kompilator mengganti frame yang sama — alih-alih membuat frame baru, kompilator memperbarui parameter dan melompat kembali ke awal function.

fun faktorialBiasa(n: Long): Long {
    return if (n <= 1) 1L else n * faktorialBiasa(n - 1)
}

Versi faktorialBiasa di atas tidak dalam bentuk tail karena setelah pemanggilan rekursif faktorialBiasa(n - 1) kembali, hasilnya dikalikan dengan n. Akibatnya, kompilator tidak dapat menulis ulang menjadi loop. Pada input besar (misalnya 100000), function ini akan melempar StackOverflowError. Penambahan keyword tailrec pun tidak akan membantu — kompilator akan melaporkan peringatan bahwa function tidak dalam bentuk tail.

Syarat tailrec Berhasil #

Tiga syarat utama agar tailrec benar-benar dioptimalkan kompilator:

• pemanggilan rekursif harus menjadi operasi terakhir sebelum return
• pemanggilan rekursif tidak boleh berada dalam blok try-catch-finally
• pemanggilan rekursif tidak boleh berada dalam finally

Bila salah satu syarat tidak terpenuhi, kompilator memancarkan peringatan “A function is marked as tailrec but it is not tail recursive” dan tidak melakukan optimasi. Function tetap berjalan benar, tetapi tetap rentan terhadap stack overflow pada input besar.

Pemilihan Bentuk Rekursi vs Loop #

Antara tailrec dan loop biasa, keduanya menghasilkan bytecode yang serupa. Pemilihan bergantung pada keterbacaan. Algoritma yang secara natural rekursif (pohon, graf, divide-and-conquer) terbaca lebih jelas dalam bentuk rekursif. Operasi linier sederhana seperti penjumlahan 1..N sering kali lebih jelas dalam bentuk loop for.

tailrec fun jumlahTailrec(n: Int, acc: Int = 0): Int =
    if (n == 0) acc else jumlahTailrec(n - 1, acc + n)

fun jumlahLoop(n: Int): Int {
    var total = 0
    for (i in 1..n) total += i
    return total
}

Kedua function di atas menghasilkan output yang sama dan kinerja yang setara. Pilih bentuk yang paling jelas untuk konteks Anda.

Referensi Lanjutan #

• Kotlin functions — panduan resmi tailrec function yang dioptimalkan compiler menjadi loop iteratif
• Kotlin control flow — rujukan control flow Kotlin untuk if dan when yang dipakai pada rekursi tail

Ringkasan #

Keyword tailrec memberi tahu kompilator untuk menulis ulang rekursi menjadi loop iteratif, menghindari pertumbuhan call stack. Syarat utama adalah pemanggilan rekursif menjadi operasi terakhir — gunakan akumulator untuk membawa hasil parsial. Bila syarat tidak terpenuhi, kompilator memberi peringatan tanpa mengoptimasi. Pada chapter Higher-Order Functions berikutnya, kita akan melihat bagaimana function dapat menerima dan mengembalikan function lain sebagai nilai.