Đệ quy trong Kotlin

Ở bài trước chúng ta đã học xong cách tạo function, vậy thì trong bài này ta sẽ vận dụng nó để học một kiến thức mới đó là tạo hàm đệ quy trong Kotlin.

Hàm được gọi là hàm đệ quy nếu nó tự gọi chính nó và quá trình này được gọi là đệ quy. Quá trình này sẽ kết thúc khi gặp một điều kiện thoát.

1. Như thế nào là hàm đệ quy?

Ở đây hàm myfunction() tự gọi nó, đây là hàm đệ quy.

fun myfunction(){    
  //some code  
  ....
  //myfunction() calling myfunction()
  myfunction()   
}

Cùng xem thêm ví dụ để hiểu về hàm đệ quy hơn.

Bài viết này được đăng tại [kiso.vn]

2. Ví dụ về hàm đệ quy trong Kotlin

Chúng ta hãy tìm hiểu đệ quy qua ví dụ về tính giai thừa. Ở đây chúng ta định nghĩa một hàm fact() để tính giai thừa của một số mà nó truyền cho hàm này dưới dạng tham số. Trong thân hàm, chúng ta gọi hàm này một lần nữa, quá trình này được gọi là đệ quy.

Chúng ta nhập Input là một số, chương trình sử dụng Input này làm đối số cho hàm fact().

fun main(args: Array<String>) {
    print("Enter a positive integer number: ")
    val number: Int =Integer.valueOf(readLine())
    val factorial = fact(number)
    println("Factorial of $number = $factorial")
}

//recursive function
fun fact(num: Int): Int {
    return if(num == 1){
        num
    }
    else{
        //function fact() calling itself
        num*fact(num-1)
    }
}

OUTPUT:

24 Kotlin recursive function jpg

3. Đệ quy đuôi tron Kotlin

Trong đệ quy, tính toán được thực hiện sau lệnh gọi đệ quy. Ví dụ về giai thừa mà chúng ta đã thấy ở trên là một ví dụ về đệ quy hoặc đệ quy đầu. Trong đó để tính giai thừa của n chúng ta cần giai thừa của n-1.

Trong đệ quy đuôi, việc tính toán được thực hiện ngay từ đầu trước khi gọi đệ quy. Lệnh gọi hàm đệ quy xảy ra ở cuối hàm. Điều đó có nghĩa là việc tính toán được thực hiện trước và sau đó được chuyển sang lệnh gọi đệ quy tiếp theo.

Chúng ta hãy tìm hiểu rõ hơn qua ví dụ về đệ quy đuôi.

4. Ví dụ về đệ quy đuôi

Để khai báo hàm đệ quy đuôi, chúng ta sử dụng tailrec trước hàm.

fun main(args: Array<String>) {
    val number = 6
    val factorial = fact(number)
    println("Factorial of $number = $factorial")
}

tailrec fun fact(n: Int, temp: Int = 1): Int {
    return if (n == 1){
        temp
    } else {
        fact(n-1, temp*n)
    }
}

OUTPUT:

25 Tail recursion jpg

Bài viết liên quan

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *