Trong bài này, bạn sẽ học cách tạo các hàm đệ quy; một hàm gọi chính nó. Ngoài ra, bạn sẽ tìm hiểu về hàm đệ quy đuôi.
Một hàm gọi chính nó được gọi là hàm đệ quy. Và, kỹ thuật này được gọi là đệ quy.
Một ví dụ về thế giới vật chất là đặt hai gương song song đối diện nhau. Bất kỳ đối tượng nào ở giữa chúng sẽ được phản ánh một cách đệ quy.
Làm thế nào để đệ quy hoạt động trong lập trình?
fun chính (args: Array) (… recurse ()…) fun recurse () (… recurse ()…)
Ở đây, recurse()hàm được gọi từ chính nội dung của recurse()hàm. Đây là cách chương trình này hoạt động:
Ở đây, cuộc gọi đệ quy tiếp tục mãi mãi gây ra đệ quy vô hạn.
Để tránh đệ quy vô hạn, if… else (hoặc cách tiếp cận tương tự) có thể được sử dụng khi một nhánh thực hiện lệnh gọi đệ quy và nhánh khác thì không.
Ví dụ: Tìm giai thừa của một số bằng phép đệ quy
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) )
Khi bạn chạy chương trình, đầu ra sẽ là:
Giai thừa của 4 = 24
Chương trình này hoạt động như thế nào?
Lời gọi đệ quy của factorial()hàm có thể được giải thích trong hình sau:
Dưới đây là các bước liên quan:
giai thừa (4) // Lời gọi hàm thứ nhất. Đối số: 4 4 * giai thừa (3) // Lời gọi hàm thứ 2. Đối số: 3 4 * (3 * giai thừa (2)) // lệnh gọi hàm thứ 3. Đối số: 2 4 * (3 * (2 * giai thừa (1))) // lệnh gọi hàm thứ 4. Đối số: 1 4 * (3 * (2 * 1)) 24
Đệ quy đuôi Kotlin
Đệ quy đuôi là một khái niệm chung chung chứ không phải là tính năng của ngôn ngữ Kotlin. Một số ngôn ngữ lập trình bao gồm Kotlin sử dụng nó để tối ưu hóa các cuộc gọi đệ quy, trong khi các ngôn ngữ khác (ví dụ: Python) không hỗ trợ chúng.
Đệ quy đuôi là gì?
Trong đệ quy thông thường, bạn thực hiện tất cả các lệnh gọi đệ quy trước và cuối cùng tính toán kết quả từ các giá trị trả về (như trong ví dụ trên). Do đó, bạn không nhận được kết quả cho đến khi tất cả các cuộc gọi đệ quy được thực hiện.
Trong đệ quy đuôi, các phép tính được thực hiện đầu tiên, sau đó các lệnh gọi đệ quy được thực hiện (lệnh gọi đệ quy chuyển kết quả của bước hiện tại của bạn cho cuộc gọi đệ quy tiếp theo). Điều này làm cho cuộc gọi đệ quy tương đương với lặp và tránh nguy cơ tràn ngăn xếp.
Điều kiện cho đệ quy đuôi
Một hàm đệ quy đủ điều kiện cho đệ quy đuôi nếu lệnh gọi hàm đến chính nó là hoạt động cuối cùng mà nó thực hiện. Ví dụ,
Ví dụ 1: Không đủ điều kiện cho đệ quy đuôi vì lệnh gọi hàm cho chính nó n*factorial(n-1)không phải là hoạt động cuối cùng.
fun giai thừa (n: Int): Long (if (n == 1) (return n.toLong ()) else (return n * giai thừa (n - 1)))
Ví dụ 2: Đủ điều kiện cho đệ quy đuôi vì hàm gọi chính nó fibonacci(n-1, a+b, a)là thao tác cuối cùng.
fun fibonacci (n: Int, a: Long, b: Long): Long (return if (n == 0) b else fibonacci (n-1, a + b, a))
Để yêu cầu trình biên dịch thực hiện đệ quy đuôi trong Kotlin, bạn cần đánh dấu hàm bằng tailrecsửa đổi.
Ví dụ: Đệ quy đuôi
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) )
Khi bạn chạy chương trình, đầu ra sẽ là:
354224848179261915075
Chương trình này tính toán số hạng thứ 100 của chuỗi Fibonacci. Vì đầu ra có thể là một số nguyên rất lớn, chúng tôi đã nhập lớp BigInteger từ thư viện chuẩn Java.
Ở đây, hàm fibonacci()được đánh dấu bằng công cụ tailrecsửa đổi và hàm đủ điều kiện để gọi đệ quy đuôi. Do đó, trình biên dịch tối ưu hóa đệ quy trong trường hợp này.
Nếu bạn cố gắng tìm số hạng thứ 20000 (hoặc bất kỳ số nguyên lớn nào khác) của chuỗi Fibonacci mà không sử dụng đệ quy đuôi, trình biên dịch sẽ đưa ra java.lang.StackOverflowErrorngoại lệ. Tuy nhiên, chương trình của chúng tôi ở trên hoạt động tốt. Đó là bởi vì chúng tôi đã sử dụng đệ quy đuôi, sử dụng phiên bản dựa trên vòng lặp hiệu quả thay vì đệ quy truyền thống.
Ví dụ: Giai thừa sử dụng đệ quy đuôi
Ví dụ để tính giai thừa của một số trong ví dụ trên (ví dụ đầu tiên) không thể được tối ưu hóa cho đệ quy đuôi. Đây là một chương trình khác để thực hiện cùng một tác vụ.
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) )
Khi bạn chạy chương trình, đầu ra sẽ là:
Giai thừa của 5 = 120
Trình biên dịch có thể tối ưu hóa đệ quy trong chương trình này vì hàm đệ quy đủ điều kiện cho đệ quy đuôi và chúng tôi đã sử dụng công cụ tailrecsửa đổi để thông báo cho trình biên dịch tối ưu hóa đệ quy.
