Rekursi dan tailrec

Kasus dasar rekursi dan optimasi tail-recursive dengan tailrec.

Daftar isi

Rekursi adalah teknik pemecahan masalah dengan fungsi yang memanggil dirinya sendiri hingga mencapai kasus dasar. Setiap pemanggilan rekursif menumpuk kerangka panggilan pada tumpukan (stack) program, sehingga rekursi yang terlalu dalam dapat menghabiskan tumpukan itu. Topik ini membahas struktur rekursi yang benar, perilaku rekursi yang dalam, serta modifier tailrec yang mengubah rekursi menjadi perulangan.

Struktur rekursi yang benar#

Fungsi rekursif memerlukan dua bagian, yaitu kasus dasar yang menghentikan pemanggilan dan langkah rekursif yang memperkecil masalah. Tanpa kasus dasar, pemanggilan tidak pernah berhenti. Untuk faktorial, kasus dasarnya adalah n bernilai 1 atau kurang, sedangkan langkah rekursifnya mengalikan n dengan faktorial dari n - 1 sesuai definisi berikut.

n! = n \times (n-1) \times (n-2) \times \cdots \times 1

Program berikut memuat fungsi faktorial rekursif bertipe Int yang mengikuti definisi tersebut.

kotlin main.kt

// Faktorial rekursif: kasus dasar dan langkah rekursif
fun faktorial(n: Int): Int {
    return if (n <= 1) 1 else n * faktorial(n - 1)
}

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

bash

# compiler Kotlin dan pustaka standar yang dipakai jalur ini
export PATH=/home/kal/my-project/tools/kotlinc/bin:/home/kal/my-project/tools/jdk-merged/bin:$PATH
export STDLIB=/home/kal/my-project/tools/kotlinc/lib/kotlin-stdlib.jar
# kompilasi berkas main.kt menjadi out.jar, lalu jalankan programnya
kotlinc main.kt -d out.jar && java -cp "out.jar:$STDLIB" MainKt

text Keluaran

5!  = 120
10! = 3628800

Keluaran menunjukkan 5! bernilai 120 dan 10! bernilai 3628800, dan keduanya masih berada dalam jangkauan tipe Int. Nilai 13! sudah melebihi batas atas Int yang besarnya 2147483647, sehingga fungsi faktorial bertipe Int hanya aman dipakai sampai faktorial 12. Batasan tipe ini terpisah dari batasan kedalaman rekursi yang dibahas pada bagian berikut.

Rekursi dalam dan stack overflow#

Setiap pemanggilan fungsi menyimpan kerangka panggilan pada tumpukan program, berisi parameter, variabel lokal, dan titik kembalinya. Pada rekursi biasa, kerangka tidak boleh dilepaskan sebelum pemanggilan rekursifnya selesai, sehingga kedalaman rekursi terbatas oleh besarnya tumpukan. Program berikut memanggil fungsi rekursif sederhana dengan kedalaman 100000.

kotlin dalam.kt

fun turun(n: Int): Int {
    return if (n == 0) 0 else turun(n - 1)
}

fun main() {
    println(turun(100000))
}

bash

# kompilasi lalu jalankan, dengan keluaran dibatasi empat baris pertama
kotlinc dalam.kt -d dalam.jar && java -cp "dalam.jar:$STDLIB" DalamKt 2>&1 | head -4

text Keluaran

Exception in thread "main" java.lang.StackOverflowError
	at DalamKt.turun(dalam.kt:2)
	at DalamKt.turun(dalam.kt:2)
	at DalamKt.turun(dalam.kt:2)

Program terhenti dengan java.lang.StackOverflowError, yaitu error yang dilemparkan JVM ketika tumpukan habis. Keluaran di atas hanya menampilkan empat baris pertama dari stack trace yang panjangnya mencapai ribuan baris, karena setiap barisnya menunjuk satu kerangka panggilan yang tertumpuk pada saat program jatuh. Batas tumpukan JVM memang dapat diatur lewat opsi runtime, tetapi menaikkannya hanya menunda masalah, bukan menyelesaikannya. Solusi yang tepat untuk rekursi yang dalam adalah mengubahnya menjadi perulangan, dan modifier tailrec melakukan hal itu secara otomatis.

Optimasi tail-recursive dengan tailrec#

