Trong bài viết này, bạn sẽ học cách tạo các hàm đệ quy (hàm đệ quy là một hàm mà gọi chính nó. Ngoài ra, bạn cũng sẽ tìm hiểu về hàm đệ quy đuôi.
Một hàm mà gọi chính nó được gọi là hàm đệ quy. Và, kỹ thuật này được gọi là đệ quy.
Có một ví dụ trong vật lý như sau: đặt hai gương song song đối diện nhau. Bất kỳ vật nào có vị trí ở giữa 2 gương ấy sẽ được phản chiếu đệ quy.
Nội dung chính
1. Đệ quy trong lập trình làm việc như thế nào?
fun main(args: Array<String>) {
... .. ...
recurse()
... .. ...
}
fun recurse() {
... .. ...
recurse()
... .. ...
}
Ở đây, hàm recurse() được gọi từ thân của chính hàm recurse() ấy. Sau đây là cách chương trình này hoạt động:
Ở đây, việc gọi đệ quy tiếp tục diễn ra và gây ra hiện tượng đệ quy vô hạn.
Để tránh đệ quy vô hạn, chúng ta có thể sử dụng biểu thức if … else (hoặc các cách tương tự), sao cho trong đó, một nhánh thực hiện việc gọi hàm đệ quy và nhánh khác không thực hiện việc gọi hàm đệ quy.
1.1. Ví dụ: Tìm giai thừa của một số bằng cách sử dụng đệ quy
/*
Cafedev.vn - Kênh thông tin IT hàng đầu Việt Nam
@author cafedevn
Contact: cafedevn@gmail.com
Fanpage: https://www.facebook.com/cafedevn
Group: https://www.facebook.com/groups/cafedev.vn/
Instagram: https://instagram.com/cafedevn
Twitter: https://twitter.com/CafedeVn
Linkedin: https://www.linkedin.com/in/cafe-dev-407054199/
Pinterest: https://www.pinterest.com/cafedevvn/
YouTube: https://www.youtube.com/channel/UCE7zpY_SlHGEgo67pHxqIoA/
*/
fun main(args: Array<String>) {
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, kết quả sẽ là:
Factorial of 4 = 241.2. Chương trình này hoạt động như thế nào?
Việc gọi đệ quy của hàm factorial() có thể được giải thích trong hình sau:
Dưới đây là các bước làm liên quan:
factorial(4) // 1st function call. Argument: 4
4*factorial(3) // 2nd function call. Argument: 3
4*(3*factorial(2)) // 3rd function call. Argument: 2
4*(3*(2*factorial(1))) // 4th function call. Argument: 1
4*(3*(2*1))
242. Đệ quy đuôi trong Kotlin
Đệ quy đuôi là một khái niệm chung chung chứ không phải là một tính năng của ngôn ngữ lập trình Kotlin. Một số ngôn ngữ lập trình (bao gồm Kotlin) sử dụng nó để tối ưu hóa việc gọi đệ quy, trong khi các ngôn ngữ khác (ví dụ như Python) thì lại không hỗ trợ chúng.
2.1. Đệ quy đuôi là gì?
Trong đệ quy thông thường, trước tiên bạn thực hiện việc gọi đệ quy và cuối cùng mới tính kết quả từ các giá trị trả về (như đã hiển thị trong ví dụ trên). Do đó, bạn không nhận được kết quả cho đến khi tất cả thao tác gọi đệ quy được thực hiện.
Trong đệ quy đuôi, các phép tính được thực hiện trước, sau đó mới gọi đệ quy (việc gọi đệ quy chuyển kết quả của bước hiện tại sang bước gọi đệ quy tiếp theo). Điều này khiến cho việc gọi đệ quy tương đương với vòng lặp và tránh nguy cơ tràn stack.
2.2. Điều kiện của đệ quy đuôi
Một hàm đệ quy đủ điều kiện để thực hiện đệ quy đuôi nếu thao tác cuối cùng mà nó thực hiện là việc gọi chính nó. Ví dụ,
Ví dụ 1: Không đủ điều kiện cho đệ quy đuôi vì việc hàm gọi đến chính nó n*factorial(n-1) không phải là thao tác cuối cùng.
fun factorial(n: Int): Long {
if (n == 1) {
return n.toLong()
} else {
return n*factorial(n - 1)
}
}Ví dụ 2: Đủ điều kiện để thực hiện đệ quy đuôi vì việc hàm gọi đến 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)
}Để báo cho 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 modifier tailrec.
2.3. Ví dụ: Đệ quy đuôi
/*
Cafedev.vn - Kênh thông tin IT hàng đầu Việt Nam
@author cafedevn
Contact: cafedevn@gmail.com
Fanpage: https://www.facebook.com/cafedevn
Group: https://www.facebook.com/groups/cafedev.vn/
Instagram: https://instagram.com/cafedevn
Twitter: https://twitter.com/CafedeVn
Linkedin: https://www.linkedin.com/in/cafe-dev-407054199/
Pinterest: https://www.pinterest.com/cafedevvn/
YouTube: https://www.youtube.com/channel/UCE7zpY_SlHGEgo67pHxqIoA/
*/
import java.math.BigInteger
fun main(args: Array<String>) {
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, kết quả sẽ là:
354224848179261915075Chương trình này tính toán số thứ 100 của chuỗi Fibonacci. Vì output có thể là một số nguyên rất lớn, ta đã phải import class BigInteger từ thư viện chuẩn Java.
Ở đây, hàm fibonacci()được đánh dấu bằng modifier tailrec và chức năng đủ điều kiện cho cuộc 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 muốn tìm số 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ẽ ném ngoại lệ java.lang.StackOverflowError. Tuy nhiên, chương trình của chúng ta ở trên vẫn hoạt động tốt. Đó là bởi vì chúng ta đã sử dụng đệ quy đuôi, tức là sử dụng phiên bản dựa trên vòng lặp hiệu quả thay vì dùng đệ quy thông thường.
2.4. Ví dụ: Tìm giai thừa bằng cách sử dụng đệ quy đuôi
Chương trình 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 việc sử dụng đệ quy đuôi. Bạn hãy tham khảo chương trình dưới đây, chương trình này cũng thực hiện việc tìm giai thừa.
fun main(args: Array<String>) {
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, kết quả sẽ là:
Factorial of 5 = 120Trì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 để thực hiện đệ quy đuôi và chúng ta đã sử dụng modifier tailrec cho trình biên dịch để tối ưu hóa đệ quy.
