Pada artikel ini, Anda akan belajar membuat fungsi rekursif; fungsi yang memanggil dirinya sendiri. Selain itu, Anda akan belajar tentang fungsi rekursif ekor.
Fungsi yang memanggil dirinya sendiri dikenal sebagai fungsi rekursif. Dan, teknik ini dikenal sebagai rekursi.
Contoh dunia fisik adalah menempatkan dua cermin paralel saling berhadapan. Objek apa pun di antara mereka akan dipantulkan secara rekursif.
Bagaimana rekursi bekerja dalam pemrograman?
fun main (args: Array) (… recurse ()…) fun recurse () (… recurse ()…)
Di sini recurse()fungsi dipanggil dari tubuh recurse()fungsi itu sendiri. Berikut cara kerja program ini:
Di sini, panggilan rekursif berlanjut selamanya menyebabkan rekursi tak terbatas.
Untuk menghindari rekursi tak terbatas, if… else (atau pendekatan serupa) dapat digunakan di mana satu cabang membuat panggilan rekursif dan yang lainnya tidak.
Contoh: Menemukan faktorial dari suatu Angka menggunakan Rekursi
fun main(args: Array) ( val number = 4 val result: Long result = factorial(number) println("Factorial of $number = $result") ) fun factorial(n: Int): Long ( return if (n == 1) n.toLong() else n*factorial(n-1) )
Saat Anda menjalankan program, hasilnya adalah:
Faktorial 4 = 24
Bagaimana program ini bekerja?
Pemanggilan factorial()fungsi rekursif dapat dijelaskan pada gambar berikut:
Berikut langkah-langkahnya:
factorial (4) // pemanggilan fungsi pertama. Argumen: 4 4 * faktorial (3) // pemanggilan fungsi ke-2. Argumen: 3 4 * (3 * factorial (2)) // pemanggilan fungsi ke-3. Argumen: 2 4 * (3 * (2 * factorial (1))) // pemanggilan fungsi ke-4. Argumen: 1 4 * (3 * (2 * 1)) 24
Rekursi Ekor Kotlin
Rekursi tail adalah konsep umum daripada fitur bahasa Kotlin. Beberapa bahasa pemrograman termasuk Kotlin menggunakannya untuk mengoptimalkan panggilan rekursif, sedangkan bahasa lain (misalnya Python) tidak mendukungnya.
Apa itu rekursi ekor?
Dalam rekursi normal, Anda melakukan semua panggilan rekursif terlebih dahulu, dan menghitung hasil dari nilai yang dikembalikan pada akhirnya (seperti yang ditunjukkan pada contoh di atas). Karenanya, Anda tidak akan mendapatkan hasil sampai semua panggilan rekursif dilakukan.
Dalam rekursi ekor, penghitungan dilakukan terlebih dahulu, kemudian panggilan rekursif dijalankan (panggilan rekursif meneruskan hasil dari langkah Anda saat ini ke panggilan rekursif berikutnya). Ini membuat panggilan rekursif setara dengan perulangan, dan menghindari risiko stack overflow.
Kondisi untuk rekursi ekor
Fungsi rekursif memenuhi syarat untuk rekursi ekor jika pemanggilan fungsi itu sendiri adalah operasi terakhir yang dilakukannya. Sebagai contoh,
Contoh 1: Tidak memenuhi syarat untuk rekursi ekor karena pemanggilan fungsi itu sendiri n*factorial(n-1)bukanlah operasi terakhir.
fun factorial (n: Int): Long (if (n == 1) (return n.toLong ()) else (return n * factorial (n - 1)))
Contoh 2: Memenuhi syarat untuk rekursi ekor karena pemanggilan fungsi itu sendiri fibonacci(n-1, a+b, a)adalah operasi terakhir.
fun fibonacci (n: Int, a: Long, b: Long): Long (return if (n == 0) b else fibonacci (n-1, a + b, a))
Untuk memberi tahu compiler agar melakukan rekursi tail di Kotlin, Anda perlu menandai fungsi dengan tailrecpengubah.
Contoh: Rekursi Ekor
import java.math.BigInteger fun main(args: Array) ( val n = 100 val first = BigInteger("0") val second = BigInteger("1") println(fibonacci(n, first, second)) ) tailrec fun fibonacci(n: Int, a: BigInteger, b: BigInteger): BigInteger ( return if (n == 0) a else fibonacci(n-1, b, a+b) )
Saat Anda menjalankan program, hasilnya adalah:
354224848179261915075
Program ini menghitung suku ke- 100 dari deret Fibonacci. Karena, hasilnya bisa berupa bilangan bulat yang sangat besar, kami telah mengimpor kelas BigInteger dari pustaka standar Java.
Di sini, fungsi fibonacci()tersebut ditandai dengan tailrecpengubah dan fungsi tersebut memenuhi syarat untuk panggilan rekursif ekor. Oleh karena itu, compiler mengoptimalkan rekursi dalam kasus ini.
Jika Anda mencoba menemukan suku ke- 20000 (atau bilangan bulat besar lainnya) dari deret Fibonacci tanpa menggunakan rekursi ekor, kompilator akan mengeluarkan java.lang.StackOverflowErrorpengecualian. Namun, program kami di atas berfungsi dengan baik. Itu karena kami telah menggunakan rekursi ekor yang menggunakan versi berbasis loop yang efisien daripada rekursi tradisional.
Contoh: Faktorial Menggunakan Rekursi Ekor
Contoh untuk menghitung faktorial angka dalam contoh di atas (contoh pertama) tidak dapat dioptimalkan untuk rekursi ekor. Berikut adalah program berbeda untuk melakukan tugas yang sama.
fun main(args: Array) ( val number = 5 println("Factorial of $number = $(factorial(number))") ) tailrec fun factorial(n: Int, run: Int = 1): Long ( return if (n == 1) run.toLong() else factorial(n-1, run*n) )
Saat Anda menjalankan program, hasilnya adalah:
Faktorial 5 = 120
Kompilator dapat mengoptimalkan rekursi dalam program ini karena fungsi rekursif memenuhi syarat untuk rekursi tail, dan kami telah menggunakan tailrecpengubah yang memberi tahu kompilator untuk mengoptimalkan rekursi.