Modifier tailrec menandai fungsi tail-recursive, yaitu fungsi yang pemanggilan rekursifnya menjadi langkah terakhir sebelum hasil dikirim. Pada bentuk ini, compiler mengganti rekursi dengan perulangan biasa sehingga kerangka panggilan tidak lagi menumpuk. Dokumentasi resmi Kotlin menyatakan bahwa optimasi ini menghasilkan versi berbasis perulangan yang cepat dan efisien tanpa risiko stack overflow. Kunci mengubah faktorial menjadi tail-recursive adalah memindahkan perkalian ke dalam argumen melalui akumulator, sehingga pemanggilan rekursif benar-benar menjadi langkah terakhir.

kotlin tailrec.kt

tailrec fun faktorialCepat(n: Int, akumulator: Long = 1): Long {
    return if (n <= 1) akumulator else faktorialCepat(n - 1, akumulator * n)
}

fun main() {
    println("20! = ${faktorialCepat(20)}")
}

bash

# kompilasi berkas tailrec.kt, lalu jalankan programnya
kotlinc tailrec.kt -d tailrec.jar && java -cp "tailrec.jar:$STDLIB" TailrecKt

text Keluaran

20! = 2432902008176640000

Parameter akumulator membawa hasil perkalian sementara dan memiliki nilai bawaan 1, sehingga pemanggil pertama cukup menulis faktorialCepat(20). Perkalian akumulator * n dikerjakan sebelum pemanggilan rekursif, bukan sesudahnya, sehingga setiap pemanggilan menyerahkan seluruh pekerjaan kepada pemanggilan berikutnya. Compiler cukup mengganti nilai parameter lalu mengulang tubuh fungsi tanpa menyimpan kerangka panggilan baru. Hasil 20! tidak muat dalam Int, sehingga akumulator bertipe Long dan keluarannya berupa bilangan besar yang utuh.

Peringatan compiler saat syarat tidak terpenuhi#

Modifier tailrec yang dipasang pada fungsi yang bukan tail-recursive tidak membatalkan kompilasi, tetapi memunculkan peringatan. Berkas berikut memuat fungsi faktorial bentuk awal yang diberi modifier tailrec padahal perkaliannya masih berada setelah pemanggilan rekursif.

kotlin peringatan.kt

tailrec fun hitung(n: Int): Int {
    return if (n <= 1) 1 else n * hitung(n - 1)
}

fun main() {
    println(hitung(5))
}

bash

# kompilasi berkas peringatan.kt dengan tailrec yang tidak terpenuhi syaratnya, lalu jalankan
kotlinc peringatan.kt -d peringatan.jar && java -cp "peringatan.jar:$STDLIB" PeringatanKt

text Keluaran

peringatan.kt:1:1: warning: a function is marked as tail-recursive but no tail calls are found.
tailrec fun hitung(n: Int): Int {
^^^^^^^
peringatan.kt:2:35: warning: recursive call is not a tail call.
    return if (n <= 1) 1 else n * hitung(n - 1)
                                  ^^^^^^
120

Dua peringatan muncul pada keluaran di atas. Peringatan pertama menyatakan bahwa tidak ada tail call yang ditemukan pada fungsi tersebut, sedangkan peringatan kedua menunjuk baris pemanggilan rekursif yang bukan tail call. Program tetap berhasil dikompilasi dan mencetak 120, tetapi rekursinya tidak pernah dioptimasi, sehingga risiko stack overflow tetap ada. Peringatan semacam ini menjadi sinyal untuk merestrukturisasi fungsi dengan akumulator sebagaimana contoh pada bagian sebelumnya.

Ringkasan#

Fungsi rekursif memerlukan kasus dasar dan langkah rekursif yang memperkecil masalah pada setiap pemanggilan.
Rekursi biasa menumpuk kerangka panggilan, sehingga kedalaman yang terlalu besar menghasilkan StackOverflowError.
Modifier tailrec mengganti rekursi dengan perulangan, dengan syarat pemanggilan rekursif menjadi langkah terakhir.
Pola akumulator memindahkan perhitungan ke dalam argumen agar syarat tail call terpenuhi.

Referensi#

Functions — Kotlin Documentation — Bagian tail-recursive functions pada dokumentasi resmi Kotlin.
Command-line compiler — Kotlin Documentation — Cara mengompilasi dan menjalankan program Kotlin dengan kotlinc dari terminal.