Dalam artikel ini, anda akan belajar membuat fungsi rekursif; fungsi yang memanggil dirinya sendiri. Anda juga akan belajar mengenai fungsi rekursif ekor.
Fungsi yang memanggil dirinya dikenali sebagai fungsi rekursif. Dan, teknik ini dikenali sebagai rekursi.
Contoh dunia fizikal ialah meletakkan dua cermin selari yang saling berhadapan. Setiap objek di antara mereka akan dipantulkan secara berulang.
Bagaimana rekursi berfungsi dalam pengaturcaraan?
fun main (args: Array) (… recurse ()…) fun recurse () (… recurse ()…)
Di sini, recurse()fungsi dipanggil dari badan recurse()fungsi itu sendiri. Inilah cara program ini berfungsi:
Di sini, panggilan rekursif berterusan selama-lamanya menyebabkan pengulangan yang tidak terhingga.
Untuk mengelakkan pengulangan yang tidak terbatas, jika… yang lain (atau pendekatan serupa) dapat digunakan di mana satu cabang membuat panggilan rekursif dan yang lain tidak.
Contoh: Cari faktorial bagi Nombor menggunakan Pengulangan
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) )
Semasa anda menjalankan program, outputnya adalah:
Faktor faktor 4 = 24
Bagaimana program ini berfungsi?
Panggilan factorial()fungsi berulang dapat dijelaskan dalam gambar berikut:
Berikut adalah langkah-langkah yang terlibat:
faktorial (4) // panggilan fungsi pertama. Hujah: 4 4 * faktorial (3) // Panggilan fungsi ke-2. Hujah: 3 4 * (3 * faktorial (2)) // Panggilan fungsi ke-3. Hujah: 2 4 * (3 * (2 * faktorial (1))) // Panggilan fungsi ke-4. Hujah: 1 4 * (3 * (2 * 1)) 24
Pengulangan Ekor Kotlin
Pengambilan ekor adalah konsep generik dan bukan ciri bahasa Kotlin. Beberapa bahasa pengaturcaraan termasuk Kotlin menggunakannya untuk mengoptimumkan panggilan berulang, sedangkan bahasa lain (misalnya Python) tidak menyokongnya.
Apakah rekursi ekor?
Dalam rekursi normal, anda melakukan semua panggilan rekursif terlebih dahulu, dan mengira hasilnya dari nilai kembali akhirnya (seperti yang ditunjukkan dalam contoh di atas). Oleh itu, anda tidak mendapat hasil sehingga semua panggilan berulang dibuat.
Dalam rekursi ekor, pengiraan dilakukan terlebih dahulu, kemudian panggilan rekursif dilaksanakan (panggilan rekursif meneruskan hasil langkah anda saat ini ke panggilan rekursif berikutnya). Ini menjadikan panggilan rekursif setara dengan gelung, dan mengelakkan risiko tumpukan tumpahan.
Keadaan untuk berulang ekor
Fungsi recursive layak untuk recursion ekor jika fungsi memanggil dirinya sendiri adalah operasi terakhir yang dilakukannya. Sebagai contoh,
Contoh 1: Tidak layak untuk mengulang ekor kerana fungsi panggilan untuk dirinya sendiri n*factorial(n-1)bukan operasi terakhir.
faktorial yang menyeronokkan (n: Int): Panjang (jika (n == 1) (return n.toLong ()) lain (return n * factorial (n - 1)))
Contoh 2: Layak untuk mengulang ekor kerana fungsi panggilan untuk dirinya sendiri fibonacci(n-1, a+b, a)adalah operasi terakhir.
fibonacci yang menyeronokkan (n: Int, a: Long, b: Long): Long (return if (n == 0) b fibonacci lain (n-1, a + b, a))
Untuk memberitahu penyusun untuk melakukan pengulangan ekor di Kotlin, anda perlu menandakan fungsinya dengan tailrecpengubah.
Contoh: Pengulangan 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) )
Semasa anda menjalankan program, outputnya adalah:
354224848179261915075
This program computes the 100th term of the Fibonacci series. Since, the output can be a very large integer, we have imported BigInteger class from Java standard library.
Here, the function fibonacci() is marked with tailrec modifier and the function is eligible for tail recursive call. Hence, the compiler optimizes the recursion in this case.
If you try to find the 20000th term (or any other big integer) of the Fibonacci series without using tail recursion, the compiler will throw java.lang.StackOverflowError exception. However, our program above works just fine. It's because we have used tail recursion which uses efficient loop based version instead of traditional recursion.
Example: Factorial Using Tail Recursion
Contoh untuk mengira faktorial nombor dalam contoh di atas (contoh pertama) tidak dapat dioptimumkan untuk pengulangan ekor. Berikut adalah program yang berbeza untuk melaksanakan 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) )
Semasa anda menjalankan program, outputnya adalah:
Faktor faktor 5 = 120
Pengkompilasi dapat mengoptimumkan rekursi dalam program ini kerana fungsi rekursif memenuhi syarat untuk pengulangan ekor, dan kami telah menggunakan tailrecpengubah yang memberitahu penyusun untuk mengoptimumkan rekursi.
